Competitive Programming Editorials

  Problem Link Algorithm used: Knapsack DP Time Complexity: O(N²) In this problem, you start out with  an array A of size N where all elements are initially 1  an array B of size N where all elements are in the range 1 - 10³ an array C of size N where all elements are in the range 1 - 10⁶.  In one operation, you may increase the value of A[i] by  ⌊A [i] / x ⌋ , where x is a non negative integer. You may do this at most K times. For each A[i] that you modify, such A[i] = B[i], you receive C[i] coins. Find the most number of coins that you may receive while not performing more than K operations. For each A[i], find the minimum num ber of operations needed to convert 1 to B[i]. This can be done using a simple BFS, where each node is the cur rent value of A[i], and the distance to this node is the number of operations needed to reach this value. For a distance x, we can increase it by x/1, x/2, x/3 ... x/x. It doesn't make sense to divide x by any number greater tha...

  Problem Link Algorithm used - Greedy, Data structures Time Complexity: O(N log N) You start out with a health value of 0. There are N potions numbered 1 to N that are examined sequentially. You may choose either drink or not drink a potion. Upon drinking a potion your health value changes by the potion's value. If the potion's is positive, then your health value increases by the potion's value. But if it's negative then your health value decreases by the potion's value. You must ensure that your health value remains non-negative. Find the maximum number of potions that you can drink. It is obvious that you can drink all potions whose values are greater than or equal to 0, since your health value will never dip below 0 upon drinking these. To maximize the answer, we should also try to drink some negative potions. To try and drink the maximum number of potions with a negative value, we sort them in ascending order and iterate over them. For each potion, check if our...