Editorial for Another Contest 5 Problem 4 - Tudor Interacts With Poop


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

For the first subtask, we first note that there are 961 lattice points inside the rectangle. Therefore, we can query all of them and find the corners of the rectangle directly as the top-left, top-right, bottom-left, and bottom-rightmost points.

For the second subtask, we cannot query close to the total number of lattice points. The bound of K = 10 looks suspiciously like \left\lceil 2 \log_2 30 \right\rceil, but this is intended as a bait to trick people who automatically assume that every interactive problem is intended to be solved with binary search.

The intended solution for the second subtask is to start by querying all four corners of the rectangle. This is a good first step because intuitively the most obvious way of seeing if the corner is in the rectangle is by querying it directly. We'll focus exclusively on the origin. If the answer we get back is K, then we know that the lower-left corner of the rectangle lies on the line x+y = K. If we query (0, 30), we know that the top-left corner lies on the line y = x+30-K. If we could query any point on the plane, we would then query the intersection point of those two lines to get the distance of the left side of the rectangle to the line x = 0. We forcibly snap the x-coordinate to zero and discretize the y-coordinate if it doesn't lie on a lattice point. Repeating this process for all four sides, we only need eight queries.

To get full credit, we first realize that we don't need to query all four corners - querying any three corners automatically allows us to infer the line for the fourth corner. Finally, with three of these lines, identifying one corner as being on one of the lines automatically forces the other corners to be realized, so we only need to query for one side of the rectangle.


Comments


  • -1
    discoverMe  commented on July 22, 2019, 10:29 p.m. edit 3

    Wait... You can query more than once per instance?? :poggers: :poggers:

    update: You can