GRUMPMA - Unofficial Editorial

editorial
1

This is an unofficial editorial and I may have complicated or simplified the problem.

PROBLEM LINK:

Contest
Practice

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:

My 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

3 Likes
2

Very good attempt to help us understand the solution through editorial.Thanks👍

4 Likes
3

Thanks man. It will really motivate me to make further editorials if they are delayed because of any reason.

5 Likes
4

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 .

CAN U PLEASE EXPLAIN THIS LINE?

3 Likes
5

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.
can someone explain the state of dp

2 Likes
6

which will store the value of the number of subsequences of length 1 to k formed for each i from 1 to n

So basically,

The array here I am talking about is the dp array.
So, dp[i] stores the maximum number of subsequences of length i, which adheres to the sequence stored in the seq array.

Eg: The seq array is [1, 2, 3];
So,
dp[1] will store the maximum number of subsequences which form [1].
dp[2] will store the maximum number of subsequences which form [1, 2].
dp[3] will store the maimum number of subsequences which form [1, 2, 3].

As we are storing this as we iterate through the original array a, I have written the statement like that.

2 Likes
9

mistakely!

2 Likes
12

@aryan12 I suggest u as a editorialist for this problem …
Thanks…

1 Like
13

Thanks for the comment. It will help me immensely in the future if I make any editorial.

14

can u help me link. Dont Know why getting TLE and how to do further Optimization.

1 Like
15

I don’t know about the TLE part, but your code will give WA even if you optimize the code. In you code, the part m == 1,
You are not inputting the array, and thus you will get a WA. I am working on the TLE part and will inform you as soon as I find it.

And also another mistake I found was that you need to iterate the dp array backwards because when m == 1, it is an edge case. Figure out that on your own.

16

i got AC now after putting m==1 condition after taking input . and i don’t think iteration from back or front matter as i am handling edge case.

1 Like
17

Achcha yaa, I forgot that you handled that edge case before only. Anyways, congrats on getting AC in that problem. But I am curious to know why you got a TLE there?

18

i just placed that if(m==1) condition after taking all inputs and my TLE turned into AC, may be getting TLE bcoz my code isnt giving any output for some “extra input” ( you know what it means).

19

@aryan12 did a really great job of explaining the solution in a very efficient way.
For more explained solution and facts regarding the problem, check out the official editorial.
Apology for the delay in posting official editorial guys, the editorial is available here at

1 Like