PROBLEM LINK:
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 = R – L. 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 : 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:
-
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. -
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. -
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. -
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.
