Competitive Programming Editorials

  Problem Link Algorithm Used: 2P, Sliding Window, Sorting Time Complexity: O(N + M) Thanks to  Alphastar USACO Training  for making this video, which helped me understand this problems solution. In this problem, there are K grassy patches, situated on a number line, whose positions are distinct integers in the range 0 to 10⁹. Each of the grassy patches has a yumminess value associated with it. Farmer Nhoj has situated his M cows on the number line (not necessarily on grassy patches), and FJ needs to position his N cows too. The grassy patches will be owned by the farmer whose cow(s) are closest to the patch. If FJs and Farmer Nhojs (will be called FN now) cows are equally close to a grassy patch, then FN owns that patch. If FJ owns a patch, then his score increases by the yumminess value of that patch. Position FJs cows such that his score is maximal (FJ may place his cows on fractional positions on the number line too). To solve this problem, here are a few observations...

Problem Link Algorithm Used: Connected Components (DFS), binary search, two pointer Time Complexity: O(T(N + M)) In this problem, T test cases are given. In each test case, there are N fields and M roads, which connect two fields. FJ can build at most 2 roads. The cost of building a new road between field i and field j is (i - j)². There is a barn located in field 1 and another in field N. Find the minimum cost to get from the first to the second barn. This problem can be modelled as a graph problem, where the fields are the node and the roads are the edges. Roads are bidirectional and have a weight of 0. Only the new roads will be weighted, depending on the nodes they connect. There are three possible cases: FJ may build 0, 1 or 2 roads. The only case where FJ can build no roads and still reach the second barn is when the two barns are already connected by existing roads, which means that they are in the same component.  The component containing the first barn will be called the s...

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

  Problem Link Algorithm Used: Dynamic Programming Time Complexity: O(N³) There are N groups of snakes given, of varying sizes. Nets are used to catch the snakes. Each net must be at least the size of the group of snakes being caught. Every time a group of snakes is caught, the space wasted is the difference in the size of the net and the size of the current group of snakes. To minimize the total amount of wasted space, the net size may be changed up to K times. Find the minimum total space that must be wasted in order to catch all the snakes. At first glance, the way the nets are changed doesn't seem to follow any specific pattern that leads to a greedy/binary search/sorting solution, so the only other option is brute force. There are N groups of snakes and nets may be changed N times so there are N² possible states. For each state, the net size must be calculated by scanning the groups of snakes, so that a net that is smaller than the current group of snakes is not chosen. Then, ...

  Problem Link Time Complexity: O(Nlog(KlogK)) Algorithm used: Dijkstra's algorithm, Binary Search This  is where I understood how to solve this problem in time. In this problem, the breeds of N cows are given, followed by a K by K matrix, describing whether or not a cow of breed i is willing to transmit a message to cow of breed j. The cost of sending a message from cow i to cow j is |i - j|. Find the minimum possible cost of transmitting a message from cow 1 to cow N. This problem can be represented as a graph problem, where the cows are the nodes and edges are drawn between the nodes depending on the compatibility of cow breeds, described in the matrix. While reading in the matrix, also create an adjacency list for every breed. Intuitively, we could run a standard  Dijkstra's algorithm  starting from cow 1 and loop over the adjacency list for every pass of the algorithm. Although this implementation would always produce the correct answer, the program would exceed...