Competitive Programming Editorials

  Problem Link Algorithms used: DP In this problem, we are given an N by M grid. There are some "marked" cells that we need to cover using tape. The tape can only be applied horizontally or vertically, cannot cover "unmarked" cells and a marked cell cannot be covered by more than one piece of tape. We need to find the minimum number of pieces of tape required to cover every marked cell such that the above conditions are satisfied. We can solve this problem using DP. Usually, when the constraints on a variable are small (less than 20), we can expect bitmask DP to be part of the solution. It's no different here. I solve this problem recursively. We can go over every cell of the grid from top to bottom, left to right and maintain a bitmask that tells us which cells, from all the cells from (i-1, j) to (i, j-1), have been covered by a vertical piece of tape (signified by a 1 bit in the mask) or a horizontal piece of tape (signified by a 0 bit in the mask). If a cell...

  Problem Link In this problem, we are given 2 sets of N planks. We need to order the second set of planks such that they are "similar" to the first set the the sum of the differences between adjacent planks is maximized. The planks are similar if, for example, in the first set, plank i is smaller than plank i+1, then in the second set, plank i is also smaller than plank i+1. Likewise, if plank i is greater than plank i+1 or are equal, the same must happen in the second set. Let's take an example. Let's say the first set of planks is as follows: 4 2 6 9 8 The sum of differences would be a[1] - a[2] + a[3] - a[2] + a[4] - a[3] + a[4] - a[5] or a[1] - 2 * a[2] + 0 * a[3] + 2 * a[4] - a[5] The only possible coefficients for each element are -2, -1, 0, 1, 2 An element with a coefficient of +2 is going to increase our answer the most, so we should allocate the largest numbers to the positions with this coefficient. Likewise, elements with a coefficient of -2 is going to de...

  Problem Link Algorithms Used: Binary Search, Prefix Sums In this problem, we are given the positions of Fire (F), Grass (G) and Water (W) monsters represented by a string of F, G, and W characters. A monster can attack any adjacent monster. The winner of each attack is determined as follows: Fire beats Grass Grass beats Water Water beats Fire In an attack consisting of two monsters of the same type, either one can win. We need to determine the number of possible winners of the entire string. For each monster, we need to see if it can emerge as the ultimate winner or not. Let's say this monster is fire. In order for fire to win, all the water monsters on its left and right somehow need to die. This can only be done if there is a grass monster also present on the same side as the water monster because then the grass monster will kill all the water monsters and finally the fire monster can finish off the grass monster. So, for each monster, if a monster against which it loses is pre...