How to efficiently map to original indices of an array after modification?

User 13068788

This is a simplified version of the problem.

We have an array of numbers (between 0 and X-1), at each round, we choose a range of numbers that we compare and only promote the biggest one and eliminate the rest. At each round, we need to output the *original* indices of the numbers that have been eliminated.

This is best explained using an example:

Here is the input:

8 // X represents the size of the array, 2 ≤ X ≤ 100000
4 // Y represents the number of elimination rounds 1 ≤ Y ≤ X−1
1 0 3 6 2 4 7 5 // the numbers
1 3
2 4
1 3
0 1

Output: 4 lines, the original index of the losers at each round

Here is a diagram of how the output was obtained, `[]` means the numbers inside the brackets are the ones being compared.

1 \[0 3 6\] 2 4 7 5 // output 1 2 because 0 and 3 were eliminated
1 6 \[2 4 7\] 5 // output 4 5 because 4 and 2 were eliminated
1 \[6 7 5\] // output 3 7 because 7 and 5 were eliminated
\[1 7\] // output 0 because 1 was eliminated
7

The basic idea is that we want to output the original indices of the number eliminated at each round.

**Approach:**

Model each number as a pair, with the second entry representing the original index. So we have the following:

(1,0) \[(0,1) (3,2) (6,3)\] (2,4) (4,5) (7,6) (5,7) // 1 2
(1,0) (6,3) \[(2,4) (4,5) (7,6)\] (5,7) // 4 5
(1,0) \[(6,3) (7,6) (5,7)\] // 3 7
\[(1,0) (7,6)\] // 0
\[7,6\]

Is this a promising approach? What is the best way to complement it efficiently?

Is there a better, more efficient approach that is easier to implement?

Victor Nijegorodov

Is it a homework? What is your variant of the solution? What does not work in your solution?