SEQCOUNT - Editorial

dynamic-programming
easy-medium
ltime10
seqcount

#1

Problem link: contest practice

Difficulty: Easy-Medium

Pre-requisites: DP

Problem: Count the number of increasing sequences of K natural numbers, where adjacent numbers differ no more than by D, the first number is not greater than D and the total sum of all numbers in the sequence equals to N.

Explanation:

Let’s denote the original “nice” sequence by (a1, a2, …, aK). Let’s denote the sum a1 + a1 + … + aK by N.
We know that a1 < a2 < … < aK. So, we can obtain a sequence (b1, b2, …, bK) of natural numbers, where:

b1 = a1

bi = ai - ai-1 for i in the range from 2 to K.

In this new sequence bi > 0 will be hold for every i from one to K. We will call the values of bi b-values.

Then, let’s reconstruct the sequence (a1, a2, …, aK) using the sequence (b1, b2, …, bK). We obtain:

a1 = b1

a2 = b1 + b2

a3 = b1 + b2 + b3

… and so on …

ak = b1 + b2 + … + bk

Here we see that b1 occurs K times in N, b2 occurs K-1 times in N, …, bK occur once in N.

And now, we can have a DP: F[j]* corresponds to the number of ways to make the sum i using an increasing sequence of j natural numbers. The recalculation is quite simple here: when we add the j-th number to the sequence (having j-1 numbers already added) we know that its’ b-value will occur K-j+1 times in the final sum (in other words, in N). So, we can get to (i, j) from (i - (K - j + 1), j - 1), (i - 2 * (K - j + 1), j - 1), (i - 3 * (K - j + 1), j - 1), … , (i - D * (K - j + 1), j - 1). The value of the position (i - D * (K - j + 1), j - 1) is the last possible summand for the (i, j) DP state, because the differences larger than D * (K - j + 1) means larger adjacent number differences in the sequence (a1, a2, …, aK) that is prohibited by the constraint on D.

The final time complexity is O(N*K). At the first glance, it’s too much for this problem. But we can check in the beginning, whether the answer is zero or not by taking the smallest possible sum of K natural numbers and comparing it with N. If this is sum is greater than N, we can output zero and quit immediately. Otherwise the time complexity reduces to no more than O(N * sqrt N) that is OK.

Setter’s solution: link

Tester’s solution: link


#3

We can obtain O(NK) because anytime we need to get the last D integers that has the same value of sum_of_sequence mod (K - j + 1) as i. So, we can handle an array, where we’ll store the sum of the last D integers with this property for every possible remainder from the division by (K - j + 1) (see setter’s solution). This simple trick gives us O(NK).


#4

How do you get that “last D integers that has the same value of sum_of_sequence mod (K - j + 1) as i” ?


#5

It’s so because we take the following states for the final sum: (i - (K - j + 1), j - 1), (i - 2 * (K - j + 1), j - 1), (i - 3 * (K - j + 1), j - 1), … , (i - D * (K - j + 1), j - 1). Subtracting (K - j + 1) will not change the remainder modulo (K - j + 1).