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
1 2
4 5
3 7
0
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 2
[(1,0),(0,1),(3,2),(6,3),(2,4),(4,5),(7,6),(5,7)]
-----------------
4 5
[(1,0),(6,3),(2,4),(4,5),(7,6),(5,7)]
-----------------
3 7
[(1,0),(6,3),(7,6),(5,7)]
-----------------
0
[(1,0),(7,6)]
-----------
[(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?
Another approach uses a segment tree but I don’t understand how that would work.