UVa 10036 - Divisibility

It can be solved using 2d DP with the parameters as:

"i"- index of the array
"sum" - (Sum of the elements)%k

 Here recurrence can be defined as :

dp[i][sum]= max((dp[i+1][(sum+a[i])%k]) , (dp[i+1][(sum-a[i])%k]))

           where dp[i][sum] stores "1" if it would lead to dp[n][0] or else "0".

The tricky part of the question is that a[i] can be negative which can cause sum dimension to be negative..

But with some observation it can be solved easily by adding some value in sum and the modified recurrence would look like :

dp[i][sum]= max((dp[i+1][(sum+a[i]+z*k)%k]) , (dp[i+1][(sum-a[i]+z*k)%k]))

          where z=(a[i]/k)+1

Hence now sum can never be negative and it would easily compute the desired answer.

Base Case:

        -->Return "1" when i==n and sum=0.

        -->Return "0" when i>=n. 

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,k,a[MAX];
int dp[10005][105];

int solve(int i,int sum){
    if(i==n && sum==0)
        return 1;
    if(i>=n)
        return 0;
    if(dp[i][sum]!=-1)
        return dp[i][sum];
    int z=a[i]/k;
    z++;
    return dp[i][sum]=max((solve(i+1,(sum+a[i]+z*k)%k)) , (solve(i+1,(sum-a[i]+z*k)%k)));
}

int main(){
    int r,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    si(t);
    while(t--){
        clr(dp,-1);
        sii(n,k);
        f(i,0,n){
            si(a[i]);
        }
        if(solve(0,0))
            printf("Divisible\n");
        else
            printf("Not divisible\n");
    }

    return 0;
}