You are not logged in. Please login at www.codechef.com to post your questions!

×

CHNGSS - Editorial

PROBLEM LINK:

Contest
Practice

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

setter
tester

This question is marked "community wiki".

asked 13 Mar '16, 14:18

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 27 Mar '16, 22:31


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

link

answered 15 Mar '16, 15:18

killjee's gravatar image

5★killjee
4769
accept rate: 5%

I also solved it using 2x1 rectangles and got more efficient solution. link to my code https://www.codechef.com/viewsolution/9671097

link

answered 15 Mar '16, 16:54

uddhav's gravatar image

4★uddhav
1
accept rate: 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

link

answered 17 Mar '16, 14:19

dollarakshay's gravatar image

4★dollarakshay
17617
accept rate: 4%

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. :-)

link

answered 18 Mar '16, 10:54

kinginthenorth's gravatar image

4★kinginthenorth
212
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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