The only other contestant to solve the hardest problem, pashka, was actually unable to figure out the proper algorithmic solution in time; so he decided to take his chances and treat the problem as a general hamiltonian cycle problem and solve it with a simple but powerful heuristic, just like I did in 2014. It seems that participating in IOI 2002 has finally paid off for both of us :)
The medium problem was quite nice in this round. After removing some unnecessary complications, the statement boiled down to: you are given a 9x47 grid of zeroes and ones. In one step, you can take any cell that contains a one, and another cell that is either in the same row but to the right or in the same column but to the bottom from the first cell, and flip both of them (so one changes to zero, and zero changes to one). You are given the initial and the final state of the grid, and need to produce any (not necessarily the shortest) sequence of operations that transforms one to the other with at most 947 operations.
Thanks for reading, and check back next week!
Hi, I have a solution. Please try to give it a look.
ReplyDeleteCheck if parity of count of '1' in target matrix is same as that of source matrix.
If it is not, answer is clearly not possible.
Now, let diff = courn1(source) - count1(target)
We need to destroy diff number of '1's from source, if diff is negative. ans is not possible.
Strategy to destroy 1's seems important. A greedy strategy(Destroying right bottom corer 1's could be wrong).
Let's think after some point. We can create a graph from source to target 1's. Edges from source 1's will be to all target 1's which are in bottom right. Just a max bi partite matching would tell us. Now, We will be destroying redundant edges. This can take 9*47/2 = 212 operations in worst case.
Now, In gauss elimination fashion we can move our 1's.
This can take 9*47 = 423 moves.
Total moves = 635 moves.
Looks good modulo small details!
Delete