The Tesla Model E - Space X's newest Mars Rover - has just landed on the Red Planet, in a crater near the base of Mount Olympus. Its goal is to locate the base of the mountain.
The surface of the planet is seen as a square grid of dimension N, each cell having associated some altitude. The base of the mountain is the only cell that has altitude 0 (it is guaranteed that exactly one such cell exists). The Model E has the capacity to scan the altitude of the Martian landscape at any coordinates (i, j), 0 ≤ i, j < N. Moreover, the grid ascends on both axes: Ai,j < Ai+1,j and Ai,j < Ai,j+1, ∀ i, j ≥ 0.
However, each scan drains a lot of energy, so the total number of scanned cells should be as small as possible. You decide where to make the scans.
Interaction
Your solution will be verified by a simulator. The two programs interact as follows:
Your programs begins by printing two integers X Y. The verifier will respond with the altitude of cell (X, Y). If this altitude is 0, your program can halt. Otherwise, it should repeat the process, trying another cell. In case of invalid coordinates, you will receive an Invalid Query verdict.
Note: After each command you should print a newline character and immediately flush the output, using functions such as fflush(stdout) or cout.flush().
Score
Your solution is considered correct if it manages to correctly identify the cell with an altitude of 0, under the time constraint. In this case, your score for a certain testcase will be computed with the following formula:
Your final score will be equal to the sum of scores for each testcase. If your solution does not find the answer (or gets a TLE verdict), your score for that testcase will be 0. However, it will not affect other cases.
Note: the maximum score for pretests is 30.
Constraints
- N = 200 for all tests.
Example interaction
| User program | Verifier | Grid |
|---|---|---|
| 0 0 | ||
| -5 | -5 ? ? ? . . . ? ? ? ? ? . . . ? ? ? ? ? . . . ? ? ? ? ? . . . ? . . . . . . . . . . . . . . . ? ? ? ? ? | |
| 0 1 | ||
| -3 | -5 -3 ? ? . . . ? ? ? ? ? . . . ? ? ? ? ? . . . ? ? ? ? ? . . . ? . . . . . . . . . . . . . . . ? ? ? ? ? | |
| 1 0 | ||
| -1 | -5 -3 ? ? . . . ? -1 ? ? ? . . . ? ? ? ? ? . . . ? ? ? ? ? . . . ? . . . . . . . . . . . . . . . ? ? ? ? ? | |
| 2 1 | ||
| 8 | -5 -3 ? ? . . . ? -1 ? ? ? . . . ? ? 8 ? ? . . . ? ? ? ? ? . . . ? . . . . . . . . . . . . . . . ? ? ? ? ? | |
| 1 2 | ||
| 1 | -5 -3 ? ? . . . ? -1 ? 1 ? . . . ? ? 8 ? ? . . . ? ? ? ? ? . . . ? . . . . . . . . . . . . . . . ? ? ? ? ? | |
| 1 1 | ||
| 0 | -5 -3 ? ? . . . ? -1 0 1 ? . . . ? ? 8 ? ? . . . ? ? ? ? ? . . . ? . . . . . . . . . . . . . . . ? ? ? ? ? | |
| *stops execution* |
Solution #1
The obvious approach would be to query the whole matrix, which has a complexity of O(N2). This idea obtains a null score.
1 #!/usr/bin/python2.7 2 import sys 3 4 n = 200 5 for i in range(n): 6 for j in range(n): 7 print "%i %i" % (i, j) 8 sys.stdout.flush() 9 10 if input() == 0: 11 exit(0)
Solution #2
A better approach is to apply a binary search on each line (or column), which has a complexity of O(N * log N). This idea obtains ~40% of the maximum score.
1 #include <iostream> 2 using namespace std; 3 4 const int n = 200; 5 6 int main() { 7 for(int i=0; i<n; i++) { 8 int lo = -1; 9 int hi = n; 10 11 while(hi - lo > 1) { 12 int mid = (hi + lo) / 2; 13 14 cout<<i<<" "<<mid<<"\n"; 15 cout.flush(); 16 17 int val; 18 cin>>val; 19 20 if(val > 0) 21 hi = mid; 22 if(val < 0) 23 lo = mid; 24 if(val == 0) 25 return 0; 26 } 27 } 28 }
Solution #3
We can solve this problem in linear time (with approximately 2*n queries) by noticing that we can start from the upper right corner of the matrix and moving one step at a time to neighbouring cells, as such:
- if the value in the current cell is 0, stop execution.
- if it is bigger, go to the left.
- if it is smaller, go down.
This solution obtains 80~90% of the maximum score and can be implemented easily:
1 #!/usr/bin/python3 2 import sys 3 4 i, j = 0, 199 5 while True: 6 print("%i %i" % (i, j)) 7 sys.stdout.flush() 8 9 x = input() 10 11 if x == '0': 12 exit(0) 13 elif '-' in x: 14 i += 1 15 else: 16 j -= 1
Solution #4
The official solution uses a divide et impera approach to find the answer. Assume that the hill looks like this:
We start by taking the middle row of the matrix, and applying a binary search on that row. Once we find the element which is closest to 0, the whole matrix can be split into 4 smaller matrices, like this:
We then apply the same algorithm recursively to the highlighted parts, until we find the element 0.
This solution's complexity is more difficult to compute. In practice, it behaves better than the linear solution. Depending on the implementation, it should obtain the maximum score.
