BEHAPPY - Be Awesome As Barney Stinson

no tags 

Barney Stinson ;) is way too flirty. He has many girlfriends and he wants to keep all of them happy. He has M girlfriends. He bought N gifts for them. Now he knows that some girlfriends need more gifts and some need less. So he decided that he will give atleast Ai gifts and at most Bi gifts to his ith girlfriend. He has to give away all the N gifts. Tell us in how many different ways he can do this.


For each test case, first line contains two integers M and N, then follows M lines each having two integers Ai and Bi (1<=i<=M). Input ends with M and N both equal to 0 and that case should not be processed.


For each test case, output the number of different ways in which he can distribute those gifts in a single line.



3 5

0 1

1 3

1 4

0 0





Explanation: He can distribute 5 gifts in his 3 girlfriends in 6 different ways as follows (0 1 4), (0 2 3), (0 3 2), (1 1 3), (1 2 2), (1 3 1).


Constraints: 1<=M<=20, 1<=N<=100, 0<=Ai,Bi,<=100


hide comments
vaibhavk31: 2017-06-06 23:33:29

With Recursion ACC

shahzada: 2017-03-06 04:56:51

Should be moved to tutorial.

kshubham02: 2017-02-22 06:36:06

1. I realized after submitting that I am not even taking multiple test cases. Just inputting M and N once, no breaking at 0 0 or any of that shit.
2. Recursive Solution, should have been TLE because of exponential time complexity.
Result - AC in 0.00s.

So fellas, this question is not about getting ACs. Try and optimize your solutions. Hint - My 'correct' solution runs in O((A[i]-B[i])*M*N).
Spoiler - Think DP.
Suggestion - Try to implement bottom-up.

Last edit: 2017-02-22 06:37:52
vengatesh15: 2017-02-22 06:35:37

easy one AC in 1 go :-) simple recursion pass with 0.00s

.::Austin::.: 2016-07-09 14:07:20

wth!!! exponential passes in 0.00s

GAURAV CHANDEL: 2016-04-28 11:25:24

Be Happy .. with DP ..

kejriwal: 2016-01-16 17:49:31

solve to increase your confidence in dp :) !

hodobox: 2015-12-29 02:59:25

Solved it as knapsack in O( (Bi-Ai)*n*m )

Prateek Agarwal: 2015-12-04 08:58:35

No memoization required

spoj2121: 2015-12-01 17:43:28

weak test case backtracking gets AC in 0.00 sec..

Last edit: 2015-12-01 17:43:43

Added by:Ankit Kumar Vats
Time limit:0.490s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64