# Internet Problem Solving Contest

## Solution to Problem C – Crane Operator

What we want to do is to create a given permutation of the boxes. A permutation can be decomposed into disjoint cycles. In our case there are three types of cycles:

• A fixed point – a cycle of length one. This is a box that is already on its place. Clearly in the best solution the crane doesn't need to move a box which is a fixed point.
• A non-trivial cycle (of length k) containing the free location. It is a sequence of boxes b0, b1, ..., bk-2
• such that b0 should be moved to the free location 0, bi+1 should be moved where the box bi is (for i=0, 1, 2, ..., k-3) and the box bk is currently on the location that should be free at the end. Each box in this cycle must be moved at least once because it is not on its final position. But it suffices to move each block exactly once. Simply move b0 to place 0, then move b1 where b0 was, etc. So k-1 moves are necessary and sufficient in this case.
• A non-trivial cycle (of length k) not containing the free location. It is a sequence of boxes b0, b1, ..., bk-1 such that b0 should be moved where bk-1 is and bi+1 should be moved where the box bi is (for i=0, 1, 2, ..., k-2). Again, each of these boxes must be moved as least once, but to move all of them to their final positions at least one of them has to be moved out of the cycle first. This number of moves is already sufficient: First move b0 to the free location, then rearrange the other boxes in similar way as in the previous case and finally move b0 to the currently free location (its final position). So k+1 moves are necessary and sufficient in this case.

This all means that the number of moves necessary and sufficient to reach the final configuration is N-(number of fixed points)+(number of non-trivial cycles)-(2 if there is a non-trivial cycle with the free location).

The only problem remaining is to find the final positions of the blocks. It can be done by simulating the described procedure. We need some data structure to find the numbers x and y efficiently. Let g=gcd(N,d). Observe that all numbers of the form (C+d*x+y) mod N for fixed y are in the same remainder class modulo g. So for each number j=0, 1, ..., g-1 we will count number of blocks alread placed on positions with reaminder j (modulo g). When i-th block is processed, we compute the value vi=(ci mod N) mod g and look if there is a fee place in this remainder class. If there is we take y=0, else we look for next free remainder class and determine y. When we have y we can find the next free x.

So we need a data structure where we can store k items arranged into the cycle where each can be marked (as occupied) or unmarked. We need to support the following operations:

1. Mark a given item
2. For given item find first next unmarked item.
We will have one such data structure to determine y and for each remainder class modulo g one to determine x.

This can be implemented by the Union-FindSet algorithm. By this algorithm we will maintain the (maximal) connected segments of marked elements. To determine the next free unmarked item we perform a FIND operation to find the segment containing gived item and return the item following that segment. To mark an item we look if it does not connect some segments. If it does, we perform a UNION operation to join them.

This algorithm has linear space complexity and O(N*log*(N)) time complexity if the Union-FindSet algorithm is implemented with path compression and balancing. (Path compression was sufficient to have a fast program.)