Regarding "Yeh pubg wala h kya" from Null void contest

Please explain how to calculate no of ways to form sum as n from 1 ,2 ,4 .

YES please Help Me too… i tried using brute force but got TLE .Anyone??

@user_404 @pnitinvsr its Dynamic Programming problem like the most famous coin change problem.

So basically if convert the given text to a mathematical problem it becomes:
Given that a,b,c are non negative integers, find all such possible values of a,b,c such that
4a + 2b + c = n
So first of all let us take the first two terms to the RHS, we get
c = n - 2b - 4a
The only restriction on c is that it should be greater than or equal to zero.
Therefore n - 2b - 4a ≥ 0

We have successfully eliminated one variable. Now for a given value of a it would be very easy to find the number of solutions for b right? Its just \lfloor (n-4a)/2 \rfloor

So now one can just loop all values of a from 0 to \lfloor n/4 \rfloor and keep summing up the values of \lfloor (n-4a)/2 \rfloor for all valid values of a.

The complexity now becomes O(n), one would think this would be sufficient to pass through all the test cases. But that one would be wrong. Believe me, I have tried :stuck_out_tongue: . So we have to find a general formula for this question and indeed it exists. Its not that hard to find the general formula from here so I leave it up to you.

Here is my solution (although some variable names may be different in my original solution) https://www.codechef.com/viewsolution/24489499

1 Like