GRUMPMA (Problem Code)

help
1

This is my code for GRUMPMA. Can someone tell me why is it wrong?

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{   
    int t;
    cin>>t;
    ll NUM=1000000007;
    while(t--){
        ll n,k,m;
        cin>>n>>k>>m;
        ll b[k+1]={0};
        b[0]=1;
        
        for(int i=0; i<n; i++){
            ll temp;
            cin>>temp;
            temp=temp%m;
            int j=0;
            
            while(j*m+temp<=k){
                b[0]=1;
                b[(j*m+temp)]=(b[(j*m+temp)]%NUM+b[(j*m+temp)-1]%NUM)%NUM;
                j++;
            }
        }
        cout<<b[k]<<'\n';
    }
    return 0;
}
2

Will fail for m = 1… once u update b[x] u are using same b[x] to update b[x+1] whereas it has to be the old one. Iterating j backwards will help fix this.

1 Like
5

Please explain the logic behind your code

6

Lets take k=2

1- without having an element for index 1, there’s no use of an element with index 2

2- If we have x elements that can fit index 1, and we get 1 element for index 2, then we can form x subsequence of length 2, lets store this as y

3-If we find some more elements suitable for index 1 after finding index an element for index 2, they are of no use until we get an element after that which is suitable for index 2

4-If we get an element for index 2 after all this, then the number of subsequences will be [(number of subsequences in step 2 ) + ((number of elements in step 1) + (number of elements in step 3))] = [(number of subsequence in step 2) + (number of elements suitable for index 1 encountered till now)]

5- I will update this new value for y and carry on same steps. {If you notice, its just adding number of ones encountered till now to y, or you can say adding x to y when we discover an element for index 2}

6- Now take an array of k elements, where k is say 4,
so we have to update a[i]=a[i-1] for a value of i if we encounter an element suitable for i th position in the subsequence

1 Like
7

can some one explain me the solution…

8

I have made an unofficial editorial for the problem. Check that.

1 Like
9

@aryan12 thanks…

10

Hey, the official editorial is available now.