You are not logged in. Please login at www.codechef.com to post your questions!

×

CSEQ - Editorial

6
3

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

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

This question is marked "community wiki".

asked 11 Apr '15, 19:12

adurysk's gravatar image

4★adurysk ♦
92852428
accept rate: 11%

edited 01 Jun '16, 20:22

admin's gravatar image

0★admin ♦♦
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.

link

answered 13 Apr '15, 16:05

karanaggarwal's gravatar image

3★karanaggarwal
2816
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) bhavesh_munot3★
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) grebnesieh7★

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

  1. Art of Problem Solving
  2. Wolfram Math World
link

answered 13 Apr '15, 16:54

avmnusng's gravatar image

5★avmnusng
1473
accept rate: 9%

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

link

answered 13 Apr '15, 18:17

jackx's gravatar image

2★jackx
312
accept rate: 0%

lol :D :D :D

(13 Apr '15, 19:54) vikky_codder6★

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.

link

answered 13 Apr '15, 16:26

yashv's gravatar image

4★yashv
696
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) rishavz_sagar3★

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

link

answered 13 Apr '15, 17:31

punjabidon's gravatar image

5★punjabidon
211
accept rate: 0%

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.

*Google the proof if not able to derive.

link

answered 13 Apr '15, 17:49

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 13 Apr '15, 17:50

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?

link

answered 13 Apr '15, 16:07

bhavesh_munot's gravatar image

3★bhavesh_munot
1981513
accept rate: 0%

edited 13 Apr '15, 16:08

Your solution is O(N) which is bad.

(13 Apr '15, 16:24) alexvaleanu4★

@alexvaleanu Thanks!!

A small mistake costed 50 pts. ;(

(13 Apr '15, 21:29) bhavesh_munot3★

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

link

answered 13 Apr '15, 17:56

vijay_khandal's gravatar image

3★vijay_khandal
1
accept rate: 0%

edited 13 Apr '15, 17:57

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) darkshadows ♦5★

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

(13 Apr '15, 19:31) vijay_khandal3★

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

(13 Apr '15, 22:34) eknoor2924★

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

link

answered 13 Apr '15, 20:26

oflocon502's gravatar image

4★oflocon502
1
accept rate: 0%

You don't use Lucas' theorem. O(N) is not optimal

(14 Apr '15, 19:52) alexvaleanu4★

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?

link

answered 13 Apr '15, 20:57

saurabhgpt's gravatar image

3★saurabhgpt
1
accept rate: 0%

edited 13 Apr '15, 21:30

Your solution is O(N). It should get TLE for the last subtask.

(14 Apr '15, 19:49) alexvaleanu4★

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

link

answered 13 Apr '15, 23:18

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

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

link

answered 14 Apr '15, 19:12

himanshujaju's gravatar image

6★himanshujaju
251310
accept rate: 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.

link

answered 14 Apr '15, 19:49

ak_sky's gravatar image

2★ak_sky
1
accept rate: 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

link

answered 15 Apr '15, 12:32

codedecode0111's gravatar image

5★codedecode0111
3201215
accept rate: 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) ?

link

answered 15 Apr '15, 19:55

madhusudan_k's gravatar image

2★madhusudan_k
1
accept rate: 0%

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

link

answered 18 Apr '15, 15:08

s24w's gravatar image

4★s24w
456
accept rate: 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

skpro19's gravatar image

3★skpro19
0
accept rate: 0%

edited 20 Mar '16, 21:41

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

link

answered 19 Jul '16, 17:05

prakhariitd's gravatar image

6★prakhariitd
1.1k211
accept rate: 10%

edited 19 Jul '16, 17:22

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

link

answered 26 Oct '17, 08:39

varun44540's gravatar image

2★varun44540
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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