PROBLEM LINK:
Author: Sachin Yadav
Tester: Kishen Gowda
Editorialist: Dishank Goel
DIFFICULTY:
EASY
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given an array A of N non-negative integers and two integers K and M. Find the number of subsequences of array A of length K which satisfies the following property:
Suppose the subsequence is S = S_1S_2 \ldots S_K, then for all i such that 1 \leq i \leq K,
S_i \% M = i \% M
should hold true, where S_i denotes the i-th element of the subsequence, using 1-based indexing.
As the number of subsequences may be very large, output the answer modulo 1000000007.
QUICK EXPLANATION:
We maintain an array of length of K, where the ith index stores the number of subsequences of length i encountered till now which satisfies the given property. Initially the elements of array are zero. Now at each array element we update the array accordingly. The value at K^{th} position of this array will give us the answer.
EXPLANATION:
The key observation in the problem is that we can use the answer of A[n-1] to find the answer of A[n]. Since if we know how many subsequence are there of length n-1 which satisfy the given property, adding one more element to it will increase the count for n length by the answer of n-1. This is the basic idea behind a dynamic programming solution.
Let us imagine the subsequence of length K that we need to find as chunks of subarrays of length M joined together. For example, a valid subsequence that we need to count will be, for K = 10 and M = 4
{1,2,3,0,1,2,3,0,1,2}
Such subsequences will be picked from the original array A.
Now, consider the element A[i]. This element can be part of a subsequence and be in one of the chunks at position (A[i]\%M). Like in the above mentioned example. if A[i] = 5, A[i]\%M = 1 and it can be in chunk 1 (starting at 1st position) or chunk 2 (starting at 5th position) or chunk 3 (starting at 9th position), every time at 1st position.
But since we are working in mod M, we have to keep track of the length of longest subsequence that these elements are part of. Let’s call this acheived_length. achieved_length will be less than equal to K.
Now whenever we encounter an element A[i], it can be part of all the chunks present in the subsequence of length achieved_length.
The acheived_length will increase only when we encounter the right element to be placed at (achieved_length + 1).
We can maintain a dp array which will store the number of such subsequences of length i at it’s ith position.
To count the element A[i] in all the chunks, we increase the count in dp array for every possible occurence of A[i] in length 0 to achieved_length. Suppose if the element A[i] can be counted at position p in every chunk, then,
dp[p] = dp[p] + dp[p-1]
dp[m+p] = dp[m+p] + dp[m+p-1]
…
and so on till length achieved_length.
Do note that it’s better to traverse in reverse direction i.e update the chunk at right most position first because for M = 1, if you go in forward direction, once you update dp[p], you will be updating dp[p+1], where you will be counting the updated value instead of the old value of dp[p]. Going in reverse direction fixes this error.
We are adding the value of dp[p-1] to d[p] because this A[i] can be part of all those subsequences of length d[p-1] that have already been counted. And we do this for all the chunks.
Finally, dp[K] will have all total count of subsequences of length K that satisfy the mentioned property.
Time Complexity : O(N \times \lceil \frac{K}{M} \rceil )
SOLUTIONS:
Setter's Solution
#include<iostream>
#define MOD 1000000007LL
using namespace std;
int main()
{
int T; cin>>T;
while(T--)
{
int N, K, M; cin>>N>>K>>M;
int arr[N]; for(int i=0; i<N; i++){ cin>>arr[i]; arr[i]%=M; }
long long len[K+1]={0};
len[0]=1;
int last=1;
for(int i=0; i<N; i++)
{
int x=arr[i], y=last%M;
y=last-(y-x+M)%M;
if(y==last && last<K) last++;
for(int j=y; j>0; j-=M)
{
len[j]+=len[j-1];
if(len[j]>=MOD) len[j]-=MOD;
}
}
cout<<len[K]<<"\n";
}
return 0;
}
Tester's Solution
M = 10**9+7
for _ in range(int(input())):
n,k,m=(int(s) for s in input().split())
l = [int(s)%m for s in input().split()]
ans = [0]*(k+1)
i = 1
for j in range(n):
mov = 0
just = 0
if (i%m+1)%m==l[j] and i<k:
if ans[i]!=0:
just=1
mov = 1
w = i - (i%m-l[j])%m
while w>=1:
if w==1:
ans[w]+=1
else:
ans[w]+=ans[w-1]
w-=m
if mov:
i+=1
if just:
ans[i] = ans[i-1]
print(ans[k]%M)
Editorialist's Solution
mod = 10**9 + 7
for i in range(int(input())):
n,k,m = tuple(map(int, input().split()))
a = list(map(int, input().split()))
ans = [0 for i in range(k+1)]
ans[0] = 1
curr_ending = 1
for i in range(n):
mod_a = a[i]%m
start = curr_ending - (curr_ending%m - mod_a)%m
if(mod_a == curr_ending%m and curr_ending<k):
curr_ending += 1
for i in range(start, 0, -m):
ans[i] += ans[i-1]
if(ans[i] > mod):
ans[i] = ans[i] - mod
print(ans[k])