10036 - Divisibility

[lbv]

Is there any algorithms faster than DP on index and mod ??

I don't know of any strategy other than one with O(NK) time complexity, but it can be done using only O(K) space, which may speed up the implementation, if that's what you want.

this is my code :

Please don't post AC code in the forums. I invite you to read this post; it's a little old but it contains useful information that is still relevant today.

[just_yousef]

Is there any algorithms faster than DP on index and mod ??

I don't know of any strategy other than one with O(NK) time complexity, but it can be done using only O(K) space, which may speed up the implementation, if that's what you want.

this is my code :

Please don't post AC code in the forums. I invite you to read this post; it's a little old but it contains useful information that is still relevant today.

Code Deleted

[sabbir_alam_ufo]

Getting TLE.
Is there anything wrong in my dp function ?

Code: Select all

#include<iostream>
#include<sstream>
#include<string>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cctype>
#include<set>
#include<bitset>
#include<algorithm>
#include<list>

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>

using namespace std;
#define print1(a)    cout<<a<<endl
#define print2(a,b) cout<<a<<" "<<b<<endl
#define print3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define oo          (1<<30)
#define PI          3.141592653589793
#define pi          (2.0*acos(0.0))
#define ERR         1e-5
#define PRE         1e-8
#define SZ(s)       ((int)s.size())
#define LL          long long
#define ISS         istringstream
#define OSS         ostringstream
#define VS          vector<string>
#define VI          vector<int>
#define VD          vector<double>
#define VLL         vector<long long>
#define SII         set<int>::iterator
#define SI          set<int>
#define mem(a,b)    memset(a,b,sizeof(a))
#define fr(i,a,b)   for(i=a;i<=b;i++)
#define frn(i,a,b)  for(i=a;i>=b;i--)
#define fri(a,b)    for(i=a;i<=b;i++)
#define frin(a,b)   for(i=a;i>=b;i--)
#define frj(a,b)    for(j=a;j<=b;j++)
#define frjn(a,b)   for(j=a;j>=b;j--)
#define frk(a,b)    for(k=a;k<=b;k++)
#define frkn(a,b)   for(k=a;k>=b;k--)
#define frl(a,b)    for(l=a;l<=b;l++)
#define frln(a,b)   for(l=a;l>=b;l--)
#define REP(i,n)    for(i=0;i<n;i++)
#define EQ(a,b)     (fabs(a-b)<ERR)
#define all(a,b,c)  for(int I=0;I<b;I++)    a[I] = c
#define CROSS(a,b,c,d) ((b.x-a.x)*(d.y-c.y)-(d.x-c.x)*(b.y-a.y))
#define sqr(a)      ((a)*(a))
#define FORE(i,a)   for(typeof((a).begin())i=(a).begin();i!=(a).end();i++)
#define typing(j,b) typeof((b).begin()) j=(b).begin();
#define BE(a)       a.begin(),a.end()
#define rev(a)      reverse(BE(a));
#define sorta(a)    sort(BE(a))
#define pb          push_back
#define popb        pop_back
#define mp          make_pair
#define round(i,a)  i = ( a < 0 ) ? a - 0.5 : a + 0.5;
#define makeint(n,s)  istringstream(s)>>n
#define inpow(a,x,y) int i; a=x;fri(2,y)  a*=x
#define cntbit(mask) __builtin_popcountll(mask)
//0 based print
#define debug_array(a,n) for(int i=0;i<n;i++) cerr<<a[i]<<" "; cerr<<endl;
#define debug_matrix(mat,row,col) for(int i=0;i<row;i++) {for(int j=0;j<col;j++) cerr<<mat[i][j]<<" ";cerr<<endl;}

#define csprnt printf("Case %d: ", ++cas);
#define mod         1000000007
#define eulerconstant 0.5772156649

template<class T1> void debug(T1 e){cout<<e<<endl;}
template<class T1,class T2> void debug(T1 e1,T2 e2){cout<<e1<<"\t"<<e2<<endl;}
template<class T1,class T2,class T3> void debug(T1 e1,T2 e2,T3 e3){cout<<e1<<"\t"<<e2<<"\t"<<e3<<endl;}
template<class T1,class T2,class T3,class T4> void debug(T1 e1,T2 e2,T3 e3,T4 e4){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<endl;}
template<class T1,class T2,class T3,class T4,class T5> void debug(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<"\t"<<e5<<endl;}
template<class T1,class T2,class T3,class T4,class T5,class T6> void debug(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5,T6 e6){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<"\t"<<e5<<"\t"<<e6<<endl;}
template<class T> void debug(vector< vector<T> > e,int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j]<<" ";cout<<endl;} cout<<endl;}
template<class T> void debug(vector< basic_string<T> > e,int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j];cout<<endl;} cout<<endl;}
template<class T> void debug(T e[110][110],int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j]<<" ";cout<<endl;}}
template<class T> string toString(T n){ostringstream oss;oss<<n;oss.flush();return oss.str();}
int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}
bool isVowel(char ch){ch=tolower(ch);if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u')return true;return false;}
bool isUpper(char c){return c>='A' && c<='Z';}
bool isLower(char c){return c>='a' && c<='z';}
/***************************************************code starts from here*************************************************************************************************/

int found=0,n,arr[1000000],kk;

void dp(int k,int index)
{
    int temp;
    if(k<0)
    {
        temp=-k;
        temp=temp%n;
        temp=n-temp;
    }
    else
    {
        temp=k%n;
    }
    //printf("temp-->%d k-->%d index-->%d\n",temp,k,index);
    if(found)
    {
        return ;
    }
    else if(index==kk+2)
    {
        return ;
    }
    else if(index==kk+1 && temp==0)
    {
        found=1;
        return ;
    }
    else if(!found)
    {
        dp(temp+arr[index],index+1);
        if(found)
        {
            return ;
        }
        dp(temp-arr[index],index+1);
    }
    return ;
}

int main()
{
    int tCase,nCase;
    scanf("%d",&tCase);
    fr(nCase,1,tCase)
    {
        int i,j;
        kk=0,n=0;
        mem(arr,0);
        found=0;
        scanf("%d %d",&kk,&n);
        fr(i,1,kk)
        {
            scanf("%d",&arr[i]);
        }
        dp(0,1);
        if(found)
        {
            printf("Divisible\n");
        }
        else
            printf("Not divisible\n");
    }
    return 0;
}

[brianfry713]

Try matching variable names to the problem statement if you're going to post code. Switching N and K doesn't make it easier to read.
The DP array only needs to be as large as 2 * K (I'm talking about K from the problem statement), yours is much larger than that.
I don't see where your code is doing any memoization. Just naming a function dp doesn't make it DP.
In cases where you fill the DP array bottom up is faster than top down as it avoids the function overhead.

[sabbir_alam_ufo]

Thank you brianfry713. I will try to write cleaner code.

[fresher96]

i tested this code with many cases and can't find the wrong part
can anyone help ?

Code: Select all

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
/**/
#define MAXX 10000
#define KMAXX 100
int mem[MAXX][KMAXX];
int k,n;
int p[MAXX];
/**/
int fix(int a) 
{
	return (a % k + k) % k;
}
int tryAll2(int i, int mod) 
{
	int &ret = mem[i][mod];
	if (ret != -1)
		return ret;
	if (i == n)
		return ret = mod == 0;

	if (tryAll2(i + 1, fix(mod + p[i])) || tryAll2(i + 1, fix(mod - p[i])))
		return ret = 1;
	return ret = 0;

}
/**/
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n,&k);
		memset(mem , -1 , KMAXX*MAXX*(sizeof(int)));
		int i;
		for(i=0; i<n; i++)
			scanf("%d",&p[i]);
		if(tryAll2(1, fix(p[0]) ))
			printf("Divisible");
		else
			printf("Not divisible");
		printf("\n");
	}
}

[brianfry713]

Change line 5 to:
#define MAXX 10001

[fresher96]

Change line 5 to:
#define MAXX 10001

Got it
thanks a lot