Author: | Roman Bilyi |
Vlad Ulmeanu | |
Solved by: | |
First to solve: | FMI-1 |
We denote a move by (i, j), i \neq j. If we perform the same move times, we note it by (i, j)^k. Let pos_t represent the position at which we can find in the permutation. We assume that we update after every move that we do. Property 1: An optimal sequence of moves never contains (i, j > i). A sequence of moves that achieves the same result, while only utilizing the (i, j < i) kind of moves is (j, 1)^{j-i}, (j-1, 1)^{i-1}, but it only requires a cost of j-1 < j. Property 2: (i, j < i) can be replaced by a sequence of moves of the same cost of type : (i, 1), (j, 1)^{j-1}. Following the first two properties, there must exist an optimal sequence of moves only of the type . Property 3: Let 0 \leq t < n s.t. pos_t \nless pos_{t+1} < \ldots < pos_n. If t = 0, the permutation is already sorted. Since pos_t \nless pos_{t+1}, the solution must contain at some time the move (pos_t, 1). Property 4: If the sequence contains a move (pos_t, 1), then it must later contain (pos_{t-1}, 1), (pos_{t-2}, 1), \ldots(pos_{1}, 1) as well, because after (pos_t, 1) will be in front of 1, 2, \ldots t-1. Property 5: If the sequence contains a move (pos_t, 1), then the sequence mustn’t later contain (pos_{z>t}, 1), since and will be correctly ordered, and we can’t break the correct ordering by doing any other moves required by property 4. Using properties 3 and 4, the optimal sequence’s length must be at least , containing (pos_t, 1), (pos_{t-1}, 1), \ldots (pos_1, 1). Using property 5, we shouldn’t use any other moves. There is a sequence of moves whose length is exactly : (pos_t, 1), (pos_{t-1}, 1), \ldots (pos_1, 1) (using properties 4 and 5, we won’t need to redo any moves if we employ this order).
We now have to figure out how to efficiently update . Property 6: When we have to do (pos_{1 \leq z \leq t}, 1), pos_z will be higher than its original value by the number of values z < y \leq t that were originally to the right of . We move them to the first position earlier, therefore each increasing ’s position by one. We need a data structure that supports point updates (i.e. we moved a value from index to the first position) and range sum queries (how many values that were originally after us were moved before us to the front). A Binary Indexed Tree is enough for this. Although we can sort the permutation with a cost of , it’s not easy to find a solution that generates the required moves faster than O(n \log n).