Editorial for IOI '07 P1 - Aliens


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We'll use the terms red cells and red squares for cells and squares with flattened grass. The other cells and squares are white. Using the alien device at some coordinates is now equivalent to checking the color of a cell.

The process of finding the solution consists of two stages. The first stage is to determine the side length M of one square of the chessboard and the center (X_C, Y_C) of the red square F containing the given red cell (X_0, Y_0). The second stage is to move from (X_C, Y_C) to the center of the entire crop formation (using shifts of length M or 2M along each coordinate).

The key part of this task is efficiently solving the first stage. In order to find M, we should find:

  • X_R — the rightmost x-coordinate of cells in F,
  • X_L — the leftmost x-coordinate of cells in F, and
  • Y_B — the bottom y-coordinate of cells in F.

We describe several approaches for finding X_R; it is trivial to adapt them for finding X_L and Y_B.

The most obvious algorithm checks the colors of cells (X_0+1, Y_0), (X_0+2, Y_0), (X_0+3, Y_0) etc., stopping at the first white cell (X_R+1, Y_0) and using M queries in the worst case. This approach would score 40 points, as described in the Grading section of the task description.

To cut down on the number of queries, let's instead check the color of cells (X_0+1, Y_0), (X_0+2, Y_0), (X_0+4, Y_0), \dots, (X_0+2^k, Y_0), \dots, stopping at the cell we call C_{last}. This is the first white cell of the sequence or the first cell outside the meadow boundaries (we must be careful not to query the device in the latter case). It can be shown that all red cells left of C_{last} must belong to the square F and not to some other red square. Let C_{previous} be the rightmost red cell left of C_{last}. We have used at most \log_2 M queries so far.

Now we could reset X_0 = C_{previous} and repeat the procedure described in the last paragraph until [C_{previous}, C_{last}] contains only 2 cells, after which C_{previous} = (X_R, Y_0). However, here we have used (\log_2 M)^2 queries in the worst case, which is only good enough to score 70 points.

To get the full score, use binary search on the segment [C_{previous}, C_{last}] to find X_R: (X_R, Y_0) is the only red cell in that segment that has a neighboring white cell to the right. Using this algorithm we can find all of X_R, X_L and Y_B using at most 6 \log_2 M queries total. Now, M = X_R-X_L+1, X_C = X_L+(M-1)/2, Y_C = Y_B+(M-1)/2.

This concludes the description of the first stage. The second stage uses the alien device only a few times to detect which of 13 possible squares has (X_C, Y_C) as the center. Just checking the color of several cells having X_C, X_C \pm M, X_C \pm 2M as x-coordinates and Y_C, Y_C \pm M, Y_C \pm 2M as y-coordinates will do the trick.


Comments

There are no comments at the moment.