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

×

MANRECT - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Noszály Áron
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh

DIFFICULTY:

Medium

PREREQUISITES:

Observation would do. Manhattan distance and basic Math.

PROBLEM:

Using at most $Q$ queries, we need to identify the hidden rectangle chosen by Chef in a square grid of width and height $10^9$ each. In each query, we give a point $P(x, y)$ and chef tells us minimum Manhattan distance from point P to any point inside the rectangle. For full points, we have $Q = 7$ (excluding printing the hidden rectangle). $q(x, y)$ denote query for point $(x, y)$.

Let hidden rectangle be $(x1, y1, x2, y2)$ (Rectangle with lower left corner at $(x1, y1)$ and upper right corner at $(x2, y2)$.

QUICK EXPLANATION

  • First make two queries $(0,0)$ and $(0, 10^9)$. Let their answers be $d1$ and $d2$ respectively.
  • By math, we can work out that $y1 \leq t = (d1+10^9-d2)/2 \leq y2$. So, we know that $x1 = q(0, t/2)$ and $x2 = 10^9-q(0, 10^9)$. Now, using equations, we can work out values of $y1$ and $y2$, thus identifying the rectangle in four queries.

EXPLANATION

For the first subtask, we can simply query each possible point $(x, y)$ for $0 \leq x, y \leq 100$ in total $101^2$ queries and determine the hidden rectangle, as all points inside or on the border of rectangle shall have Minimum Manhattan distance zero.

For subtask two, we have $70$ queries which are approximately $2*log_2(10^9)$ which hints towards a binary search solution using two binary searches or similar. Indeed, The original setter solution was this binary search solution. See the image below.

alt text

Let us rewrite query answer as per our problem. Here, for Point $P(x, y)$ and hidden rectangle $(x1,y1,x2,y2)$, query gives $x1-x$ if $x < x1$, $0$ if $x1 \leq x \leq x2$ and $x-x2$ if $x > x2$ as steps moved parallel to line OX. Similar cases hold for y coordinate.

Now, The red region denotes the hidden rectangle chosen by the chef. It can be seen that querying in this region is useless since the answer to each query shall be zero here. The green region is the most preferable region since, in this region, either the x component or the y component of Manhattan distance shall be zero, thus providing us with the value of the other component of Manhattan distance. This way, Once we find any value $x$ such that $x1 \leq x \leq x2$ (or similar for y coordinate), we can use two queries $(x, 0)$ and $(x, INF)$ to determine the values of $y1$ and $y2$ which can be substituted back so as to determine $x1$ and $x2$.

This is where binary search comes in. We run binary search twice, Once for $x1$ and then for $x2$. See how it works in hidden box.

View Content

Now, we have seen how to solve this problem by binary search, but need to solve it in even lesser queries. Now, Let's query Two non-opposite corners, say $(0,0)$ and $(10^9,0)$. It can be seen that $q(0,0) = x1+y1$ and $q(10^9,0) = 10^9-x2+y1$. By eliminating $y1$, we get $x1+x2 = q(0,0)+10^9-q(10^9,0)$.

Here comes the interesting part. We were earlier finding any point of form $(x, 0)$ using binary search. We know, that average of two numbers always lie between the two numbers. Hence, $x$ = average of $x1$ and $x2$ = $(x1+x2)/2$. This implies that $x1 \leq x \leq x2$. Hence, Point $(x, 0)$ lies in green region. We can easily find $y1 = q(x, 0)$ and $y2 = 10^9-q(x, 10^9)$.

So, we have managed to solve the problem in four queries.

For anyone still facing a problem, refer the box.

View Content

Time Complexity

Time complexity is $O(1)$ per test case.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 14 Feb, 00:10

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 16 Feb, 16:41

admin's gravatar image

0★admin ♦♦
19.8k350498541

Solutions' links not working, as usual.

(17 Feb, 15:50) the_extractor4★

@admin Can you post code with binary search for subtask-2? Also not able to access solutions posted here.

link

answered 17 Feb, 14:49

prmondal's gravatar image

3★prmondal
512
accept rate: 0%

edited 17 Feb, 14:50

Even I want to know how binary search works here. It would be good if someone posts an explanation.

(17 Feb, 15:54) the_extractor4★

Testers binary search solution https://ideone.com/MR3WdX

(19 Feb, 12:53) taran_14076★

Only 4 equations are necessary for finding out the secret rectangle

here's my handwritten proof

link

answered 18 Feb, 23:21

rajput1999's gravatar image

5★rajput1999
3716
accept rate: 0%

Thanks @rajput1999, your handwritten notes was very helpful for me. I wanted to upvote but due to less reputation couldn't.

(22 Feb, 08:47) aashkumar53★

Hello please review my code or please let me know for which test case it is failing

https://www.codechef.com/viewsolution/23066914

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    try {
        int t = Integer.parseInt(br.readLine().trim());
        long delta = 1000000000;
        long x = 0, y = 0, distance = 0, xl = 0, yl = 0, aux = 0, gussDistance = 0;
        long xu = 0, yu = 0, rp = 0;
        int wa = 0;
        for (int i = 0; i < t; i++) {
            x = 0;
            y = 0;
            xu = 0;
            yu = 0;
            distance = 0;
            xl = 0;
            yl = 0;

            System.out.println("Q " + x + " " + y);
            System.out.flush();
            gussDistance = distance = Integer.parseInt(br.readLine().trim());
            if (distance == 0) {
                xl = x;
                yl = y;

            } else {
                x = xl = distance;
                y = yl = 0;
                System.out.println("Q " + x + " " + y);
                System.out.flush();
                distance = Integer.parseInt(br.readLine().trim());
                if (distance == 0) {
                    xl = x;
                    yl = y;
                } else {
                    aux = distance / 2;
                    if (distance % 2 != 0) {
                        aux++;
                    }
                    x = gussDistance - aux;
                    y = aux;
                    System.out.println("Q " + x + " " + y);
                    System.out.flush();
                    distance = Integer.parseInt(br.readLine().trim());
                    if (distance == 0) {
                        xl = x;
                        yl = y;
                    } else {
                        yl = y + distance;
                        xl = x - distance;
                    }
                }
            }
            x = xu = xl + 1;
            y = yu = yl;
            System.out.println("Q " + x + " " + y);
            distance = Integer.parseInt(br.readLine().trim());
            // for point check
            if (distance > 0) {
                // next x is out of box
                x = xu = xl;
                y = yu = yl + 1;
                System.out.println("Q " + x + " " + y);
                System.out.flush();
                distance = Integer.parseInt(br.readLine().trim());
                if (distance > 0) {
                    // next y is out of box
                    System.out.println("A " + xl + " " + yl + " " + xl + " " + yl);
                    System.out.flush();
                    wa = Integer.parseInt(br.readLine().trim());
                    if (wa < 0) {
                        break;
                    }
                    continue;
                } else {
                    // next y is in side box
                    delta = 1000000000;
                    rp = delta;
                    System.out.println("Q " + xl + " " + rp);
                    distance = Integer.parseInt(br.readLine().trim());
                    yu = rp - distance;
                    System.out.println("A " + xl + " " + yl + " " + xl + " " + yu);
                    System.out.flush();
                    wa = Integer.parseInt(br.readLine().trim());
                    if (wa < 0) {
                        break;
                    }
                    continue;
                }
            }
            // for line check
            if (distance == 0) {
                // next x is in side box
                x = xu = xl;
                y = yu = yl + 1;
                System.out.println("Q " + x + " " + y);
                System.out.flush();
                distance = Integer.parseInt(br.readLine().trim());
                if (distance > 0) {
                    // next y is out of box
                    delta = 1000000000;
                    rp = delta;

                    System.out.println("Q " + rp + " " + yl);
                    System.out.flush();
                    distance = Integer.parseInt(br.readLine().trim());
                    xu = rp - distance;
                    System.out.println("A " + xl + " " + yl + " " + xu + " " + yl);
                    System.out.flush();
                    wa = Integer.parseInt(br.readLine().trim());
                    if (wa < 0) {
                        break;
                    }
                    continue;
                }

            }

            delta = 1000000000;
            rp = delta;

            System.out.println("Q " + rp + " " + yl);
            System.out.flush();
            distance = Integer.parseInt(br.readLine().trim());
            xu = rp - distance;

            rp = delta;
            System.out.println("Q " + xl + " " + rp);
            System.out.flush();
            distance = Integer.parseInt(br.readLine().trim());
            yu = rp - distance;

            System.out.println("A " + xl + " " + yl + " " + xu + " " + yu);
            System.out.flush();
            wa = Integer.parseInt(br.readLine().trim());
            if (wa < 0) {
                break;
            }
        }
    } catch (NumberFormatException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
}

}

============================================================================

link

answered 22 Feb, 16:59

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

edited 22 Feb, 22:41

Please tend to share the submission link instead of entire code if the code is long.

(22 Feb, 18:54) vijju123 ♦♦5★
link

answered 22 Feb, 22:41

jawa2code's gravatar image

3★jawa2code
24127
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:

×2,657
×264
×189
×31
×17
×9

question asked: 14 Feb, 00:10

question was seen: 1,218 times

last updated: 22 Feb, 22:41