You are not logged in. Please login at to post your questions!


WORLDCUP - Editorial




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




Dynamic programming or combinatorics.


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).


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.


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;


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".

asked 09 Feb '15, 19:58

amitpandeykgp's gravatar image

accept rate: 0%

edited 11 Feb '16, 19:08

admin's gravatar image

0★admin ♦♦

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) mediocoder3★

Yes, updated :) thanks.

(16 Feb '15, 00:25) amitpandeykgp4★

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]


answered 16 Feb '15, 00:54

pranav_is_cool's gravatar image

accept rate: 22%

edited 16 Feb '15, 02:19

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

rajatgoyal's gravatar image

accept rate: 0%

edited 16 Feb '15, 01:00


Will add this approach as well. :)

(16 Feb '15, 00:53) amitpandeykgp4★

Used the same. 2nd best submission :)

(16 Feb '15, 01:09) dhruvmullick5★

editorial really helped a lot.! :)


answered 23 Jul '15, 18:13

code_hard123's gravatar image

accept rate: 7%

Why did My Solution get TLE ??


answered 16 Feb '15, 03:24

yoyosonu's gravatar image

accept rate: 0%

There is no need of clearDP function. It has caused you TLE.

(16 Feb '15, 09:56) rajatgoyal4★

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) betlista ♦♦3★

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) rahul_nexus2★

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

leharb's gravatar image

accept rate: 0%

dividing by W!, because there is fix order in wickets.

(17 Feb '15, 15:47) amitpandeykgp4★

Quick explanations are always awesome :)


answered 10 Jun '15, 09:31

hitesh091's gravatar image

accept rate: 0%

I have implemented the same thing, but why am I still getting TLE ?


answered 15 Apr '16, 18:54

ps06756's gravatar image

accept rate: 9%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 09 Feb '15, 19:58

question was seen: 6,378 times

last updated: 15 Apr '16, 18:54