Problem Statement
Problem
Dr. Patel has N stacks of plates. Each stack contains K plates. Each plate has a positive beauty value, describing how beautiful it looks.
Dr. Patel would like to take exactly P plates to use for dinner tonight. If he would like to take a plate in a stack, he must also take all of the plates above it in that stack as well.
Help Dr. Patel pick the P plates that would maximize the total sum of beauty values.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the three integers N, K and P. Then, N lines follow. The i-th line contains K integers, describing the beauty values of each stack of plates from top to bottom.
Output
For each test case, output one line containing
Case #x: y, where x is the test case number (starting from 1) and y is the maximum total sum of beauty values that Dr. Patel could pick.Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ 30.
1 ≤ P ≤ N * K.
The beauty values are between 1 and 100, inclusive.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ 30.
1 ≤ P ≤ N * K.
The beauty values are between 1 and 100, inclusive.
Test set 1
1 ≤ N ≤ 3.
Test set 2
1 ≤ N ≤ 50.
Sample
Input | Output |
2 2 4 5 10 10 100 30 80 50 10 50 3 2 3 80 80 15 50 20 10 | Case #1: 250 Case #2: 180 |
In Sample Case #1, Dr. Patel needs to pick P = 5 plates:
- He can pick the top 3 plates from the first stack (10 + 10 + 100 = 120).
- He can pick the top 2 plates from the second stack (80 + 50 = 130) .
In Sample Case #2, Dr. Patel needs to pick P = 3 plates:
- He can pick the top 2 plates from the first stack (80 + 80 = 160).
- He can pick no plates from the second stack.
- He can pick the top plate from the third stack (20).
Note: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.
Problem link
Video Tutorial
You can find the detailed video tutorial hereThought Process
First thought is similar to merging multiple lists, this won't work since the lists are not sorted and we are not allowed to sort due to the order constraint.Second thought is keep a max heap, and always merge the largest value from all the top elements in the lists. This is wrong since greedy won't work here. E.g., below if we want to pick 3 plates, using max heap will pick 2, 2, 2, instead of 1, 1, 100
2, 2, 2, 2, 2
1, 1, 100, 100, 100
Third thought seems we have to brute force, for all the combos of P, we check what's the maximum value. Quote from the analysis, it's exponential time complexity
For example, if N = 3 and for any given values of K and P, generate all possible triples (S1, S2, S3) such that S1+S2+S3 = P and 0 ≤ Si ≤ K. Note: Si is the number of plates picked from the i-th stack.Forth and final solution to optimize this is using dynamic programming. It's very common in those coding competitions.
This can be done via recursion and the total time complexity is O(KN) which abides by the time limits.
Quote from the analysis
First, let's consider an intermediate state dp[i][j] which denotes the maximum sum that can be obtained using the first i stacks when we need to pick j plates in total.
Next, we iterate over the stacks and try to answer the question: What is the maximum sum if we had to pick j plates in total using the i stacks we've seen so far? This would give us dp[i][j]. However, we need to also decide, among those j plates, how many come from the i-th stack? i.e., Let's say we pick x plates from the i-th stack, then dp[i][j] = max(dp[i][j], sum[i][x]+dp[i-1][j-x]). Therefore, in order to pick j plates in total from i stacks, we can pick anywhere between [0, 1, ..., j] plates from the i-th stack and [j, j-1, ..., 0] plates from the previous i-1 stacks respectively. Also, we need to do this for all values of 1 ≤ j ≤ P.The flow would look like:
for i [1, N]:
for j [0, P]:
dp[i][j] := 0
for x [0, min(j, K)]:
dp[i][j] = max(dp[i][j], sum[i][x]+dp[i-1][j-x])If we observe closely, this is similar to the 0-1 Knapsack Problem with some added complexity. To conclude, the overall time complexity would be O(N*P*K).
Solutions
DP solution
Time Complexity: O(N*P*K)Space Complexity: O(N*max(P, K))
