What will be approach for this prob?

#1

Can u give some hint plz

#2

Hey @pranjalarora98
if we try to solve it using 3-D DP, then the space complexity will be (5000 )^3 which is more than 10^8 so it will give us TLE. Though we can optimize it by using only 2 parameters. It’s because among a and b overall only one of them is responsible for defining the state of dp so if we know one of them then we can find other. Therfore complexity will be reduced
For eg:- a=3 , b=4, n=5

  • now for current state i=3, and b’=2 which means (b’ = b-2 = 4-2) so 2 items are taken by guddu bhaiya but since i=3 that means i=0,1,2 i.e. 3 boxes are already taken. So one box is taken by bablu

  • so accordingly a’ should be a’ = a-1 = 3-1 = 2.
    So here there are only 2 unique parameters that are defining the state of DP.

#3

Moreover editorial will be well explained. So if it doesn’t help you. Go through the editorial too.

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.