How to erase elements more efficiently from a vector or set?

Question

Problem statement:

Input:

First two inputs are integers n and m. n is the number of knights fighting in the tournament (2 <= n <= 100000, 1 <= m <= n-1). m is the number of battles that will take place.

The next line contains n power levels.

The next m lines contain two integers l and r, indicating the range of knight positions to compete in the ith battle.

After each battle, all nights apart from the one with the highest power level will be eliminated.

The range for each battle is given in terms of the new positions of the knights, not the original positions.

Output:

Output m lines, the ith line containing the original positions (indices) of the knights from that battle. Each line is in ascending order.

Sample Input:

8 4
1 0 5 6 2 3 7 4
1 3
2 4
1 3
0 1

Sample Output:

1 2
4 5
3 7
0

Here is a visualisation of this process.

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

[(7,6)]

I have solved this problem. My program produces the correct output, however, it is O(n*m) = O(n^2). I believe that if I erase knights more efficiently from the vector, efficiency can be increased. Would it be more efficient to erase elements using a set? I.e. erase contiguous segments rather that individual knights. Is there an alternative way to do this that is more efficient?

#define INPUT1(x)  scanf("%d", &x)
#define INPUT2(x, y)  scanf("%d%d", &x, &y)
#define OUTPUT1(x) printf("%d\n", x);

int main(int argc, char const *argv[]) {
    int n, m;
    INPUT2(n, m);
    vector< pair<int,int> > knights(n);
    for (int i = 0; i < n; i++) {
        int power;
        INPUT(power);
        knights[i] = make_pair(power, i);
    }
    while(m--) {
        int l, r;
        INPUT2(l, r);
        int max_in_range = knights[l].first;
        for (int i = l+1; i <= r; i++) if (knights[i].first > max_in_range) {
            max_in_range = knights[i].first;
        }
        int offset = l;
        int range = r-l+1;
        while (range--) {
            if (knights[offset].first != max_in_range) {
                OUTPUT1(knights[offset].second));
                knights.erase(knights.begin()+offset);
            }
            else offset++;
        }
        printf("\n");
    }
}

Answer 1

Well, removing from vector wouldn't be efficient for sure. Removing from set, or unordered set would be more effective (use iterators instead of indexes).

Yet the problem will still remain O(n^2), because you have two nested whiles running n*m times.

--EDIT--

I believe I understand the question now :) First let's calculate the complexity of your code above. Your worst case would be the case that max range in all battles is 1 (two nights for each battle) and the battles are not ordered with respect to the position. Which means you have m battles (in this case m = n-1 ~= O(n))

• The first while loop runs n times
• For runs for once every time which makes it n*1 = n in total
• The second while loop runs once every time which makes it n again.
  • Deleting from vector means n-1 shifts that makes it O(n).

Thus with the complexity of the vector total complexity is O(n^2)

First of all, you don't really need the inner for loop. Take the first knight as the max in range, compare the rest in the range one-by-one and remove the defeated ones.

Now, i believe it can be done in O(nlogn) with using std::map. The key to the map is the position and the value is the level of the knight.

Before proceeding, finding and removing an element in map is logarithmic, iterating is constant.

Finally, your code should look like:

while(m--) // n times
    strongest = map.find(first_position); // find is log(n) --> n*log(n)

    for (opponent = next of strongest; // this will run 1 times, since every range is 1
         opponent in range;
         opponent = next opponent) // iterating is constant
       // removing from map is log(n) --> n * 1 * log(n)
       if strongest < opponent
           remove strongest, opponent is the new strongest
       else
           remove opponent, (be careful to remove it after iterating to next)

Ok, now the upper bound would be O(2*nlogn) = O(nlogn). If the ranges increases, that makes the run time of upper loop decrease but increases the number of remove operations. I'm sure the upper bound won't change, let's make it a homework for you to calculate :)

Answer 2

A solution with a treap is pretty straightforward.

For each query, you need to split the treap by implicit key to obtain the subtree that corresponds to the [l, r] range (it takes O(log n) time). After that, you can iterate over the subtree and find the knight with the maximum strength. After that, you just need to merge the [0, l) and [r + 1, end) parts of the treap with the node that corresponds to this knight.

It's clear that all parts of the solution except for the subtree traversal and printing work in O(log n) time per query. However, each operation reinserts only one knight and erase the rest from the range, so the size of the output (and the sum of sizes of subtrees) is linear in n. So the total time complexity is O(n log n).

I don't think you can solve with standard stl containers because there'no standard container that supports getting an iterator by index quickly and removing arbitrary elements.