The idea is very similar to that of Google CodeJam 3. The number of mismatches is indeed a lower bound, but you need to find minimum number of cycles to which you can decompose the swaps, and you can do that by union find. I wasted an hour by failing to understand how exactly is the N-th value (xor of all A values) play a role.

Sometimes you need more moves. For example '4 1 2 5 6 2 1 6 5' needs 6 moves. Analyze why and you will find how to get the minimum number of moves.

This was what I found in the contest :

Reduce the problem to finding the minimum number of moves needed to turn an array a into b, where a move is swapping the last element with any other element of the array.

Let the elements of array a be a₀, a₁, ..., a_n (a_n is equal to the xor of a₀ to a_n - 1) and the elements of array b be b₀, b₁, ..., b_n.

Add an undirected edge from a_i to b_i for all i. Let x be the number of mismatches in the array a and b (not counting a_n and b_n). For each component that does not contain a_n and b_n and has size  ≥ 2, add 1 to the x. The answer is x.

Realize that the array has to be such that the difference between maximum and minimum values of the array is at most 1.

Now there are two cases, either all the values of the array are same. That is only possible if all people have distinct color hats, or nobody has a distinct color hat.

In the other case (when the difference is 1), let's assume the values are x and x+1, then all the people with value x must have a distinct color hat (i.e. each such person must have a color that no other person has). And for all the people with x+1, they should have a hat such that there is at least one other person, with value x + 1, that has the same color hat. Using this logic you will get an inequality. Code

Just curious, are you using a special extension/another website? (The interface is different)

Omg, I have never thought about nimbers that way, that's clever

I had the same situation with the following bug: when a certain layer contains one of (1,2), we're certain that we have achieved what we need, so I added 1 to the number of ways. But we need to add 2 to the power of the number of edges connecting yet unassigned vertices.

I had 883, when forgot, that you can have any edges to vertices of higher layers. Didn't you do the same?

Could you tell the link to your submissions?

You can partition the board into h × w disjoint rectangles. Each small rectangle has negative sum, so the total sum cannot be positive.

Divide the entire board into H/h * W/w submatrices. Sum of each such submatrix must be negative whereas the whole some must be positive, so you get a contradiction. For example, if W=H=4 and w=h=2, you have:

a[1][1] + a[1][2] + a[2][1] + a[2][2] < 0
a[1][3] + a[2][3] + a[1][4] + a[2][4] < 0
a[3][1] + a[4][1] + a[3][2] + a[4][2] < 0
a[3][3] + a[4][4] + a[3][4] + a[4][3] < 0
-------------------------------------
add them all and you get sum of all the elements in the matrix is negative and it should be positive

I had O(Bell(n - 2)·n) and it passed easily in 2 seconds out of 5. Increasing n by 2 would disallow my solution, but this would imply setting TL to 10-15 seconds, which is not too great.

EDIT: to be exact, my solution is O(Bell(n - 1)).

Our bell solution took more than 20s, and we didn't want to make the constraints too tight for O(3^n * n) solution. But yes, we should have used bigger n.

The TL was pretty loose IMO. My solution takes less than 200 ms and can be optimised further. It's O(N·3^N), but treats vertices 1 and 2 as special, which improves the constant.

Pink.

White :|

Btw could you explain why some users have not really expected color? Like semiexp or Um_nik

And my suggestion for new color is rainbow xD

As for dan, maybe "Alpha Go"?

By the way, how does "kyu" system work? I checked that rating 1 corresponds to 20 kyu, 2 corresponds to 19 kyu, and 4 corresponds to 18 kyu.

I'm sure margin of "kyu" is different from "dan", but I don't know exactly how the system works.

You can scale the displayed rating in a fashion similar to ratings <400 to introduce an upper cap. I hope tourist would not object if he converged to 4400.

I have an idea about Dan:

3800-3999: 10 dan
4000-4199: Legend
4200-4399: Winner
4400-4599: God

By the way, the maximum performance in entire AtCoder history is about 4500, so rating won't be exceed 4600.

Works on CSAcademy too.

But what if he makes a mistake and one of the tasks is incorrect? Oh ... right ...

Reduce the problem to finding the minimum number of moves needed to turn an array a into b, where a move is swapping the last element with any other element of the array (if you have trouble here, see the current editorial)

Let the elements of array a be a₀, a₁, ..., a_n (a_n is equal to the xor of a₀ to a_n - 1) and the elements of array b be b₀, b₁, ..., b_n.

Do coordinate compression on these numbers and suppose there are v distinct numbers. Construct a graph on v vertices with the following method :

Add an undirected edge from a_i to b_i for all 0 ≤ i ≤ n with a_i ≠ b_i. (We allow multiedges here)

Each edge of this graph describes a mismatched pair. Note that each vertex has even degree, as if x appears k times in a, then it must appear k times in b. Thus, each component has an Eulerian cycle.

Now, we can use these Eulerian cycles to construct the optimal solution. For the component containing a_n, we can perform the swaps according to the Eulerian cycle and use e - 1 swaps to accomplish the goal (where e is the number of edges in that component). After that, the last element will be b_n and if the component containing b_n is still unresolved, we can use e moves to resolve it, where e is the number of edges in that component. For every other component that does not contain a_n or b_n, we require e + 1 moves to resolve that component. This summarizes to :

Let x be the number of mismatches in the array a and b (not counting a_n and b_n). For each component that does not contain a_n and b_n and has at least one edge, add 1 to the x. The answer is x.

yes, uploaded.

Internal Error. Fixed now.