×

# CSEQ - Editorial

Author: Lalit Kundu
Tester: Sergey Kulik

EASY – MEDIUM

Combinatorics

# PROBLEM:

Given three positive integers N, L and R, find the number of non-decreasing 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 non-decreasing 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.
Summation of Choose(K + R - L, K) for all K between 1 and N (inclusive) will be Choose(N + R - L + 1, N) - 1.
In the question it is given that the answer should be printed mod (10^6+3) which is a prime number. Choose(N, R) mod P for N > P can be found by using Lucas Theorem.

# EXPLANATION:

Let us assume that our non-decreasing 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.
Let us replace each a[i] of the sequence with a[i] – L. Let P = RL. Now each a[i] satisfies the condition 0 <= a[i] <= P.

We can solve this by using DP. Make a dp[][] array where dp[i][j] stores number of non-decreasing sequences ending with j and are of length i.
If a[i] = j, and a[i - 1] = k, then k should be <= j. So dp[i][j] will be sum of dp[i – 1][k] such that k <= j.
Boundary case : dp1[j] = 1 for all j.
Calculate these values for all 1 <= i <= MAX_N and 0 <= j <= MAX_P. For each test case output the sum of dp[i][P] for all i.
Complexity = O(N * P) Where P = R - L.

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:

1. We can see that there will be exactly P blue balls in the row.
Proof: Total number of blue balls = a[1] + a[2] – a[1] + a[3] – a[2] + …..a[K] – a[K – 1] + P – a[K]. All the terms of sequence a[] will be cancelled out leaving us with P.

2. Two different sequences produce different permutations of red and blue balls.
Proof: Let us assume the two sequences are a[1], a[2]…a[K] and b[1], b[2]…b[K]. Let i be the smallest index where a[i] != b[i]. Simply assume a[0] = 0 and b[0] = 0. So there will be a[i] - a[i - 1] blue balls between i’th and i-1’th red balls in the first permutation and b[i] – b[i-1] blue balls between i’th and i-1’th red balls in the second permutation. Hence, the two permutations are different.

3. For each permutation of red and blue balls there exists a sequence which produces it.
Proof: The sequence can be generated this way, each a[i] will be equal to (total number of blue balls to the left of it). In this sequence a[i] will never be greater than a[i+1] because there any blue ball to the towards left of i’th red ball in the row will also be to the left of i+1’th red ball in the row. So the sequence is non-decreasing. As the total number of blue balls is P, the highest element of the sequence can be P. Hence all the elements lie in the range 0 to P.

4. Observations 2 and 3 are enough to say that the mapping between the sequences and the permutation of balls is a Bijection. You can read about Bijective functions here.

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)).
Now Choose(P + 2, 2) + Choose(P + 2, 1) = Choose(P + 3, 2).
Now Choose(P + 3, 3) + Choose(P + 3, 2) = Choose(P + 4, 3).
… So on till N’th term gives Choose(P + N + 1, N).

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

92852428
accept rate: 11%

19.8k350498541

 11 Distributing <=K things, to N people, is same as distributing exactly K things, to (N+1) people (1 extra dummy person). We can use this reduction, to directly get this result " Choose(N + R - L + 1, N) - 1" . The -1 is here because we need to distribute at least 1 thing, so we are removing the case of distributing 0 things. answered 13 Apr '15, 16:05 281●6 accept rate: 0% "Distributing <=K things, to N people, is same as distributing exactly K things, to (N+1) people". Why is this so? Can you let know the analysis? (13 Apr '15, 16:13) 3 ^ As he said, the extra person is a dummy. That is to say, the first n people will get some c (say) <= k things, the remaining (k - c) will go to the last person. There will be a case where the last guy gets everything, so we do -1 to get the right answer. (13 Apr '15, 17:51)
 5 This result is actually known as Hockey Stick Theorem (Christmas Stocking Theorem), Explained here: answered 13 Apr '15, 16:54 5★avmnusng 147●3 accept rate: 9%
 3 This is insane. You make me question my intelligence by putting this in the "Easy" section answered 13 Apr '15, 18:17 2★jackx 31●2 accept rate: 0% lol :D :D :D (13 Apr '15, 19:54)
 1 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 4★yashv 69●6 accept rate: 0% 1 @yashv, well predicted,a similar question was asked in May Lunch time.Link: http://www.codechef.com/LTIME24/problems/NWAYS (15 Jun '15, 16:02)
 1 @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 21●1 accept rate: 0%
 1 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, what we need is sum of number of ways to reach cells $(0,p), (1,p) ... (N,p)$, which is equivalent to number of ways to reach cell $(N,p+1)$ which is $\binom{N+p+1}{N}$. Visualise it this way: 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 3.0k●93●164●187 accept rate: 12%
 0 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 198●1●5●13 accept rate: 0% 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)
 0 Can anyone tell me what is the difference between the below 2 cases: case 1: I got 50 points- c=(Lucas(p,min(n,p-n),MOD)%MOD)-1; pl((c)%MOD);  solution link: http://www.codechef.com/viewsolution/6773053 case 2: Got 100 points c=(Lucas(p,min(n,p-n),MOD)%MOD)-1; pl((c)%MOD);  solution link: http://www.codechef.com/viewsolution/6773023 answered 13 Apr '15, 17:56 1 accept rate: 0% 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)
 0 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 1 accept rate: 0% You don't use Lucas' theorem. O(N) is not optimal (14 Apr '15, 19:52)
 0 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 1 accept rate: 0% Your solution is O(N). It should get TLE for the last subtask. (14 Apr '15, 19:49)
 0 Thanks for the problem. Learned a new thing. Lucas theorem answered 13 Apr '15, 23:18 893●2●11●35 accept rate: 10%
 0 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 251●3●10 accept rate: 0%
 0 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 2★ak_sky 1 accept rate: 0%
 0 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 320●1●2●15 accept rate: 0%
 0 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 1 accept rate: 0%
 0 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 4★s24w 45●6 accept rate: 0%
 0 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 3★skpro19 0 accept rate: 0%
 0 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 1.1k●2●11 accept rate: 10%
 0 If anyone is not clear with the formula, check this -:https://www.youtube.com/watch?v=UTCScjoPymA answered 26 Oct '17, 08:39 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,852
×2,214
×1,723
×1,220
×900
×186
×35
×34

question asked: 11 Apr '15, 19:12

question was seen: 11,725 times

last updated: 26 Oct '17, 08:39