## Balkan OI '11 P4 - Compare

View as PDF

Points: 25 (partial)
Time limit: 10.0s
Memory limit: 128M

Problem type
Allowed languages
C, C++

You must design an algorithm for an ancient computer whose memory is just an array of 10240 bits. The memory is initialized to zero, after which you may write and read a single bit at a time.

You must implement two operations on this computer:

• remember(a): is an integer between 0 and 4095
The implementation of this operation may call:
• bit_set(address): address is an integer between 1 and 10240
• The memory bit at position address will be set to 1
• compare(b): is an integer between 0 and 4095
if , it should return -1
if , it should return 0
if , it should return 1
The implementation of this operation may call:
• bit_get(address)
• Returns the memory bit at position address: 1 if it was set through bit_set() during the remember(a) operation, and 0 otherwise.

Implement remember() and compare() to minimize the total number of memory accesses (bit_set() and bit_get()) in the worst-case for all possible values of and .

Your solution will be evaluated exhaustively:

define AllMemory = array [0..4095][1..10240] of bits
set AllMemory to zeros
for a = 0..4095:
remember(a)
let maxA = the maximum number of bit_set() calls executed for any a
for (a,b) in {0..4095}x{0..4095} in random order (i.e. all valid pairs (a,b) are considered, in some random order)
if answer for comparing a and b is incorrect : your score = 0; exit
let maxB = the maximum number of bit_get() calls executed for any (a,b) pair
T=maxA + maxB
If (T>20): your score = 0; exit
else your score = 1 + 9 * (21 - T); exit

#### Implementation Details

The prototypes for the memory-access functions are:

void bit_set(int addr);


You must implement the functions:

void remember(int value);
int compare(int value);


#### Constraints

• You may be disqualified for any attempt to interact with the memory of the grading code.
• If your solution does not obey the protocol defined above (e.g. calling bit_set() during compare() or with an invalid address), you will receive zero points.
• Time limit: your implementation must execute calls to remember() and calls to compare() in under 10 seconds.