Competitive Programming Editorials

  Problem Link Problem Summary There are N students that each have a skill rating a_i. You need to group them (not necessarily all) into at least one and at most K non-empty groups, but the range of skill ratings of the students in a group should not exceed 5. Find the number of ways the students may be divided into groups. Algorithm Used Knapsack DP, Sorting Editorial First, sort the skill ratings in ascending order - this will make find the answer easier later on. Let's say we have to find the answer to following problem: make j groups and only choosing from the first i students. To find the answer to this subproblem, we can use the following subproblems: Don't include the ith student in the jth group. Include the ith student in the jth group. If we don't include the ith student in the jth group, then the answer to this subproblem is simply the answer for grouping i-1students in j group. But if we include the ith student in the jth group, then we find the number of stud...

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