Efficient Memory Comparison Challenge

We are given a 2D binary array \( mem \) of dimensions \(4096 \times 10240\) (the first dimension indices from 0 to 4095 and the second dimension indices from 1 to 10240) initialized with zeros.

You must implement two functions that operate on the \(01\) array:

• void remember(int a)
• int compare(int b)

Function Details:

void remember(int a):

• It is guaranteed that \(0 \le a \le 4095\).
• You are allowed to call void bit_set(int ad) with \(1 \le ad \le 10240\). Calling bit_set(ad) sets \( mem_{a,ad} = 1 \).

int compare(int b):

• It is guaranteed that \(0 \le b \le 4095\).
• The function must compare the unknown value \(a\) (which was passed earlier to remember) with \(b\) and return:
  • \(-1\) if \(b < a\),
  • 0 if \(b = a\),
  • 1 if \(b > a\).
• You are allowed to call int bit_get(int ad) with \(1 \le ad \le 10240\). This returns the value of \( mem_{a,ad} \).

Objective: Implement the functions remember and compare so as to minimize the number of calls to bit_set and bit_get.

The scoring is computed using the following pseudo‐code:

define AllMemory = array [0..4095][1..10240] of bits
set AllMemory to zeros
for a = 0..4095:
    define bit_set(address): AllMemory[a][address] = 1
    remember(a)
let maxA = the maximum number of bit_set() calls executed for any a

for (a,b) ∈ {0..4095}×{0..4095} in random order
    define bit_get(address): return AllMemory[a][address]
    answer = compare(b)
    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

Note: The total worst‐case number of calls (T) must not exceed 20. In our sample solution below we take advantage of the fact that you may use extra memory. Here, we simply store the remembered value a in a global variable (thus using only 1 call to bit_set in remember and 0 calls to bit_get in compare). This yields \(T = 1 + 0 = 1\) which is well within the limit.

---

Implementation Requirements: Your submission must provide implementations of both functions in five languages: Python 3, C++, Java, C, and JavaScript. Your code should be accepted by all test cases.

inputFormat

This is an interactive‐style problem. For the purpose of testing, the input will consist of two integers on separate lines. The first integer is the value a to be passed to remember and the second integer is the value b to be passed to compare.

Your submitted functions remember and compare will be called by the judging environment; however, for testing your solution locally, you should simulate the calls as follows:

read a
call remember(a)
read b
print compare(b)

outputFormat

Output a single integer which is the result of compare(b) after having called remember(a). The output should be:

• -1 if \(b < a\),
• 0 if \(b = a\),
• 1 if \(b > a\).

sample

1000
999

-1