×

CHNGSS - Editorial

Author: Vasya Antoniuk
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

Challenge

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$. :D

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.

AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

1.7k586142
accept rate: 11%

 0 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 5★killjee 476●9 accept rate: 5%
 0 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 4★uddhav 1 accept rate: 0%
 0 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 176●1●7 accept rate: 4%
 0 Under the constraints, you can ask two questions per element. So I divided 1-50 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 mid-value of the zone it lied in. This fetched me nearly 50 points. :-) answered 18 Mar '16, 10:54 21●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,855
×1,056
×858
×192

question asked: 13 Mar '16, 14:18

question was seen: 1,962 times

last updated: 27 Mar '16, 22:31