Minimum queries required for MANRECT

general
, ,
1

I just saw a solution using 4 queries. What is the absolute minimum number of queries? Can you prove it?

2

Please provide the link of that soln. :stuck_out_tongue:

3

Yes , 4 queries are enough . 3 at 3 corners of given space 1e9x1e9 , and one at mid-point which can be calculated using the results of these 3 queries.
Link: https://www.codechef.com/viewsolution/22895038

Regarding Proof , we need 4 linearly independent equations atleast to solve for 4 points . So i think minimum no of queries is 4 only.

2 Likes
4

Someone posted it in the discussion. I’m not able to find the post but this is the video: https://www.youtube.com/watch?v=zaC9iJakqy8

1 Like
5

Aah, that was easy :slight_smile: Thanks!

1 Like
6

I solved it using 4 queries.

7

Here is the link for My solution using 4 queries

First Query (0,0)
Answer : Z = X_low + Y_low

Now we can form a line between (Z,0) to (0,Z) and lower left point of the rectangle must lie somewhere in the line

Next Query (10^9,0)
Answer : A = 10^9 - X_high + Y_low
Similarly we get another line between ( 10^9-A,0) to (10^9,A)

Now we will find intersection between those two lines and it is guaranteed that lower side of the line will be perpendicular to the point.

Let’s consider intersection points to be (X_temp,Y_temp) and ask query { To be rounded in case of floating point coordinate }
Answer : B
Y_low = Y_temp + B

Other points can be calculated easily. We need to ask 4th Query (10^9,10^9) for that

8

I too solved using 4 queries only.
Solution

9

soln

6 Likes
10

last equation gives value of b and by using it you can calculate a,c,d

1 Like