Перенесли на пораньше. Все успеют.

Really Nice contest...

No, it doesn't. The hacker cup starts 9 hours after this round ends.

Round 1 lasts for 24 hours and time penalties don't matter for advancing to the next round, feel free to participate at whatever time you like -- there's no advantage to doing the problems right at the start of the round.

It's dynamic score, thats mean, the problem most solved will have 500 points, etc.

left differs from right

UPD but it was fun to make 2 WA#1 because of first number in output (count of succesful shuffles)

И задачи шикарные :)

me too!

Sort all the numbers in array a, then reverse them in array b. Then the pairs with the same numbers can form only a single subsegment. Then try to swap some numbers from b in this subsegment with some numbers from b either at the start or the end. One can prove this is optimal.

bipartite matching works, build the graph with color of mittens as the vertex and the number of each mittens as capacity of the vertex from super-source to each color and each color to super-sink, it works in O(m^3) which is enough to pass the time limit.

My idea was to build another array and send it to output with

res[i] + " " + res[ (i+offset)%size ] ; // i = 1..n

where array looks like

1 1 1 2 2 3
for
1 2 2 1 3 1

// (I've just found that I simply need to sort it, xd)

so, "offset" is maximal count of 1..m types (or colors, I don't remember)

and this method gives output

1 2
1 2
1 3
2 1
2 1
3 1

There was a stupid solution: sort left mittens, sort right mittens. shift right mittens cyclically by n/2. P.S. almost the same problem was in one russian contest last year: https://zaoch.olympiads.ru/zaoch/2012-13/final/problems.shtml

Here is a solution that seems intuitive to me: First sort the colors with descending number of occurrences We note that if the majority color is <= size / 2, we can get everything to be distinct by simply shifting the majority color to the guy who is at the start of the second majority color

E.g.

111111222333

222333111111

On the other hand, if the #majority color is > size /2, our best choice is still to do the above assignment, because the number of matches is at least 2*#major — size

Code: http://codeforces.com/contest/370/submission/5369409

Sort all children by colors, and then iteratively check.

At the i-th child, check if it is possible to find someone before with unchanged mittens, then swap one mitten with him/her. If everybody before has got changed mittens, then find someone before with mittens share two differenct color with the i-th child, then swap. If there's nobody satisfying these two conditions, then just wait and see.

i.e. Initial distribution: 1 1 2 3 3

The first two children can only wait: 1 1 2 3 3 1 1

Then 2 can swap with the first one: 1 1 2 3 3 2 1 1

Then 3 insert to the second place to 'save' that child: 1 1 2 3 3 2 3 1 1

The Last one swap with the first one: 1 1 2 3 3 3 3 1 1 2

The end.

Well I thought about implementing it during the contest but I thought that it wouldn't pass, the time limit is so strict (1 second)

-28

My first solution had WA10, because I did not read this sentence, but I fixed this bug :)

http://codeforces.com/blog/entry/9854#comment-153240

and it will fail for,

1 1 1 1 2 2 2 3 3 3

why system doesn't show the tests? and also other's code??

W должны быть не внутри, а строго на границе рамки.