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.