 MANRECT - EDITORIAL

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

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

Click to view
Answer to query $(0,0)$ is $x1+y1$. While binary searching on $x1$, We can see, that answer for query $(x, 0)$ shall be $x1+y1-x$ if $x < x1$. This provides us condition for binary search. Similar condition can be derived for $x2$ and hence, is left as an exercize.


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.

Click to view
Minimum Manhattan Distance from Point $P(x, y)$ to rectangle $(x1,y1,x2,y2)$
- if $x < x1$ and $y < y1$: $x1-x+y1-y$
- if $x < x1$ and $y1 \leq y \leq y2$: $x1-x$
- if $x < x1$ and $y > y2$: $x1-x+y-y2$
- if $x1 \leq x \leq x2$ and $y < y1$: $y1-y$
- if $x1 \leq x \leq x2$ and $y1 \leq y \leq y2$: $0$
- if $x1 \leq x \leq x2$ and $y > y2$: $y-y2$
- if $x > x2$ and $y < y1$: $x-x2+y1-y$
- if $x > x2$ and $y1 \leq y \leq y2$: $x-x2$
- if $x > x2$ and $y > y2$: $x-x2+y-y2$


Time Complexity

Time complexity is O(1) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. 2 Likes

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

Only 4 equations are necessary for finding out the secret rectangle

here’s my handwritten proof

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

import java.io.IOException;

public class Main {

public static void main(String[] args) {
try {
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();
if (distance == 0) {
xl = x;
yl = y;

} else {
x = xl = distance;
y = yl = 0;
System.out.println("Q " + x + " " + y);
System.out.flush();
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();
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);
// 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();
if (distance > 0) {
// next y is out of box
System.out.println("A " + xl + " " + yl + " " + xl + " " + yl);
System.out.flush();
if (wa < 0) {
break;
}
continue;
} else {
// next y is in side box
delta = 1000000000;
rp = delta;
System.out.println("Q " + xl + " " + rp);
yu = rp - distance;
System.out.println("A " + xl + " " + yl + " " + xl + " " + yu);
System.out.flush();
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();
if (distance > 0) {
// next y is out of box
delta = 1000000000;
rp = delta;

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

}

delta = 1000000000;
rp = delta;

System.out.println("Q " + rp + " " + yl);
System.out.flush();
xu = rp - distance;

rp = delta;
System.out.println("Q " + xl + " " + rp);
System.out.flush();
yu = rp - distance;

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


}

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

Solutions’ links not working, as usual.

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

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

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