PROBLEM LINK:
Author: Vasya Antoniuk
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Challenge
PREREQUISITES:
Binary search
PROBLEM:
There is a rectangular matrix A of n\times m integers which you have to guess. You can ask the following questions:
- range: given i_L, i_R, j_L, j_R, x, y, how many integers A_{i,j} are there such that i_L \le i \le i_R, j_L \le j \le j_R and x \le A_{i,j} \le y?
- sum: given i_L, i_R, j_L, j_R, what is \sum_{i,j} A_{i,j} for all i_L \le i \le i_R, j_L \le j \le j_R?
You can ask at most 5\times 10^5 questions and at most C sum questions.
Your score is computed based on the number of questions, the number of correct guesses, and the accuracy of your guess.
EXPLANATION:
As usual with tiebreaker questions, your score on the challenge problem depends on the score you get relative to the best score in the contest. In this month’s challenge problem, it is quite easy to get “Correct answer” by simply not asking questions and guessing A completely, say by printing an n\times m grid consisting of 1 s.
A slightly better guess would be to print a grid consisting of $25$s (or $26$s), because we know that 1 \le A_{i,j} \le 50 and they are generated randomly. Thus, without any other information, this might be one of the best possible guesses you can make.
Now, let’s try asking questions to get more information. A simple idea is to use sum questions to exactly determine some entries of A. For example, if we want to know A_{6,9}, then we can ask a sum question with (i_L, i_R, j_L, j_R) = (6,6,9,9), which represents a 1\times 1 rectangle. The “sum” of this rectangle is simply A_{6,9}. Repeating this C times gives us C entries of A exactly.
For the remaining entries, we can use range questions. One possible technique is to use binary search on individual entries of A. For example, suppose we want to determine A_{6,9}. Then we can ask a range question with (i_L, i_R, j_L, j_R, x, y) = (6,6,9,9,1,50), and then gradually adjust x and y with binary search until we determine A_{6,9}. It only takes 6 questions to determine each entry with binary search, so we can possibly determine many entries of A exactly.
Once we run out of questions, we can simply fall back to our best guess of 25. 
More techniques
One possible technique to save a few range questions might be to binary search two elements simultaneously. Specifically, if we want to determine two adjacent entries of A, we can perform binary search on both entries simultaneously using a 2\times 1 rectangle at first, and then diverging into separate binary searches once they fall into separate intervals. This might save a few questions in the long run. Also, this technique might be generalizable to more than two entries.
Another possible technique: Note that some parameters are hidden from you in this problem (a_1, a_2 and a_3). You could consider submitting your best algorithm many times, but each one trying a different RNG seed (and possibly guesses of these hidden parameters). This way, you get a higher chance of getting a good score (even though your submission might not get the highest score during preliminary scoring.)
What about you? What are your solutions? Feel free to share them below.
I could only get a score of 0.33 on this problem