Indian Computing Olympiad

Generating permutations→Depot (IOI 2001)

A storage depot consists of a 2 dimensional array of slots. Each object to be stored in the depot has a unique serial number. When an object with sequence number K arrives, it is stored according to the following pair of rules.

1. If K is bigger than the sequence numbers in row 1, add K at the end of row 1.
2. Otherwise, find the smallest sequence number bigger than K in row 1, say L. Replace object L by K and insert L into row 2 using the same pair of rules.

Problem: Given the final configuration of a depot, construct all input sequences that could have given rise to the depot.

Assume that the values in the depot are 1..N. In general, the number of compatible input configurations is exponential in N.

A naive solution would be to enumerate all permutations of 1..N, apply the depot rules and see if the resulting depot matches the one given. This is possible within the time limits for N upto 7, possibly 8.

For larger inputs (upto 13), use a recursive procedure to work backwards from the final depot. Notice that at each stage of constructing a depot, the last element to move settles down at the end of a row. It should also be a "corner" element---that is, the row below should be strictly shorter in length.

Thus, for a given depot, for each row we look at the last element and, if it is a corner, "undo" the sequence of moves that brought it there, thus generating a possible last element of the input sequence together with the previous configuration of the depot. We recursively explore all these previous configurations. When the depot becomes empty, we would have built up a possible input sequence.

Example:

       Input sequence :  3 2 6 4 1 5

       Step  :   1            2          3        4      5      6

       Residual
       Input:    2 6 4 1 5    6 4 1 5    4 1 5    1 5    5      Empty

       Depot:    3            2          2 6      2 4    1 4    1 4 5
                              3          3        3 6    2 6    2 6
                                                                3
      

Corner elements are {3,6,5}. Suppose we undo the 3. The 3 displaces the 2 in the previous row (largest element in that row smaller than 3), which in turn displaces the 1 in the first row. This leaves us with

            2 4 5         Partial input sequence:  1
            3 6

       Corner elements are {6,5}.  If we undo the 6, we get

            2 4 6         Partial input sequence:  5 1
            3

       Corner elements are {3,6}.  Undoing 6 again, we get

            2 4           Partial input sequence:  6 5 1
            3

       Corner elements are {3,4}.  Undoing 3, we get

            3 4           Partial input sequence:  2 6 5 1
      

Now we have to undo 4, then 3, yielding a candidate input sequence 3 4 2 6 5 1. Verify that this does indeed generate the same depot.

       Input sequence :  3 4 2 6 5 1

       Resulting depot:

       Step  :   1            2          3        4       5        6

       Residual
       Input:    4 2 6 5 1    2 6 5 1    6 5 1    5 1     1        Empty

       Depot:    3            3 4        2 4      2 4 6   2 4 5    1 4 5
                                         3        3       3 6      2 6
                                                                   3
      

An aside:

Suppose, while constructing a depot, we also keep track of the order in which the squares are filled, which yields a second "depot" with the same shape.

       Input sequence :  3 4 2 6 5 1

       Resulting depot:

       Step  :   1            2          3        4       5        6

       Residual
       Input:    4 2 6 5 1    2 6 5 1    6 5 1    5 1     1        Empty

       Depot1:   3            3 4        2 4      2 4 6   2 4 5    1 4 5
                                         3        3       3 6      2 6
                                                                   3

       Depot2:   1            1 2        1 2      1 2 4   1 2 4    1 2 4
                                         3        3       3 5      3 5
                                                                   6
      

Since the second depot tells us the order in which the depot was filled, we know in which order we should undo the moves, which deterministically gets us the input sequence that generated this pair of depots.

It turns out that each permutation generates a unique pair of depots and vice versa, so the set of permutations of 1..n is in 1-1 correspondence with the set of pairs of valid depots of the same shape over 1..n.

---