×

WORLDCUP - Editorial

Author: Devendra Agarwal
Tester: Anudeep Nekkanti
Editorialist: Amit Pandey

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.

This question is marked "community wiki".

25911522
accept rate: 0%

19.8k350498541

The formula is not visible clearly. I guess the editorialist means the following

$\text{Ways} = \frac {B!}{(X!)(Y!)(Z!)(W!)} ={B \choose X} {B-X \choose Y} {B-X-Y \choose W}$

(16 Feb '15, 00:22)

Yes, updated :) thanks.

(16 Feb '15, 00:25)

 6 My solution.. Keep ways[ball][run][wicket] = ways to score 'run' in 'ball' loosing atmost 'wicket' Now, for (ball = 1 .. B)             for (run = 0 .. ball*6)                         for (wicket = 0 .. 9)                                   ways += ways[for4] + ways[for6] + ways[dot] + ways[wicket] code:http://www.codechef.com/viewsolution/6283769 answered 16 Feb '15, 00:54 148●2 accept rate: 22%
 5 I have solved it differently using 3-D 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 3-D DP. Here is the link of my solution answered 16 Feb '15, 00:47 99●3●9 accept rate: 0% 1 Will add this approach as well. :) (16 Feb '15, 00:53) 2 Used the same. 2nd best submission :) (16 Feb '15, 01:09)
 1 editorial really helped a lot.! :) answered 23 Jul '15, 18:13 781●8 accept rate: 7%
 0 Why did My Solution get TLE ?? http://www.codechef.com/viewsolution/6284511 answered 16 Feb '15, 03:24 3★yoyosonu 31●1●1●4 accept rate: 0% 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) yoyosonu3★ @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)
 0 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 3★leharb 1 accept rate: 0% dividing by W!, because there is fix order in wickets. (17 Feb '15, 15:47)
 0 Quick explanations are always awesome :) answered 10 Jun '15, 09:31 198●10●25●35 accept rate: 0%
 0 I have implemented the same thing, but why am I still getting TLE ? https://www.codechef.com/viewsolution/9927496 answered 15 Apr '16, 18:54 4★ps06756 18●1●2 accept rate: 9%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,167
×1,186
×1,173
×885
×109
×21

question asked: 09 Feb '15, 19:58

question was seen: 6,378 times

last updated: 15 Apr '16, 18:54