PROBLEM LINK:Author: Vasya Antoniuk 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:
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$. :D More techniquesOne 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. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 13 Mar '16, 14:18

i tried binary search on 2*1 rectangles but it got me even less score than single binary search solutions don't know why :( answered 15 Mar '16, 15:18

I also solved it using 2x1 rectangles and got more efficient solution. link to my code https://www.codechef.com/viewsolution/9671097 answered 15 Mar '16, 16:54

I used the exact same technique :/ I could only get a score of 0.33 on this problem I really want to know how people crossed 0.5 and how one guy got 1.00 a perfect score answered 17 Mar '16, 14:19

Under the constraints, you can ask two questions per element. So I divided 150 into 4 "zones" and used 2 range questions for each element to determine which zone it lied in. I simply placed my guess corresponding to each element to be the midvalue of the zone it lied in. This fetched me nearly 50 points. :) answered 18 Mar '16, 10:54
