Internet Problem Solving Contest

• Correct output – C1
• Correct output – C2
• C code that solves both data sets

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 b₀, b₁, ..., b_k-2
such that b₀ should be moved to the free location 0, b_i+1 should be moved where the box b_i is (for i=0, 1, 2, ..., k-3) and the box b_k 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 b₀ to place 0, then move b₁ where b₀ 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 b₀, b₁, ..., b_k-1 such that b₀ should be moved where b_k-1 is and b_i+1 should be moved where the box b_i 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 b₀ to the free location, then rearrange the other boxes in similar way as in the previous case and finally move b₀ 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 v_i=(c_i 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.)