Indian Computing Olympiad

Generating permutations→Beads (APIO 2008)

Professor X has recently revealed his latest invention to the world: the Ultimate Bead Swapper (UBS). As the name implies, it can make a sequence of beads much more interesting by swapping some beads in it! The UBS has N conveyor belts placed in north-south direction in parallel. The conveyor belts are numbered 1 to N from left to right. Every belt moves from north to south at the same speed. There are M swappers placed between adjacent conveyors. No two swappers are equally far from the north end of the UBS. (In other words, they can be totally ordered according to how far they are from the north end.) The swappers are numbered 1 to M from north to south. The figure shows the UBS when viewed from above.

       Belt1   Belt2   Belt3   Belt4   Belt5
         |       |       |       |       |
         |       <-Swap1->       |       |
         |       |       |       <-Swap2->
         <-Swap3->       |       |       |
         |       |       <-Swap4->       |
         |       |       <-Swap5->       |
         |       |       |       |       |
      

To use the UBS, N beads are placed at the north end of the conveyor belts at the same time so that they form a horizontal row as they move along the belt. When two beads come under a swapper, the bead on the right conveyor belt is moved to the left conveyor belt, and the bead on the left conveyor belt is moved to the right conveyor. After being swapped, the two beads do not break the horizontal row.

Your task is to write a program that, given the number of conveyor belts N , the number of swappers M , and the positions of each swapper, answer Q questions of the form:

Given K and J , for the bead that is placed on Belt K at the north end of the UBS, which belt is the bead on after all beads just move past Swapper J ?

Limits: 1≤N, M, Q≤300,000

The naive solution is to simulate (execute) the first J swaps for each query. This takes time O(NQ) which is not acceptable.

First option:

A sequence of swaps defines a permutation. Store the permutations for selected sequences. For each swapper i, maintain the permutation corresponding to intervals of 1, 2, 4, ... , 2^k starting at i.

Even better, break up 1..N into blocks of size 1,2,4,8... and maintain the permutations for these blocks.

   	                        N
   	<------------------------------------------------>
   	         N/2                       N/2
   	<-----------------------><----------------------->
   	    N/4         N/4          N/4         N/4
   	<----------><-----------><----------><----------->
   	.
   	.
   	.
   	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
   	<><><><><><><><><><><><><><><><><><><><><><><><><>
      

Now, given J, we can tile the interval 1..J using log J such blocks and compose the corresponding functions to get the overall permutation. This takes O (Q log N) time to answer Q queries.

However, there are 2M such blocks. If we naively maintain a full permutation per block it takes O(MN) space which is too much.

Instead, for each permutation we only keep track of the elements that move in a sorted list. Having got a permutation, it now takes log N time to determine where i moves in this permutation. The good news is that the space requirement overall reduces to M log M.

Second option:

We maintain a table with rows of the form

       Bead      Move     New belt
      

Each row in this table says "At step j, bead i is swapped and moves to belt k". Each swap moves 2 elements, so across N swaps we have only 2N moves. Therefore, this table has only 2N entries. If we maintain the moves in sorted order, we can then answer a query of the form "Where is bead i after step j?" by doing a binary search among the moves of bead i in the table.

To maintain this table, use vectors.

---