This is an unofficial editorial and I may have complicated or simplified the problem.
PROBLEM LINK:
DIFFICULTY:
Easy
PREREQUISITES:
Basic DP
PROBLEM:
You are given an array of N integers and two integers K and M. Find the number of subsequences of the array of length K such that:
S[i] % M = i % M (for each i from 1 to k)
You need to print the answer modulo (10 ^ 9) + 7
QUICK EXPLANATION:
We will maintain an array from 1 to k which will store the value of the number of subsequences of length 1 to k formed for each i from 1 to n. Here the time complexity will be O(n * k) which will give us a TLE. To overcome that, we need to optimize our approach a bit. This can be done by observations.
EXPLANATION:
We see that we don’t need the original array. All the operations are in the form of mod m. So our first step will be:
for each i from 1 to n
a[i] = a[i] % m;
Now, as we only need a single subsequence, we store the subsequence in an array of length k. So the next step will be:
for each i from 1 to k
seq[i] = i % m;
Now, here comes the observation part which leads to AC instead of TLE.
We see, that the same number in the subsequence is repeating itself periodically. The distance between two similar numbers is m. So we don’t take k iterations, we take (k / m) iterations, which leads to AC.
Now lets define the recursion of dp
Recursion of dp
Firstly, lets define dp[i].
dp[i] means the number of subsequences in the array till position j (from 1 to n) of the first i (from 1 to k) integers in the sequence.
Now for the recursive formula, I am taking an example:
For example a[i] = 3, m = 4, k = 3.
Now our seq array will be [1, 2, 3]
Thus,
as (a[i] % m == seq[3] % m)
Now, the new subsequences of length 3 will be formed will be all subsequences of length 2 formed before this index, which is stored in dp[2].
And not to forget that there are some subsequences already formed before this index
Thus,
dp[i] = dp[i - 1] + dp[i];
Thus,
for each i = start to 1 step m
dp[i] = dp[i - 1] + dp[i];
dp[i] = dp[i] % ((10 ^ 9) + 7);
Finally we arrive to the answer, which is dp[k].
Just be careful when m = 1.
TIME COMPLEXITY:
O(N * (K / M) ) per each test case
SOLUTION:
Always feel free to ask me any query about this editorial and rate this editorial on 5.
- Awful
- Bad
- Average
- Good
- Excellent
0 voters