Competitive Programming Editorials

  Problem Link Time Complexity: O(N log N + M log N) Algorithm Used: Dynamic Range Maximum Queries, Segment Tree In this problem, a list of hotels is given, each having Hᵢ rooms. Then a list of people are given, each wanting Pᵢ rooms. Then people must be processed in the order given and for each group, the first available hotel must be assigned. Then the number of rooms available in that hotel decreases by the number of rooms taken. This problem uses Dynamic Range Maximum Queries. A segment tree can be used for this purpose. For each group of people, we walk down the segment tree, starting from the top node. Each node in the tree will have 2 children except for the leaves. We check both the children and choose the first of the two children (the first hotel) which has at least the number of rooms required by the group. This continues until a leaf is found.  If neither of the children have enough rooms for the group, then none of the hotels will have enough rooms, so the program...

Problem Link Time Complexity: O(NlogN) Algorithm used: Segment Trees In this problem, the lengths of N hairs are given. For each j = 0, j = 1, ..., j = N-1, reduce all hair lengths greater than j to j. Then find the number of inversions. An inversions is a pair of hairs such that the first hair has a greater length than the second, and precedes the second hair in the input. We could directly simulate this process by reducing the hairs for every j, and then count the inversions in N² or NlogN time. But, this method would be too slow to pass completely.  Instead, we need a quick way to know the number of pairs of a and b, such that a > b and a precedes b in the input aka the number of inversions. We do this by maintaining two arrays: one for storing the frequency of the hairs, and another for storing the the number of inversions in terms of b. The reason why we store the number of inversions in terms of b instead of a is because when a hair is reduced, some of the inversions for t...