Google Kickstart Problem 2 Plates

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.

Could you please brief up the problem?

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

1 Like

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

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: https://gist.github.com/virresh/d838c05f0c88b78eab13efb5829bd48a

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.

2 Likes

Thank you so much virresh for your efforts!!