ABC170 E --How to solve without using multiset of Smart Infants

The explanation using multiset was written in the E problem of AtCoder Beginner Contest, but I think that there are languages such as python that do not have mutiset, so I would like to introduce an alternative algorithm using Priority Queue (heapq). I will not explain the problem itself, so please read the official explanation there.

problem

ABC170 E - Smart Infants https://atcoder.jp/contests/abc170/tasks/abc170_e

Prerequisite knowledge

multiset Internally [Binary Search Tree](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C % A8) is used. This keeps the data sorted at all times instead of taking O (logN) every time a data is inserted. Therefore, it is possible to delete and search with O (logN). By implementing the binary search tree yourself, you can use it in languages that are not provided as standard, but you need to devise to maintain the balance. (Example of ingenuity: [Tree master training course] 7-1. What is Splay tree? Explanation [Competition professional Katsuppa])

Priority Queue Internally in GCC [binary heap](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83 % 97) is used. The same data structure is used internally in python's heapq. Inserting data takes O (logN) every time, like a binary search tree. Since it is a heap tree, the inside is ** not sorted, and you cannot search or delete anything other than the maximum (minimum) value at high speed **, but you cannot always get the maximum (minimum) value with the computational complexity O (1). I can do it. The advantage over the binary search tree is that the amount of calculation is stable because the equilibrium is always maintained without any special effort.

solution

The point

In this issue

  1. Get the maximum rate for each kindergarten --Getting the minimum value of the set of maximum rate values --Insert values into each set when entering the park --Delete the value from each set when changing gardens

It would be nice if could always be done at high speed.

As mentioned in the official commentary, each process can be performed at high speed by using multiset, but since the 4th process cannot be performed at high speed with Priority Queue, it is necessary to change the way of thinking.

In solving this problem, let's note that the fourth condition is ** not necessarily a process that must be performed unless it interferes with the first and second conditions **. In other words, it doesn't matter if the maximum value of the rate set and the minimum value of the maximum rate set in each kindergarten are not affected even if they are not actually deleted from the data.

Specific algorithm

Since the implementation does not change under the first and second conditions (the maximum and minimum are flipped over), the first condition (obtaining the maximum value of the set) will be explained as an example.

Now consider having two Priority Queues.

  1. Those that manage the entire set
  2. One that holds the element that should have been deleted

And ** insert an element in 1 when you enter the park and in 2 when you change the park. If the maximums of 1 and 2 are the same, remove them from both. ** ** This ensures that the maximum value for this kindergarten is always the same as the maximum value for 1.

I'll put some code here, but it doesn't work even if I copy it depending on the environment because std and include are broken.

code.cpp


priority_queue<int> in;
priority_queue<int> out;

//Processing when entering the park
void infant_in(int i){
    in.push(i);
}

//Processing when changing gardens
void infant_out(int i){
    out.push(i);
    while(!out.empty() && in.top() == out.top()){
        in.pop();
        out.pop();
    }
}

//Get maximum
int get_max(){
    return in.top();
}

Let's look at a concrete example. Consider that kindergartens with rates of 3, 5 and 8 enter the kindergarten, and then children with rates of 5 and 8 move in this order.


>Three kindergarten children enter
Actual kindergarten= {3,5,8}
1 = [3,5,8] 2 = []   #Of course the maximum value at this point is 8

>Children with a rate of 5 are transferred
Actual kindergarten= {3,8}
1 = [3,5,8] 2 = [5]  #The maximum value is 8

>Children with a rate of 8 are transferred
Actual kindergarten= {3}
1 = [3,5,8] 2 = [5,8]
1 = [3,5]   2 = [5]
1 = [3]     2 = []   #The maximum value is 3

With this kind of feeling, you can see that there is no problem in getting the maximum value.

Computational complexity

It is an interesting calculation amount, but since the number of times to delete the value from in and out that seems to be a bottleneck in this problem is Q times at the maximum, it can be ignored, and the calculation amount is O (NlogN) required when inserting the value. Become. This is fast enough.

Recommended Posts

ABC170 E --How to solve without using multiset of Smart Infants
How to find out the number of CPUs without using the sar command
Review of atcoder ABC158, up to question E (Python)
[Circuit x Python] How to solve circuit equations symbolically using sympy
Survey log of how to optimize LightGBM hyperparameters using Optuna
Solve ABC176 E in Python
Offline real-time how to write Python implementation example of E15 problem
How to write offline real time Solve E04 problems in Python
How to save only a part of a long video using OpenCV
How to POST to a specified channel without using Slack's Incoming WebHooks
How to install python using anaconda
Summary of how to use pandas.DataFrame.loc
How to solve simultaneous linear equations
Summary of how to use pyenv-virtualenv
Summary of how to use csvkit
How to solve slide puzzles and 15 puzzles
How to test each version of IE using Selenium in modan.IE (VM)
How to write offline real time I tried to solve E11 with python
Apply functions to rows or columns of numpy.array without using list comprehensions
How to write offline real time I tried to solve E12 with python