Google Kickstart Problem 2 Plates

1

Hi Everyone! I spent a lot of time on solving this problem during the contest but couldn’t.
So if anyone could help me with my code and approach that will be great.

https://ideone.com/tMP6F7

In editorial, problem was solved by dp and since i am not that much comfortable with dp can someone suggest to solve the problem by different approach other than dp if my approach isn’t correct.

2

Could you please brief up the problem?

3

He forgot to link it.
Question
I don’t think there’s any solution other than a knapsack dp.

1 Like
4

Hey, actually it is knapsack DP. I can’t find a way to help you, but what I can say is that you can check AtCoder for its DP contests. They are really awesome. @everule1 has mentioned this in quite a few posts. You should really check them as they have varying difficulty levels and it will surely build up your foundations. You can also watch videos on Dynamic Programming. :slight_smile:

2 Likes
5

The solution you provided is greedy, and not optimal. Once you choose a plate from a stack, you stick with it, without considering that some other stack may have a plate with higher beauty.

Consider the case:

1
3 2 2
80 80
15 50
20 1000

There is really no other way than DP to get the optimal answer. However, there are a few things that can probably help you understand the solution.
Thinking of it as a knapsack is probably easier if you’re familiar with the knapsack problem. However if not, this problem works extremely well with simple memoization.

Steps:

  1. Implement a recursive solution (brute-force it)
  2. Identify the parameters that change in the recursive function
  3. Create an array/map to store them and use that array/map within the recursive function

This strategy is extremely helpful in a lot of problems, including this one.

For this particular problem, consider my two solutions: Kickstart 2020, Round A, Plates · GitHub

The relevant function is:

int plate_beauty[sz][sz];

int max_beauty(int curr_stk, int K, int plates_left){
    if(plates_left <= 0 || curr_stk < 0){
        return 0;
    }
    int max_b = max_beauty(curr_stk-1, K, plates_left), cur_b=0;
    for(int i=0; i<min(plates_left, K); i++){
        cur_b += plate_beauty[curr_stk][i];
        max_b = max(cur_b + max_beauty(curr_stk-1, K, plates_left-i-1), max_b);
    }
    return max_b;
}

plate_beauty is a 2-D array that holds one stack in every row, and j’th element in i’th row corresponds to the beauty of j’th plate in i’th stack from top.
The brute-force logic is simple. We start from last stack and consider only curr_stk stack at a time.
We have following options:

  1. Do not choose any plate from this stack and move to previous stacks
  2. Choose i+1 plate(s) from this stack and choose remaining from previous stacks (i is 0 indexed)

The loop just imitates this and stores maximum beauty amongst all the above configurations
With the memoization steps above, you can convert this to a simple top-down DP. The same is done in memoization.cpp in the link.

This form of dp is called top-down and I usually find it easier to understand. Hope that it’ll get you started with similar problems.

4 Likes
6

Thank you so much virresh for your efforts!!