PROBLEM LINK:Author: Lalit Kundu DIFFICULTY:EASY – MEDIUM PREREQUISITES:Combinatorics PROBLEM:Given three positive integers N, L and R, find the number of nondecreasing sequences of size at least 1 and at most N, such that each element of the sequence lies between L and R, both inclusive. QUICK EXPLANATION:Number of nondecreasing sequences of size exactly K will be Choose(K + R  L, K). Where Choose(N, R) is number of ways to choose R elements from N distinct elements. EXPLANATION:Let us assume that our nondecreasing sequence is of length K, i.e in other terms the sequence a[1], a[2], a[3] ….. a[K] and a[i] <= a[i+1] and L <= a[i] <= R for each i. Subtask 1: We can solve this by using DP. Make a dp[][] array where dp[i][j] stores number of nondecreasing sequences ending with j and are of length i. Subtasks 2 & 3: Now let us consider that there are K red balls lying in a row. Now for each i, add a[i+1] – a[i] blue balls between i’th red ball and i+1’th red ball in the row. Add a[1] blue balls before 1st red ball and P – a[K] blue balls after K’th red ball in the row. Few observations:
So total number of sequences will be equal to total number of permutations. The total number of permutations of K red balls and P blue balls in a row is a standard result which is equal to Choose(K + P, K). This much solution is enough to solve the second subtask. Iterate through each of K between 1 and N and add Choose(K + P, K) to the answer. Actually we can reduce this summation to single term to solve subtask 3. The summation is Choose(P + 1, 1) + Choose(P + 2, 2) ….+ Choose(P + N, N). Add and subtract Choose(P + 1, 0) to the summation, which shouldn’t change the value of the sum. Choose(P+1, 1) + Choose(P+1, 0) = Choose(P + 2, 1) (Since it is known that Choose(N, R) + Choose(N, R – 1) = Choose(N + 1, R)). So the final answer is Choose(P + N + 1, N) – 1. You can find the best ways to calculate Choose(N, R) mod P here. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 11 Apr '15, 19:12

This result is actually known as Hockey Stick Theorem (Christmas Stocking Theorem), Explained here: answered 13 Apr '15, 16:54

This is insane. You make me question my intelligence by putting this in the "Easy" section answered 13 Apr '15, 18:17

This problem is similar to the problem of finding the number of ways to reach the point (m,n) from (0,0) when you can go only to the right or down. answered 13 Apr '15, 16:26

@bhavesh_munot "Distributing <=K things, to N people, is same as distributing exactly K things, to (N+1) people". This is because if we have x1 + x2 + x3 +... + xk < = n, then we can set up a dummy variable 's', such that it take whatever value is left in the sum to equate it to n. For example, if x1 + x2 + .. xk is 3 and n is 5, the value of the dummy variable would be 2. And in this way, we would get the total number of ways. This is equivalent to x1 + x2 + x3 +... + x(k+1) = n. answered 13 Apr '15, 17:31

Another way to derive $\sum_{i=0}^{N}\binom{i+p}{i} = \binom{N+p+1}{N}$ would be to realise that $\binom{i+p}{i}$ is number of ways to reach cell numbered $(i,p)$ beginning from $(0,0)$ when you can only more down or right*. Now, each path that reaches violet cell passes through green cells and then there is a unique way to reach violet cell from the green cell. So, we can say number of ways to reach violet cell is sum of number of ways to reach green cells. *Google the proof if not able to derive. answered 13 Apr '15, 17:49

Even after using Lucas theorem, I got 20 pts only. Solution link: http://www.codechef.com/viewsolution/6746781 Then I found the other way, but still reach 70. :( Solution Link: http://www.codechef.com/viewsolution/6746860 What was my mistake? answered 13 Apr '15, 16:07
Your solution is O(N) which is bad.
(13 Apr '15, 16:24)
@alexvaleanu Thanks!! A small mistake costed 50 pts. ;(
(13 Apr '15, 21:29)

Can anyone tell me what is the difference between the below 2 cases:
solution link: http://www.codechef.com/viewsolution/6773053 case 2: Got 100 points
solution link: http://www.codechef.com/viewsolution/6773023 answered 13 Apr '15, 17:56
c might get negative and c%MOD will still be negative. if you do (c+MOD)%MOD, it'll give positive.
(13 Apr '15, 17:58)
Thank you........ Didn't thought about this case. In whole contest , I was busy in optimizing my code.
(13 Apr '15, 19:31)
I was doing tge same mistake earlier. But then i realised it for good
(13 Apr '15, 22:34)

although using same formula .it was taking time O(n*t);gave me TLE ,please help. ps i got 50 points http://www.codechef.com/viewsolution/6742999 answered 13 Apr '15, 20:26

I used the concept of fermat from here(accepted answer on this page), still it showed TLE for the last subtask. This is the link to my solution. Please answer what optimization do i need to perform here? Or is it the case that this approach is slower in particular compared with Lucas(the one explained in the editorial)? If that's the case, what's the reason of it being slow as i'm unable to see any? answered 13 Apr '15, 20:57

Thanks for the problem. Learned a new thing. Lucas theorem answered 13 Apr '15, 23:18

A non Lucas way of getting AC .. Runs in 0.14s and 10.7M .. A bit complicated but faster (and the precomputation is the same). http://www.codechef.com/viewplaintext/6776710 answered 14 Apr '15, 19:12

Can Anyone help me!!!? Why is the last subtask wrong? I only used extended_euclid. Is Lucas's algorithm different from it? http://www.codechef.com/viewsolution/6776631 Please tell me my mistake. answered 14 Apr '15, 19:49

Hi @Adury Surya Kiran/Editors, I wanna thank you for putting up such a nice Editorial. You have explained everything in detail and I believe it must have taken you a long time to make this editorial. You have turned something complicated and ugly looking into a simple and beautiful solution. :) Thanks again. :) Rohit answered 15 Apr '15, 12:32

Hi All, I am just a newbie here. I worked on this problem for quite a lot of time. Alas, no result! Then I observed after the solutions were out, that most of the solvers of this problem had used Lucas theorem. The theorem I had not heard of, until seeing this editorial and a couple of solutions. After knowing that this problem needs something that I am missing, the only way I worked was calculating the outputs of some test cases manually and trying to figure some kind of relationship between the inputs and output which came in a form of some series. Though i found a relationship, it was too complex. Of course, I being a newbie, I could not even think like those experts who solved this. My question is how can one develop the "instinct" to solve such problems, the "instinct" to apply Lucas Theorem ? I know its from practice, but unless I know what Lucas theorem is,I cannot imagine how to solve such problem. And its not the problem with Lucas theorem. Today it was Lucas theorem, tomorrow it maybe another one. So I am asking about the way how can one approach such problems. Please can you guide on what all to know before going deeper into competitive programming ,where can I get information on such things(such as approaches/theorems etc) ? answered 15 Apr '15, 19:55

My code TLE C++ on 4.3.2 and AC on C++ 4.9.2. Why is it so? answered 18 Apr '15, 15:08

I am getting a "SIGSEGV" error in the last sub task. Can anyone please help ? My solution is :My Solution
link
This answer is marked "community wiki".
answered 20 Mar '16, 21:40

I can't believe I reached the final answer myself!! But had to take help to calculate choose(n,r) from tester's solution, for third subtask(Lucas theorem). If modulus was $10^9+7$ instead of $10^6+3$ , then what is the method to calculate $choose(n,r)$ where $1<=n,r<=10^9$ ? answered 19 Jul '16, 17:05

If anyone is not clear with the formula, check this :https://www.youtube.com/watch?v=UTCScjoPymA answered 26 Oct '17, 08:39
