How can I erase elements more efficiently from a vector or set?
Description of the problem:
Input:
The first two inputs are integers n and m. n - the number of knights battles 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 positions of the knights to compete in the i-th battle.
After each battle, all nights except 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 starting positions.
Output:
Print m lines, the i-th line containing the initial positions (indices) of the knights of this battle. Each line is in ascending order.
Input example:
8 4
1 0 5 6 2 3 7 4
1 3
2 4
1 3
0 1
Output example:
1 2
4 5
3 7
0
Here is a visualization 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 correct output, however O (n * m) = O (n ^ 2). I believe that if I erase knights from the vector faster, the efficiency can be increased. Would it be more efficient to erase items with a set? That is, erase adjacent segments, not individual knights. Is there an alternative way to make this 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");
}
}
source to share
Well, removing from the vector won't be efficient. Removing from a set or an unordered set would be more efficient (use iterators instead of indices).
However, the problem is still O (n ^ 2), because you have two nested whiles executing n * m times.
- EDIT -
I believe I understand the question now :) First, let me calculate the complexity of your code above. In the worst case, the maximum range in all battles is 1 (two nights for each battle) and battles are not ordered by position. This means you have a battle (in this case m = n-1 ~ = O (n))
- The first while loop is executed n times
- To run is done once every time, making it n * 1 = n in total
- The second while loop runs every time it does n again.
- Removing from a vector means n-1 shifts, which makes it O (n).
So the complexity of the vector total complexity is O (n ^ 2)
First of all, you don't need an inner loop. Take the first knight as the max in the 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 std :: map. The key to the map is the position, and the value is the level of the knight.
Before continuing, finding and removing an item in the map is logarithmic, iteration is constant.
Finally, your code should look like this:
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 will be O (2 * nlogn) = O (nlogn). Increasing the ranges will decrease the run time of the upper loop, but increase the number of deletions. I'm sure the upper bound won't change, let's do your homework for the calculation :)
source to share
The treap solution is pretty straightforward.
For each request, you need to split the treap with an implicit key to get the subtree that matches the range [l, r]
(takes time O(log n)
). After that, you can iterate through the subtree and find the knight with maximum strength. After that, you just need to concatenate [0, l)
and [r + 1, end)
the treap parts with the node that corresponds to that knight.
It is clear that all parts of the solution, with the exception of traversing and printing a subtree, run in O(log n)
time per request. However, each operation only reinserts one knight and erases the rest of the range, so the output size (and the sum of the subtree sizes) is linear in n
. Thus, the overall time complexity O(n log n)
.
I don't think you can solve with standard stl containers, because there is no standard container that would quickly get an iterator by index and remove arbitrary elements.
source to share