Link to standings of the official contest.

reds and very ambitious oranges

nutellas and very ambitious reds

Reminder, starts in 3 minutes

Nice problem E XD. Took me sth like 1 hour to verify answer to first sample xD.

Can we see the codes submited by finallists?

My solution to C2, unfortunately a couple of times too slow (after some heavy optimizations, I'm now able to pass more than half of the max tests). I hope it's at least a tiny bit understandable:

Let's start with a solution to C1. Assume first that all lamps in the input have y ≥ 0. We use the operations in the statement to achieve the situation where the only lit lamps lie on the OX axis (y = 0). We can observe that each lamp (x, y) toggles all the lamps (x + t, 0) such that (y & t) == t. The input data in C1 asserts that after all such toggling exactly one lit lamp will remain.

Thus we can write a fairly simple blackbox Parity(x, y, R) returning the parity of the number of lamps (t, 0), t ≤ R, that the input lamp (x, y) toggles (it can be done in ). This allows us to compute the parity of the number of toggles to the left of any lamp (t, 0) in time. If this number is even, then the sought result is to the right of (t, 0); if it's odd, the result is to the left of (t, 0). We can binary search the result, and therefore we end up with a solution in time.

However, we still need to consider the lamps with y < 0. To cope with this, let's pick M = 60 and let's move all the lamps up by 2^M units (y' = y + 2^M). C1 then asserts that there exists exactly one lamp that produced the input data. We can however prove that this is equivalent to two lit lamps: at and . Therefore, if we ask for the parity of the number of lamp toggles to the left of any lamp (t, 0), we will get an odd result iff . This is a really wide interval, and it's easy to find any integer R belonging to it. Then we do an analogous binary search in [R - 2^M, R].

C2: we can't really use the parity that easily anymore. However, we still want to assume that all lamps fulfill y ≥ 0 (shift them up if they don't) and x ≥ 0 (shift them right so that it happens). We'll again toggle all the lamps so that the only lit lamps are lying on the OX axis, and we'll find the first lamp and the last lamp turned on after all the operations: (L, 0) and (R, 0). We can easily prove that in such a setup, the original single lamp must've been located at (L, R - L).

We'll generalize the Parity blackbox. We'll assign each lamp (x, 0), x ≥ 0, a "random" p-bit number. Now we want Parity(x, y, R) to return the xor of all the numbers assigned to the lamps , \ell \leq R$, toggled by the input (x, y) lamp. Again, n invocations of such blackbox allow us to compute the xor of all the numbers assigned to the lamps , that are on after all input lamps are processed. Using this, we can easily compute the first and the last turned on lamp using two binary searches.

How to produce sufficiently "random" numbers, though? Let's consider the finite field GF(2^p) for some fairly large p (p = 32 should suffice). Generate a sequence of random elements of the field: (r₀, r₁, r₂, ...). Now, each lamp , is assigned the value . xor of the numbers translates to addition in GF(2^p). I'm omitting a bunch of technical details right now, but it's now possible to implement the Parity blackbox in time. This allows us to implement the solution in time; I believe it's or .

Here is another solution to C2, due to lamejeck. At a glance it seems different from the one described above and the one in the editorial, but I'm not sure how different it really is.

Let's call a subset of the grid (equivalently, an assignmnet of numbers 0, 1 to every grid point) an annihilating pattern if it intersects each triangle {(x, y), (x, y + 1), (x + 1, y)} in an even number of points. (Personally, I think the situation becomes clearer if you think of the lamp configurations as forming a vector space over the field of two elements, where there is one basis vector for each lamp. An annihilating pattern is then a functional that vanishes at every triangle.) Anyway, given an annihilating pattern, we can determine if the point (X, Y) is in it just by counting the parity of the number of given points in the pattern.

The problem is now to find sensible annihilating patterns, that are both easy to compute, and give us useful information about (X, Y). If you fiddle with this, you will find lots of Sierpinski triangles. In particular, suppose we start with a periodic row that looks like ...0000100001..., i.e. 2^k 0's followed by one 1. Filling in the rows above to make it annihilating, we get

...1000110001...
...0111101111...
...0010100101...
...0001100011...
...0000100001...

Crucially the top row is just the second row from the bottom shifted one step to the left. So the rows are periodic with period 2^k - 1, up to shifting. Now we can get rid of the row we started from, and just repeat the period, to get a very nice annihilating pattern. 'Hitting' the given points with this pattern and its left shifts requires O(n) bitset operations on bitsets of length 2^k + 1, and lets us determine . Taking lcm of 2^k - 1 from k = 2 to k = 13 gives 3.7e18, which is greater than 2e17+1, so if we consider this range of k's, then we can determine Y using CRT. Then we can determine X in the same way, or using the solution to C1. This solution uses O(n) operations on bitsets of length 8193, and turns out to be pretty fast.