Solution of Model E

Solution #1

The obvious approach would be to query the whole matrix, which has a complexity of O(N²). 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.