TopCoder problem "ContiguousCache" used in SRM 410 (Division I Level Two)



Problem Statement

    

You are writing a program for a very simple processor. It is attached to a slow memory system that contains n bytes, numbered 0 to n - 1. The processor has a cache which holds a copy of k of these bytes at a time, for fast access. It has a base address (referred to as base below), and it holds a copy of the bytes numbered base, base+1, ..., base+k-1.

In order to keep the processor as simple as possible, the programmer must directly control the cache. To access some byte in memory, the program must first set the cache base address. Any bytes that are in the new range that were not in the old range are read from the memory store, but bytes that were in both the old and new ranges are simply kept in the cache and do not require a read from the memory store.

You wish to optimize a program to use as few memory reads as possible. The bytes that the program accesses, in the order it accesses them, are given in addresses. Determine the minimum number of bytes that must be read from the memory store. Note that when the program starts, the cache is in a special empty state, so the first cache update always requires k bytes to be read.

 

Definition

    
Class:ContiguousCache
Method:minimumReads
Parameters:int, int, int[]
Returns:long
Method signature:long minimumReads(int n, int k, int[] addresses)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 1,000,000,000, inclusive.
-k will be between 1 and n, inclusive.
-addresses will contain between 1 and 50 elements, inclusive.
-Each element of addresses will be between 0 and n-1, inclusive.
 

Examples

0)
    
100
3
{0, 2, 16, 13}
Returns: 7
The first access must read bytes 0 to 2, inclusive. For the second access, no reads are needed, since 2 is already cached. For the third access, the base address should be set to 14. Then for the final access, the base address is set to 13, and only one additional byte must be read.
1)
    
100
10
{1,10,19,28,30,37}
Returns: 29
2)
    
1000000000
500000000
{0, 999999999, 1, 500000000, 500000001, 987654321}
Returns: 1987654320
3)
    
8
2
{7}
Returns: 2

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9728

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12182&pm=9728

Writer:

bmerry

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming