Competitive Programming Editorials

  Problem Link Time Complexity: O(M log N) Algorithm Used: Disjoint Union Set There are N barns, connected by M (1 ≤ N, M ≤ 2 * 10⁵) bidirectional roads. The barns will be closed one by one. Each time a barn is closed, all roads to and from that barn cannot be used. After each barn is closed, find out whether it is possible to reach every open barn from any other open barn. This is a graph problem, since the barns can be represented as nodes and the roads as edges. The graph is unweighted.  A naive solution to this problem would be to simulate the situation by closing a barn, then picking an arbitrary open barn and running a DFS to visited all barns possible. If all the barns supposed to be open were not visited (since they are not in the same component), then it is not possible to reach every open barn from any other open barn. This is a simple and straightforward solution that will all produce the correct output, but it would exceed the time limit with a time complexity of O...

  Problem Link Algorithm Used: Range Queries, Segment Tree Treat the cow entry and exit points as the beginning and ending of ranges. /*  1. for each cow, create a range, such that cow i enters at point a and exits         at point b the range for this cow will be (a, b)     2. sort the ranges based on starting point to make it easier to count number         of overlapping ranges     3. create a segment tree     4. iterate over the ranges, and create a difference array storing the ranges         since the ranges are added one by one, use a segment tree to store the         difference array so that it can be updated quickly and sum queries can         also be done quickly     5. For each range, figure out the number of ranges that it overlaps with         To do this, find out the number of ranges that start before the ...

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...