PROBLEM LINK:
Author: Devendra Agarwal
Tester: Anudeep Nekkanti
Editorialist: Amit Pandey
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, pre-calculate 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 at-max 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} {B-X \choose Y} {B-X-Y \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.
Number of fours = (R -6*sixes)/4 if ((R - 6*sixes) % 4 == 0)
And we can loop over number of wickets from 0 to L.
Number of zeros = B-sixes-fours-wickets
The following piece of self explanatory code will do all the calculations.
for(int six=0; six*6 <= r && six <= b; six++) {
int other = r - six*6;
if(other % 4 == 0) {
int four = other/4;
for(int wicket=0; wicket <= l; wicket++) {
if(six + four + wicket <= b) {
long long cur = C[b][six];
( cur *= C[b-six][four] ) %= 1000000007;
( cur *= C[b-six-four][wicket] ) %= 1000000007;
ways += cur;
}
}
ways %= 1000000007;
}
}
Solutions:
Setter’s solution can be found here .
Setter’s another solution can be found here .
Tester’s solution can be found here.
thanks.