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 Tags: 2P, Sorting Time Complexity :  O(nlogn) In this problem, we are given a list of  N  block widths, and we are asked to compute the number of towers that can be built, with each block allowing blocks of  D  tolerance to be placed above or below it. To begin with, block  i  can be placed below or above block  j  only if their widths have a difference of at most  D. First, sort the blocks in ascending order of widths. This will help in determining the blocks that can be placed below and above the different blocks. Next, for block  i,  we need to figure out the number of blocks that have a maximum difference of width  D . A naive approach would be to use two pointers: keep the left and right pointer at block  i  initially, but advance the right pointer until we hit a block whose width is more that block  i  width +  D . However, this approach would exceed time limit (t ime comp...