Below are the links to both the problems. https://atcoder.jp/contests/dp/tasks/dp_m
https://atcoder.jp/contests/dp/tasks/dp_j
I have read and re-read the problems again and again but I am not able to understand how to solve these two. I have seen the submissions of other contestants also, even from that I am not able to make much sense. Can you please explain how to approach these problems and suggest similar problems that use the same concept. Thanks
Problem M: link
Problem J: link
Please can someone explain the Approach for J-sushi problem.What should be my dp states. And how to proceed further with that knowledge.
Did you solved that problem ?? Any hint ?
did you try any of the other links?
Not only links , i have watched even 2-3 videos and blogs too , but still not getting why ,: in equation f(x,y,z) = (1+ p1*f(x-1,y,z)+p2*f(x+1,y-1.z)+p3*f(x,y+1,z-1))/(1-p0) :
why are we adding 1 to x in second term , and 1 to y in third term . That's why i asked .
because if we eat 1 sushi off of a dish with 3, then the dish will be left with 2, so the number of dishes with 3 decreases and the number of dishes with 2 decreases (similarly for the other case)
Solution to M-Candies here.
Bottom up solution. Prefix sum is calculated to do the transitions in O(1) or else the transitions would have costed O(ai) which will lead to TLE.
Errichto has made a video on all the tasks : link
Someone reopens the post, so... here is my approach for M-candies