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.

Solution

---