PROBLEM LINK:Author: Devendra Agarwal DIFFICULTY:Simple. PREREQUISITES:Dynamic programming or combinatorics. PROBLEM:Dehatti wonders how many ways can his team score exactly $R$ runs in $B$ balls with $L$ wickets. Given that each ball can result in $4, 6, 0$ runs or a wicket(wicket won't add anything to score). QUICK EXPLANATION:Suppose we want to make $R$ runs in $B$ balls, having $X$ number of $4$'s, $Y$ number of $6$'s, ($W \le L$) number of wickets and $Z$ number of $0$'s. So there will be $4X + 6Y = R$ and $X+Y+W+Z = B$. If $(x,y,z,w)$ is a particular solution to given equations, then number of ways of arrangement will be $\frac {B!}{(x!)(y!)(w!)(z!)}$. We have to add all such cases, and the given time limit is sufficient for it. EXPLANATION:First of all, precalculate the value of $ ^n C_{r}$ which can be done using a simple dynamic programming approach. You may refer this link for the more details. As batsman has to make $R$ runs in $B$ balls, if $R > 6B$, there will not be any way of doing it. Suppose he makes $R$ runs in $B$ balls, with atmax $L$ wickets. So, we will have the following equations. $4 \times \text{fours} + 6 \times \text{sixes} = R \\ \text{fours} + \text{sixes} + \text{wickets}(\le L) + \text{zeros} = B$ There will be many solutions to the given equations for particular values of $R$,$B$ and $L$. We have to consider each one of them. Let us consider that a particular solution of the equation is fours = $X$, sixes = $Y$, wickets = $W$ and zeros = $Z$, or $(X,Y,Z,W)$ is a solution to the given equations. So, number of ways of arranging $X \hspace{2 mm}4's$, $Y \hspace{2 mm}6's$, $W$ wickets ans $Z \hspace{2 mm}0's$ can be calculated easily using the formula. $\text{Ways} = \frac {B!}{(X!)(Y!)(Z!)(W!)} \\ ={B \choose X} {BX \choose Y} {BXY \choose W}$ Values can be used from initially calculated ${n \choose r}$ values . Take care of modulus as well. T only thing remains is to produce all the triplets $(X,Y,Z,W)$. We can run a loop on number of sixes varying from 0 to min(B,R/6),number of fours will be fixed i.e.
And we can loop over number of wickets from 0 to L.
The following piece of self explanatory code will do all the calculations.
Solutions:Setter's solution can be found here .
This question is marked "community wiki".
asked 09 Feb '15, 19:58

My solution.. Keep ways[ball][run][wicket] = ways to score 'run' in 'ball' loosing atmost 'wicket' Now,
for (ball = 1 .. B) answered 16 Feb '15, 00:54

I have solved it differently using 3D DP.The three states of DP are runs,balls and wickets.Since maximum number of balls can be 300 so answer for runs > 6*300(=1800) will be 0.The cases for which runs<1800 can be solved by 3D DP. Here is the link of my solution answered 16 Feb '15, 00:47
1
Will add this approach as well. :)
(16 Feb '15, 00:53)
2
Used the same. 2nd best submission :)
(16 Feb '15, 01:09)

Why did My Solution get TLE ?? answered 16 Feb '15, 03:24
There is no need of clearDP function. It has caused you TLE.
(16 Feb '15, 09:56)
how will I memoize then. For each testcase I need to clear the DP .. can't it be solved with top_down. ?
(16 Feb '15, 20:57)
@yoyosonu: how the solution (DP matrix) for test case 1 differs from test case 2? Think about it, whether you really need a clearing...
(16 Feb '15, 21:11)
Why not solve for cases outside the while(t) loop..thus there is no need to clear the memory..Once you have calculated for all values of b,r,w? The problem with your solution is that the no of test cases are too many..Thus it becomes easier to precompute for all combinations of b,r,w and give answer for each test case in O(1)
(16 Feb '15, 22:57)

Why are you dividing by W! ? Is there no difference between the wickets? Wicket no. 1 bowled out at second position and wicket no. 2 bowled out at first position is same? answered 16 Feb '15, 21:31

Quick explanations are always awesome :) answered 10 Jun '15, 09:31

I have implemented the same thing, but why am I still getting TLE ? answered 15 Apr '16, 18:54

The formula is not visible clearly. I guess the editorialist means the following
$\text{Ways} = \frac {B!}{(X!)(Y!)(Z!)(W!)} ={B \choose X} {BX \choose Y} {BXY \choose W}$
Yes, updated :) thanks.