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

×

WORLDCUP - Editorial

7
2

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

asked 09 Feb '15, 19:58

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 11 Feb '16, 19:08

admin's gravatar image

0★admin ♦♦
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) 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]
code:
http://www.codechef.com/viewsolution/6283769

link

answered 16 Feb '15, 00:54

pranav_is_cool's gravatar image

3★pranav_is_cool
1482
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

link

answered 16 Feb '15, 00:47

rajatgoyal's gravatar image

4★rajatgoyal
9939
accept rate: 0%

edited 16 Feb '15, 01:00

1

Will add this approach as well. :)

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

Used the same. 2nd best submission :)

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

editorial really helped a lot.! :)

link

answered 23 Jul '15, 18:13

code_hard123's gravatar image

6★code_hard123
7818
accept rate: 7%

Why did My Solution get TLE ??

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

link

answered 16 Feb '15, 03:24

yoyosonu's gravatar image

3★yoyosonu
31114
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?

link

answered 16 Feb '15, 21:31

leharb's gravatar image

3★leharb
1
accept rate: 0%

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

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

Quick explanations are always awesome :)

link

answered 10 Jun '15, 09:31

hitesh091's gravatar image

3★hitesh091
198102535
accept rate: 0%

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

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

link

answered 15 Apr '16, 18:54

ps06756's gravatar image

4★ps06756
1812
accept rate: 9%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×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