TOOMANYLIS Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

2906

PREREQUISITES:

None

PROBLEM:

You are given 2 integers N and M. You also have an empty set S.

Consider an array A of length N such that 1 \leq A_i \leq M for each 1 \leq i \leq N (there are M^N such arrays in total).

For each of these M^N arrays, insert all of its longest non-decreasing subsequences into S.

Output the size of S. Since the size of S might be large, output it modulo 10^9+7.

Note that since S is a set, it stores only distinct values. For example, when N = 3 and M = 2, the sequence [1, 1] is a longest non-decreasing subsequence for both A = [1, 2, 1] and for A = [2, 1, 1] — however, it will only be present once in S.

EXPLANATION:

Observation: All the non-decreasing sequences greater than or equal to the length of \lceil \frac{n}{m} \rceil belongs to the set.

Here since we only have m numbers so some number would atleast appear \lceil \frac{n}{m} \rceil times so minimum length of non-decreasing sequences would be \lceil \frac{n}{m} \rceil.

Hence our answer would be the count of all non-decreasing sequences of length \geq \lceil \frac{n}{m} \rceil since some element would appear with frequency \geq \lceil \frac{n}{m} \rceil, thus given any LIS of length greater than or equal to this, it’s possible to construct a full sequence.

Thus to count the number of non decreasing sequences, we just need to fix the frequencies of each element. In order to do this we can represent this as a multiplication of polynomials.

\underbrace{(1 + x^1 + x^2....)}_\text{$x^i$ denotes using $i$ units of 1} \times \underbrace{(1 + x^1 + x^2....)}_\text{$x^i$ denotes using $i$ units of 2} \times.....\times\underbrace{(1 + x^1 + x^2....)}_\text{$x^i$ denotes using $i$ units of m} \\~\\ = \frac{1}{(1-x)^{m}}

Here in the final product of the above expression, the coefficient of say x^j, would denote the number of non-decreasing subsequences of j length.
So our answer would be sum of coefficients of x^y,x^{y+1}....x^n, where y = \lceil \frac{n}{m} \rceil

Now coefficient of x^i in (1-x)^{-m} is:

\binom{m+i-1}{i} = \binom{m+i-1}{m-1}

Thus our answer is

\binom{m+y-1}{m-1} + \binom{m+y}{m-1} + .....+ \binom{n+m-1}{m-1}

In order to solve this we use the following property of combinations:

\binom{A}{B} + \binom{A}{B+1} = \binom{A+1}{B+1}

Now adding and subtracting \binom{m+y-1}{m}, we get

\binom{m+y-1}{m-1} + \binom{m+y-1}{m} + \binom{m+y}{m-1} + .....+ \binom{n+m-1}{m-1} - \binom{m+y-1}{m}

Using property above repeatedly ,we get our final answer as:

\binom{m+n}{m} - \binom{m+y-1}{m}

TIME COMPLEXITY:

O(log(N+M)), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2

Why is this true? Can you give a brief proof?

1 Like
3

Sample Input #4: 4 2
Sample Output #4: 12
However, there are 14 nondecreasing subsequences:
1: 1
2: 1 1
3: 1 1 1
4: 1 1 1 1
5: 1 1 1 2
6: 1 1 2
7: 1 1 2 2
8: 1 2
9: 1 2 2
10: 1 2 2 2
11: 2
12: 2 2
13: 2 2 2
14: 2 2 2 2

4

You can never have an LIS with just 2. Note that it is the longest increasing subsequence of all possible arrays, not all increasing sequences of all arrays

5

Lets say there is no number that appears atleast ceil(n/m) times. Since n sized length can be partitioned into m sized blocks with atleast one block ceil(n/m) times. We have m numbers so let’s put every number in separate block in order to form an LIS. Now since there is one block atleast with size ceil(n/m) and no number appears this many times => there some places cannot be filled . There we won’t be able to complete an LIS of length n. This is a contradiction.
Therefore some number must appear atleast ceil(n/m) times as an lowerbound to make sure every time we can construct a valid sequence of length n.

6

how does this equation reduce to this 1/(1-x)^m?
It looks like GP on infinite series… but why infinite when units are limited to m?

7

1+x+x^2+x^3.... = 1/(1-x)

8

But this series is supposed to stop at x^m , isn’t it? Why considering it infinite series?

9

Here’s the author’s construction. It looks a bit long but it’s pretty simple and quite easy to visualize. For ease of writing I’ll use LIS to denote longest non-decreasing subsequence.

First note that a non-decreasing sequence is described by the number of times each element appears in it.
So, consider a non-decreasing sequence S where i appears a_i times.

We have the following observations:

  • For each 1 \leq i \leq M, placing a_1 + a_2 + \ldots + a_{i-1} copies of i to the left of the sequence doesn’t increase the length of the LIS.
  • For each 1 \leq i \leq M, placing a_{i+1} + a_{i+1} + \ldots + a_M copies of i to the right of the sequence doesn’t increase the length of the LIS.
  • Doing both of the above at the same time for a given i doesn’t increase the length of the LIS.

Obviously, to make sure the extra elements we add don’t create issues within themselves, they can be placed in descending order in the prefix and in descending order in the suffix.

How long is the sequence we created?

  • The original sequence has length a_1 + a_2 + \ldots + a_M
  • The added prefix has length a_1 + (a_1 + a_2) + (a_1 + a_2 + a_3) + \ldots + (a_1 + \ldots + a_{M-1})
  • The added suffix has length a_M + (a_M + a_{M-1}) + (a_{M} + a_{M-1} + a_{M-2}) + \ldots + (a_M + \ldots + a_2)

Add these three terms up and you get a sequence of length M\cdot(a_1 + a_2 + \ldots a_M), or M times the length of S, which also has S as one of its LIS.

Now when the sequence has length \geq \left \lceil\frac{N}{M} \right\rceil, you can see we obtain a sequence of length \geq M\cdot \left \lceil\frac{N}{M} \right\rceil \geq N, so just remove some stuff from the prefix or suffix till you’re left with a length N sequence. Since the length of S is \leq N it’s always possible to do this without disturbing S, and we’re done.

10

As the editorial (and my comment above) mentions, when considering non-decreasing sequences, it’s enough to only look at the frequencies of the elements involved. In other words, a non-decreasing sequence on the elements \{1, 2, \ldots, M\} can be described using M variables a_1, a_2, \ldots, a_M where each a_i is a non-negative integer.

The generating function \frac{1}{1-x} = 1 + x + x^2 + \ldots now describes each of these a_i — there is one way for a_i to be 0, one way for it to be 1, and so on. Multiplying this function M times and looking at the coefficients of the resulting series then gives us the number of non-decreasing sequences of a specific length.

As for finiteness, you have a point in that it is not really necessary to consider terms larger than x^N (not x^M), because after all we only care about sequences of length \leq N. However, doing it like that becomes quite messy because we don’t end up with the nice \frac{1}{1-x} form to algebraically manipulate.

Note that considering larger coefficients doesn’t actually affect our answer in any way, it simply gives us more information that we happen to not care about. The first N+1 coefficients of the resulting series are going to be the same either way, so why not go with the version that is easier to think about?

1 Like
11

1st and 11th aren’t longest)