# 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, a, a …… 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 : dp[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 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 + a – a + a – a + ……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, a…a[K] and b, b…b[K]. Let i be the smallest index where a[i] != b[i]. Simply assume a = 0 and b = 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:

5 Likes

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.

11 Likes

Even after using Lucas theorem, I got 20 pts only.

Then I found the other way, but still reach 70. What was my mistake?

“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?

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.

2 Likes

This result is actually known as Hockey Stick Theorem (Christmas Stocking Theorem), Explained here:

5 Likes

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

1 Like

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:

![img]

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.
: http://www.sumoware.com/images/temp/xzjkqnhencanllac.png

*Google the proof if not able to derive.

1 Like

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

3 Likes

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);


case 2: Got 100 points

c=(Lucas(p,min(n,p-n),MOD)%MOD)-1;
pl((c)%MOD);


c might get negative and c%MOD will still be negative.
if you do (c+MOD)%MOD, it’ll give positive.

This is insane. You make me question my intelligence by putting this in the “Easy” section

3 Likes

Thank you… Didn’t thought about this case. In whole contest , I was busy in optimizing my code.

lol   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

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?

@alexvaleanu
Thanks!!

A small mistake costed 50 pts. ;(

I was doing tge same mistake earlier. But then i realised it for good

Thanks for the problem. Learned a new thing. Lucas theorem