WORLDCUP - Editorial

combinatorics
cook55
dynamic-programming
maths
simple
worldcup

#1

PROBLEM LINK:

Practice

Contest

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 imes ext{fours} + 6 imes ext{sixes} = R \\ ext{fours} + ext{sixes} + ext{wickets}(\le L) + ext{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.

ext{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**[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.


#2

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


#3

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


#4

Why did My Solution get TLE ??

http://www.codechef.com/viewsolution/6284511


#5

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?


#6

Quick explanations are always awesome :slight_smile:


#7

editorial really helped a lot.! :slight_smile:


#8

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

https://www.codechef.com/viewsolution/9927496


#9

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

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


#10

Yes, updated :slight_smile: thanks.


#11

Will add this approach as well. :slight_smile:


#12

Used the same. 2nd best submission :slight_smile:


#13

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


#14

how will I memoize then. For each testcase I need to clear the DP … can’t it be solved with top_down. ?


#15

@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

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)


#17

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