SEQCOUNT - Editorial

xcwgf666 · March 30, 2014, 2:12pm

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 (a₁, a₂, …, a_K). Let’s denote the sum a₁ + a₁ + … + a_K by N.
We know that a₁ < a₂ < … < a_K. So, we can obtain a sequence (b₁, b₂, …, b_K) of natural numbers, where:

b₁ = a₁

b_i = a_i - a_i-1 for i in the range from 2 to K.

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

Then, let’s reconstruct the sequence (a₁, a₂, …, a_K) using the sequence (b₁, b₂, …, b_K). We obtain:

a₁ = b₁

a₂ = b₁ + b₂

a₃ = b₁ + b₂ + b₃

… and so on …

a_k = b₁ + b₂ + … + b_k

Here we see that b₁ occurs K times in N, b₂ occurs K-1 times in N, …, b_K occur once in N.

And now, we can have a DP: F[i][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 (a₁, a₂, …, a_K) 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

kevind · March 30, 2014, 2:23pm

How is complexity nk? Shouldn’t it be nd*k ?

xcwgf666 · March 30, 2014, 4:52pm

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

kevind · March 30, 2014, 9:06pm

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

xcwgf666 · March 31, 2014, 6:06pm

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