looks like a nice contest :) looking forward for it

My solution used 1001 queries and get 99 points.

I asked (i, i) with i from 1 to 1000, then save the result in res_i. Now, a cell (x, y) may contain the treasure if both res_x and res_y is true. So just iterate over all par (x, y) that both res_x and res_y is true, and check if the data from res array is correct if the treasure was there. If it is correct, then ask another query to check if the actual location is (x, y) or (y, x).

The number of cells we have to check will be small, so this solution will run fast.

My implementation

Still wonder how to improve this (althought if I was in the official contest, focusing on other problem is definitely a wiser choice xD). I thought about not querying (1, 1) and (1000, 1000), but then I can't distinguist between (1, 2) and (5, 2).

you can determine X and Y simulanteneously by querying (i,i) for all i. if for a point, you TRUE, check for the possibility that the answer is (i,x) for some x by querying the point (i,i+1). and the possibility that the answer is (x,i) similarly. Note that the number of times the second query returns false is quite rare. This approach will get 98 points. using random_shuffle and getting lucky will get 100 points :)

My approach is the following one. Ask 999 queries of the following type (a_i, b_i) where (a₁, ..., a₁₀₀₀) and (b₁, ...., b₁₀₀₀) are random permutations of {1, 2, ..., 1000}. There will be just one possible cell that is consistent with all the answers (at least with a sufficiently high probability).

The reason why such a solution works is, at least for me, quite hard to justify completely. Let me describe some facts that, heuristically, show that no more than one cell will be consistent with all queries. I am quite sure that it is even possible to choose a-priori 999 queries that identify any cell (such a choice might be the queries (1,1), (2,2), .... (999, 999) or something like that).

Fact 1: The answer to two queries that differ both on the row and the column is "almost independent" (in the sense of probability).

Fact 2: For a single query whose answer is yes, the number of cells that are consistent with the query is O(1000) (the row, the column and some more cells given by pythagorean triples).

Fact 3: With high probability there are at least two queries whose answer is true.

Hence, considering only the queries whose answer is true, we can restrict ourselves to a very small number of possible cells. Then, considering all the queries whose answer is false, we will be able to decide which one is the correct one.

The solution is naturally divided in two steps:

1. Compute the number of occurrences of every remainder mod 100 in the table.
2. Deduce the answer.

The first step can be done in O(100²) exploiting the periodicity of the table both in the rows and in the columns.

Let us denote with c[r] the number of occurrences of the remainder r in the table. In the second step we have to compute the sum of all the coefficients of terms whose degree  ≡ 13 (mod 100) of the polynomial

This can be done performing all polynomial computations modulo x¹⁰⁰ - 1 that means that whenever an exponent is above 100 we do take its remainder mod 100. The result can thus be obtained through fast exponentiation (the answer will be the coefficient of x¹³). The complexity of the second step is .

Very soon. I am compiling the result (from both windows) right now :)

Original blog post updated with the URL for the (preliminary) day 1 result :)

First off we can do a transformation of a point (x, y) to a point (x + y, x - y). Now the distance between 2 such points A, B is max(|A_x - B_x|, |A_y - B_y|) (this is a well known transformation so I saw it coming right when the statement provided the manhattan distance).

From this point you can initially sort by x coordinate all the points, and then you can binary search on the answer, for a total time of (If you want I can elaborate on the binary search, but it shouldn't be hard).

First, convert point (x,y) to (x+y,x-y). Now the distance will be max(abs(x1-y1), abs(x2-y2)).

Binary search the result, call it X. Let P be the point with minimum x. A set which contains P would be a X-by-X square with P on the lower boundary. Sweep the square along y-axis, maintain the largest distance among points not in the square. I did it by set and got TLE, had to switch to vector of prefix min/max.

As the name suggests, compile_cpp only compiles the source code. To execute the program you should run ./name_of_problem < sample1.in (and you don't need to modify the grader).

Unfortunately you can't submit the problems now. However, you will be able to submit the problems once TOKI Open 2018 is over (i.e. after the second day)

Where could we find the official editorials to the problems?

If anyone's interested, or hasn't already made this deduction, here's a sketch of a proof that you can divide the board up into two-row 'states'.

O   T1  T2  J1  J2  L1  L2  S   Z

..  #.  .#  ##  .#  #.  .#  #.  .#
##  ##  ##  #.  .#  #.  .#  ##  ##
##  #.  .#  #.  ##  ##  ##  .#  #.

O'  T1' T2' S'  Z'

..  #.  .#  #.  .#
..  #.  .#  .#  #.

O -> O'
T1, J1, L1 -> T1'
T2, J2, L2 -> T2'
S -> S'
Z -> Z'

T2' + J1, T1' + J2 -> O'
Z' + J1, Z' + T1, T1' + S -> T1'
S' + L2, S' + T2, T2' + Z -> T2'
T2' + T1, S' + S -> S'
T1' + T2, Z' + Z -> Z'

#.    ..
##    ..
#.    #.
.. -> #.
#.    #.
.#    .#

The idea works fine — you can store the highest two rows and process any changes from new blocks as they come. It seems like your solution just has too high of a constant factor.

One major optimisation to your DP is to always have state y be the empty state (so always consider only cases where the playing field is empty after the insertion of block R). The reason we can do this is that we want to end up with an empty state to solve the overall problem, and state transitions still work out fine.

In particular, our DP state is now dp[i][j][x], and our transitions now become:

• If i == j, we check if adding this block leaves us with the empty state, in which case by definition our DP value is true.
• In the case where we end up removing the top 2 rows with our new block, we simply ignore this, and consider dp[i+1][j][empty state]
• In the case where we simply change the top 2 rows, we consider dp[i+1][j][changed state]
• In the case where we end up adding another 2 rows on top of the top 2 rows, we consider every possible index k (i < k < j) where the 'higher level' could finish, resulting in an empty state on the rows above us, and thus returning back here to this state for more blocks to be added. This case is handled by checking, for every valid k, whether or not both dp[i+1][k][state of new top 2 rows after adding block] and dp[k+1][j][state of old top 2 rows] are true, and if so then we would be able to add a new set of 2 rows above here, and they would eventually get removed after the addition of the k-th block, by the assumption that dp[i][j][x] is true if and only if we can end up with an empty state after adding block j.

Our answer is then dp[0][n-1][empty state], similarly to your solution. (Technically we have to keep track of some extra stuff to actually solve the problem, since we need to output the rotations, but those are implementation details.)

My approach is DP(L, R, state) which returns true if we play these tetrominoes independently and result in an empty slot or a slot with 2 rows; got accepted sub 4.