Dish Distribution

Problem code: DISHDIS

All submissions for this problem are available.

Chef feels that being the Head Chef is a very difficult job. More than cooking, managing the kitchen and distributing the work between various cooks proves to be a tiring task. There are many dishes to be prepared. And he has a team of talented cooks to do this for him. But the Chef always has a problem distributing tasks among them. For a cook i, the Chef wants to give him atleast xi dishes to prepare in a day. But different cooks have different capacities. Any cook i can cook atmost yi number of dishes in a single day. Chef is very aware of every cook's capability and will not give anyone more work than his maximum capacity. Now, he wants you to help him out here.

Your task will be simple: Tell him the number of ways in which he can distribute the given number of dishes among his team.

Input:

First line contains T, number of tests. Each test begins with a single line containing 2 space separated integers: n and m, the number of dishes to be prepared and the number of cooks in Chef's team.
Then follow m lines. The ith line contains 2 space separater integers which are the corresponding xi and yi.

Output:

For every test case, output a single integer: the number of ways of distributing the work mod 1000000007.

Constraints:

1<=T<=50
1<=n,m<=100
0<=xi,yi<=100

Example:

Input
1
3 2
0 3
1 3

Output
3

Explanation:
The chef can distribute the dishes in the following ways- 0 and 3 ; 1 and 2 ; 2 and 1 .
Author: vamsi_kavala
Date Added: 2-08-2011
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Whats happened if xi>yi,

gumantobalok @ 1 Oct 2011 03:28 PM
Whats happened if xi>yi, means chef want atleast more than the cook atmost capability?

Probably such a case will

gultus @ 1 Oct 2011 03:47 PM
Probably such a case will never occur as it mentioned in the build up story "Chef is very aware of every cook's capability and will not give anyone more work than his maximum capacity." That is not reflected in the constraints though.

It does not mean that input

gumantobalok @ 1 Oct 2011 03:51 PM
It does not mean that input does not given such that. Hope it will be as you said. can admin ensure that one?

Possibly yes but for the time

gultus @ 1 Oct 2011 03:54 PM
Possibly yes but for the time being you can assume that xi<=yi, I don't think it will be so hard to accommodate for the case xi>yi.

is it necessary to involve

jravi96 @ 1 Oct 2011 04:23 PM
is it necessary to involve each and every cook in dish distribution?

it depends on xi.

dewanshsharma @ 1 Oct 2011 04:48 PM
it depends on xi.

can anybody give me the

jravi96 @ 1 Oct 2011 05:03 PM
can anybody give me the output of the following simple test case 1 3 2 1 3 1 3

How long you will remain

shiplu @ 1 Oct 2011 05:28 PM
How long you will remain backdated? i love to solve in codechef but i hate this type of things, dp got AC but memoization got TLE.

My DP gets TLED :(

theicebreaker @ 1 Oct 2011 05:45 PM
My DP gets TLED :(

can u pls giv me some more

karan_saxena @ 1 Oct 2011 06:51 PM
can u pls giv me some more examples?

admin pls provide a bigger

k53sc @ 1 Oct 2011 07:43 PM
admin pls provide a bigger test case.....

Hello. I'm almost sure that

lutyj @ 1 Oct 2011 10:08 PM
Hello. I'm almost sure that there is a test with n=0 (which is not allowed by the statement).

what happened if n<(sum of

titia @ 1 Oct 2011 10:59 PM
what happened if n<(sum of xi) or n>(sum of yi)?

@admin should we assume xi

codeprav @ 2 Oct 2011 01:44 AM
@admin should we assume xi

@admin , should we assume xi

codeprav @ 2 Oct 2011 01:45 AM
@admin , should we assume xi

@admin , is xi

codeprav @ 2 Oct 2011 01:45 AM
@admin , is xi

is (xi

codeprav @ 2 Oct 2011 01:46 AM
is (xi

@admin ahould we assume xi

codeprav @ 2 Oct 2011 01:47 AM
@admin ahould we assume xi less than yi always, and chef need to distribute the work to all his team members

@admin my solution should

jitendra_theta @ 2 Oct 2011 10:49 AM
@admin my solution should give time limit.. why it is giving wrong answer.. i have checked it for many test cases

Can someone suggest why my

codersrikant @ 2 Oct 2011 05:15 PM
Can someone suggest why my code is saying TLE ? #include #include int findNoOfWays(int noOfDishesRemaining, int chef, int totalChef, int *min, int *max) { int noOfWays = 0; if (noOfDishesRemaining == min[chef]) { noOfWays = 1; } else if (noOfDishesRemaining > min[chef]) { int factor; if(max[chef] > noOfDishesRemaining) factor = noOfDishesRemaining; else factor = max[chef]; while (factor >= min[chef]) { if ((chef + 1) < totalChef) noOfWays += findNoOfWays(noOfDishesRemaining - factor, chef+1, totalChef, min, max); else { if(noOfDishesRemaining <= max[chef]) noOfWays += 1; break; } factor--; } } return noOfWays; } int main() { int noOfTestCases; scanf("%d", &noOfTestCases); while (noOfTestCases > 0) { int noOfDishes, noOfChefs; int *min, *max, i, noOfWays; scanf("%d", &noOfDishes); scanf("%d", &noOfChefs); min = (int *)malloc(sizeof(int) * noOfChefs); max = (int *)malloc(sizeof(int) * noOfChefs); for (i = 0; i < noOfChefs; i++) { scanf("%d", &min[i]); scanf("%d", &max[i]); } noOfWays = findNoOfWays(noOfDishes, 0, noOfChefs, min, max); printf("%dn", noOfWays); } return 0; }

@friend please some one tell

codeprav @ 2 Oct 2011 05:36 PM
@friend please some one tell me , does every team members has yo be given atleast some task as specified by x[i]

@codersrikant : you are not

taneja_stud @ 2 Oct 2011 07:06 PM
@codersrikant : you are not allowed to post codes here.......btw in your while loop you are not decreasing the noOfTestCases...

@admin Is it possible that

the123abhishek @ 2 Oct 2011 08:39 PM
@admin Is it possible that xi>yi

please someone tell me....is

the123abhishek @ 2 Oct 2011 09:27 PM
please someone tell me....is it possible that xi>yi and if every team member needs to be given some task as specified by xi

Correct Answer Execution

moskupols @ 2 Oct 2011 10:28 PM
Correct Answer Execution Time: 1.16 so strange...

@tanjea_stud : thanks for

codersrikant @ 2 Oct 2011 11:09 PM
@tanjea_stud : thanks for your suggestion. :)

hey...Anyone knows how 2 see

prgcode955 @ 3 Oct 2011 12:46 AM
hey...Anyone knows how 2 see the solution(code) of any user....

@prgcode955 if In between the

vinaybajaj2610 @ 3 Oct 2011 03:07 AM
@prgcode955 if In between the contest you are able to see other person code than what is the point of contest....there is no way of seeing other person's code till the contest ends :) :)

if xi is greater than yi ,

codeprav @ 3 Oct 2011 08:13 AM
if xi is greater than yi , then no of ways is 0? and again if sum of the xi over all i is greater then the number of jobs to be done then also no of ways is 0? please tell me if i am wrong or right?

i have tried a number of

cool_toad @ 4 Oct 2011 08:46 AM
i have tried a number of cases, all of which seem to give the correct output. @admin could you provide some other input values which could help in detecting the bug in my code?

Recursive DP TLE!!! Iterative

ridowan007 @ 4 Oct 2011 12:00 PM
Recursive DP TLE!!! Iterative AC!!! :-S

do we also need to take care

vineetdesai @ 4 Oct 2011 03:11 PM
do we also need to take care of the constraints in our program?

The same code with C++ gcc

shivmitra @ 4 Oct 2011 05:22 PM
The same code with C++ gcc 4.0.0-8 got TLE and with C++ gcc 4.3.2 got AC ... what sort of amazing optimization could the compiler have done so as to cause this... In case gcc 4.3.2 is much better then gcc 4.0.0-8 please remove that option from list ..

can any one explain this

eng_john @ 4 Oct 2011 07:28 PM
can any one explain this statement " the number of ways of distributing the work mod 1000000007" ?

could someone tell me whether

cool_toad @ 4 Oct 2011 08:22 PM
could someone tell me whether storing the "number of ways of distributing the work" in 'long int' works or not?

@admin Can you provide more

amey9004 @ 4 Oct 2011 09:43 PM
@admin Can you provide more test cases?. My solution gives correct output of everything I tried. But on submission its giving wrong answer. Also the code works fine even on the paper. Then why is it giving wrong answer on submission?

There is something weird with

skorknure @ 5 Oct 2011 08:49 AM
There is something weird with this TLE result... stupid memo-based DP gets TLE having <0.1s on local maxtests. I almost never had any problem with recursion memo, especially on such an easy problems.

plz tell me the answer for

gn13 @ 5 Oct 2011 04:12 PM
plz tell me the answer for n=100 m=100 xi=0 for all m and yi=100 for all m

skorknure, i had the same

blitzgren @ 5 Oct 2011 10:06 PM
skorknure, i had the same problem but it was magically fixed when i compiled under C++ 4.3.2 (if you are using C++) instead of 4.0.0-8 i agree with shivmitra, i was really scratching my head trying to figure out what my TLE was when max case (50 cases, all 100,100) ran in under a second on my machine.

@gn 13 for ur case the answer

ritesh_gupta @ 6 Oct 2011 12:45 AM
@gn 13 for ur case the answer will be 703668401

@admin does xi need to be

ridder @ 6 Oct 2011 08:15 PM
@admin does xi need to be smaller than yi everytime.... @all-what is the output for n=100, m=100, xi=0 & yi=100 for each m...?? i think 703668401 is incorrect for that case

@admin : could you please

cool_toad @ 6 Oct 2011 09:03 PM
@admin : could you please check my solution. I have tried every possible combination, but still it says wrong answer. I don't know whats wrong with the code, it gives the correct output for every case I tried, including the case for n=100 m=100 xi=0 for all m and yi=100 for all m (answer: 703668401). I have wasted a lot of time in this problem...

@admin : could you please

cool_toad @ 6 Oct 2011 09:04 PM
@admin : could you please check my solution. I have tried every possible combination, but still it says wrong answer. I don't know whats wrong with the code, it gives the correct output for every case I tried, including the case for n=100 m=100 xi=0 for all m and yi=100 for all m (answer: 703668401). I have wasted a lot of time in this problem...- http://www.codechef.com/viewsolution/690021

I am also getting same

mkagenius @ 6 Oct 2011 10:27 PM
I am also getting same answer as "cool_toad" but i am not getting wrong_answer rather I am getting a picture of a watch and "time limit exceeded" but It gives result very fast in my computer ....I think within minutes...

hi admin is it possible to

vineetdeoraj87 @ 6 Oct 2011 11:04 PM
hi admin is it possible to get a "wrong answer" output if my solution is crossing the time limit? Or surely my logic is wrong?? coz i tested on many inputs

@mkagenius the time limit is

vineetdeoraj87 @ 6 Oct 2011 11:05 PM
@mkagenius the time limit is just 1second.

very strict time limit

mkagenius @ 7 Oct 2011 12:06 AM
very strict time limit indeed.

@cool_tOad, chEcK tHAT uR

bodmas @ 7 Oct 2011 05:42 AM
@cool_tOad, chEcK tHAT uR modulo oPeRAtiOns are PRopERly donE, i.e. uR metHod alWays reTuRnS a vAlUe lESs thaN the GIVEn mOdulo.

wow, solved first problem

durgesh333 @ 7 Oct 2011 04:04 PM
wow, solved first problem using DP ,DP ROCKS :-)

" the number of ways of

drohit @ 7 Oct 2011 06:35 PM
" the number of ways of distributing the work mod 1000000007" can someone plzzzzzz tell me what the above line means and its use? sorry if i sound too dumb!

The time limit exceeded when

NR @ 7 Oct 2011 07:11 PM
The time limit exceeded when I used long long .... It got accepted when I used int instead of long long ..... Wasted a hell amount of time with the algorithm part instead of long long to int one...... This goes quite frustating ....

Is it necessary that each

SITZ @ 8 Oct 2011 11:19 AM
Is it necessary that each cook gets assigned at least xi number of dishes or some of them can be skipped ?

My n^3 iterative dp solution

imtiaz_cuet @ 8 Oct 2011 01:31 PM
My n^3 iterative dp solution was getting TLE because I used long long in C++ now its accepted and execution time 1.16 :O

what should be the answer

will_quotient @ 8 Oct 2011 07:05 PM
what should be the answer when total number of dishes to be distributed are greater than the total maximum capacity of all the chefs ??

yes, i got it!

bodmas @ 8 Oct 2011 09:15 PM
yes, i got it!

got it !!!! after long

aayush123 @ 9 Oct 2011 05:55 PM
got it !!!! after long struggle... :))

Can anybody tell me what to

aamandeep @ 9 Oct 2011 10:38 PM
Can anybody tell me what to print if the constraints are not satisfied.??????

Got accepted with my DP n^3

niquefa_diego @ 10 Oct 2011 06:46 AM
Got accepted with my DP n^3 and using long long :D

Why i don't see the button

tyamgin @ 11 Oct 2011 04:52 PM
Why i don't see the button "submit" ?

My problem was that i was

tmarice @ 11 Oct 2011 07:56 PM
My problem was that i was intensive use of mod operation. When i did only n^2 such operations instead of n^3, it passed.

Can anyone tell me what was

dinemont @ 12 Oct 2011 12:01 PM
Can anyone tell me what was wrong in my solution? http://www.codechef.com/viewsolution/700008

Any one of the successful

cupidvogel @ 30 Oct 2011 08:01 PM
Any one of the successful solution submitters for this problem, can you please explain the logic of solving? I am trying to do it by finding coefficient in the binomial expansion (the usual method), but it is taking too much time for the polynomial multiplications to occur.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions