We decided to hold a mirror contest of yesterday's finals because there were several requests.

- Contest Link: https://atcoder.jp/contests/wtf19-open
- Start time: February 23rd (Sat), 23:00 JST
- Duration: 4 hours

This contest is unrated, but we want to keep it as fair as possible. Please do not participate in case you already know the problems (e.g., participants of Beijing camp), and do not discuss solutions with others during the contest.

This contest is recommended for reds and very ambitious oranges.

Link to standings of the official contest.

nutellas and very ambitious reds

i dont think anyone will able to solve more than 1 in a fair contest . even may end up at 0.

i m talking of high rated red coders , leave others .

Reminder, starts in 3 minutes

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

Verifying the first sample is the main part of this problem, so you are very close.

Actually I did this in a bit different manner than in editorial. I got the interpretation with permutations, but didn't think about one with drawing from [0, 1] so my left and right parts weren't independent. Among others, I needed to calculate a weird sum which turned out to be which was exactly what I wanted for first sample, but that didn't lead me to easy generalization to arbitrary patterns. I spend a lot more time on this problem than just verifying first sample and didn't even figure out how to compute appropriate sums for "one-sided patterns" (which show up when pattern contains two consecutive dashes) and computing them for the hardest testcases (which turn out to be just alternately X and -) seemed even much more complicated, so I wouldn't call that very close :P.

However I really like this problem, I love challenging probability/EV problems.

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 theparityof 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 oftogglesto 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 pickM= 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 findanyintegerRbelonging 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) andx≥ 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,ninvocations 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 largep(p= 32 should suffice). Generate a sequence of random elements of the field: (r_{0},r_{1},r_{2}, ...). Now, each lamp , is assigned the value .`xor`

of the numbers translates to addition inGF(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 patternif 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 getCrucially 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 requiresO(n) bitset operations on bitsets of length 2^{k}+ 1, and lets us determine . Taking lcm of 2^{k}- 1 fromk= 2 tok= 13 gives 3.7e18, which is greater than 2e17+1, so if we consider this range ofk's, then we can determineYusing CRT. Then we can determineXin the same way, or using the solution to C1. This solution usesO(n) operations on bitsets of length 8193, and turns out to be pretty fast.