CSEQ - Editorial

april15
combinatorics
cseq
dynamic-programming
easy-medium
editorial
lucas-theorem
maths

#1

PROBLEM LINK:

Practice
Contest

Author: Lalit Kundu
Tester: Sergey Kulik
Editorialist: Adury Surya Kiran

DIFFICULTY:

EASY – MEDIUM

PREREQUISITES:

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.

Subtask 1:

We can solve this by using DP. Make a dp[][] array where dp*[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[1][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.

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:

  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:

Author’s solution
Tester’s solution


#2

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.


#3

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. :frowning:

Solution Link: http://www.codechef.com/viewsolution/6746860

What was my mistake?


#4

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.


#5

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

  1. Art of Problem Solving
  2. Wolfram Math World

#6

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


#7

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][123]

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

*Google the proof if not able to derive.


#8

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


#9

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


#10

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


#11

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?


#12

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


#13

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


#14

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.


#15

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. :slight_smile:

Thanks again. :slight_smile:

Rohit


#16

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


#17

My code TLE C++ on 4.3.2 and AC on C++ 4.9.2. Why is it so?


#18

I am getting a "SIGSEGV" error in the last sub- task. Can anyone please help ?

My solution is :My Solution


#19

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 ?


#20

If anyone is not clear with the formula, check this -:https://www.youtube.com/watch?v=UTCScjoPymA