10036 - Divisibility

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10036 - Divisibility

Post by lbv » Mon Jul 28, 2014 9:43 pm

just_yousef wrote: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.
just_yousef wrote: 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
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10036 - Divisibility

Post by just_yousef » Wed Jul 30, 2014 8:44 pm

lbv wrote:
just_yousef wrote: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.
just_yousef wrote: 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
New poster
Posts: 16
Joined: Fri Nov 15, 2013 9:33 pm

Re: 10036 - Divisibility

Post by sabbir_alam_ufo » Thu Sep 11, 2014 11:37 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10036 - Divisibility

Post by brianfry713 » Fri Sep 12, 2014 11:05 pm

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.
Check input and AC output for thousands of problems on uDebug!

sabbir_alam_ufo
New poster
Posts: 16
Joined: Fri Nov 15, 2013 9:33 pm

Re: 10036 - Divisibility

Post by sabbir_alam_ufo » Tue Sep 16, 2014 9:39 pm

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

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

Re: 10036 - Divisibility WA

Post by fresher96 » Wed Oct 29, 2014 7:56 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10036 - Divisibility

Post by brianfry713 » Wed Oct 29, 2014 10:06 pm

Change line 5 to:
#define MAXX 10001
Check input and AC output for thousands of problems on uDebug!

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

Re: 10036 - Divisibility

Post by fresher96 » Wed Oct 29, 2014 10:15 pm

brianfry713 wrote:Change line 5 to:
#define MAXX 10001
Got it :D
thanks a lot

Post Reply

Return to “Volume 100 (10000-10099)”