Editorialist: Aryan Agarwala
Problem link: ZIO 2019 Problem 1
Reduced problem statement:
Given a number K, you need to find the number of “special sequences”, which are non-empty sequences that fulfil the following properties:
1S[i]K
- S[i] is a multiple of S[i-1]
- All S[i] are distinct
The series can be of any length
There are three key observations to solving this problem:
1. The first observation in this problem is that the elements in the sequence will always be strictly increasing. That is, for all S[i], S[i]>S[i-1].
2. The second observation is that all special sequences can be created by merging smaller special sequences. The only rule for merging is that the first element of the second sequence must be divisible by the last element of the first sequence.
Example:
2 6 18 | 72 144 864
These sequences can be merged since 72 (the first element of the second sequence) is divisible by 18 ( the last element of the first sequence )
2 6 18 | 35 70 280
These sequences cannot be merged since 35 ( the first element of the second sequence ) is not divisible by 18 $(the last element of the first sequence )$
3. The third observation is an extension of the second. Merging two subsequences is dependent only upon the two numbers adjacent numbers that will be merged. We only need to check those two numbers for compatibility, the remaining elements of the sequence are irrelevant.
Using these three observations, we can create our solution in the form of a row with K columns. For simplicity, we can refer to the xth column as DP[x]
In this row, DP[x] represents the number of special sequences that start with the number x.
How do we build this table?
First, note that for any number x, there is at least one special subsequence containing that number ( the sequence of length = 1).
Second, we can use the concept of merging subsequences here. Consider the number x to be the first subsequence. Now, we just need to add the number of sequences where the first number is divisible by x ( which is the last element of the first subsequence ). This is simple! According to the third observation, We just need to add all DP[i] such that i is divisible by x.
Our final recurrence is:
⟹DP[x]=1+∑m=2⌊Kx⌋DP[xm]
The final answer is the sum of all DP[i] where 1iK:
∑i=1KDP[i]
Adding all of the DP states might be slightly tedious. In order to avoid this, you can simple use:
Answer =DP[1]2-1
PROOF
DP[1]=1+∑i=2KDP[i]
⟹2DP[1]=DP[1]+∑i=2KDP[i]+1
⟹2DP[1]-1=∑i=1KDP[i]
SOLVING A SUBTASK
Let us try this approach on the first subtask of this problem
K=15
DP[15]=1
DP[14]=1
DP[13]=1
DP[12]=1
DP[11]=1
DP[10]=1
DP[9]=1
DP[8]=1
DP[7]=1+DP[14]
DP[6]=1+DP[12]
DP[5]=1+DP[10]+DP[15]
DP[4]=1+DP[8]+DP[12]
DP[3]=1+DP[6]+DP[9]+DP[12]+DP[15]
DP[2]=1+DP[4]+DP[6]+DP[8]+DP[10]+DP[12]+DP[14]
DP[1]=1+∑i=215= 35
| DP | |
|---|---|
| 15 | 1 |
| 14 | 1 |
| 13 | 1 |
| 12 | 1 |
| 11 | 1 |
| 10 | 1 |
| 9 | 1 |
| 8 | 1 |
| 7 | 2 |
| 6 | 2 |
| 5 | 3 |
| 4 | 3 |
| 3 | 6 |
| 2 | 10 |
| 1 | 35 |
Answer =2DP[1]-1=69
Additionally, programmers can use the following code for reference:
#include <iostream>
using namespace std;
int main () {
int t;
cin>>t;
while(t--) {
int K;
cin >> K;
long long dp[K+1];
for (int x = K; x >= 1; x--) {
dp[x] = 1;
for (int m = 2; m <= (K/x); m++) {
dp[x] += dp[m*x];
}
}
cout << ((2 * dp[1]) - 1) << endl;
}
}