11087 - Divisibility Testing

[Nazmul Quader Zinnuree]

No sorting & no hashing.

I used a flag array to identify duplicates..

Code: Select all

char flag[20000002]

It runs within 0:07.125

[Hadi]

First I also used ur method, but I got TLE (Because of memset. now, when i think, i realize i could do it more efficiently ...)

But, now, 7.869 sec. with a solution using both hashing and sorting

[Stummer]

No sorting & no hashing.

I used a flag array to identify duplicates..

Code: Select all

char flag[20000002]

It runs within 0:07.125

I used that method and got WA

Code: Select all

#include <iostream.h>
#include <string.h>
char flag[20000005]={0};
const int dif=10000005;
int main()
{	
	long long s,temp,k,t,n,ii,i,zz,zibil;
	cin>>t;
	for(ii=1;ii<=t;ii++)
	{
		zibil=2*ii-1;
		cin>>n>>k;
		s=0;
		long long b[505]={0};
		for(i=0;i<n;i++)
		{
			cin>>zz;			
			if(flag[zz+dif]==zibil+1) continue;
			if(flag[zz+dif]==zibil)
			{
				if(zz<0) temp=(k-(zz*-1)%k)%k;
				if(zz>=0) temp=zz%k;
				temp*=temp; temp%=k;
				s+=(temp==0);
				flag[zz+dif]++;
			}
			if(flag[zz+dif]<zibil)
			{
				if(zz<0) b[(k-(zz*-1)%k)%k]++;
				if(zz>=0) b[zz%k]++;
				flag[zz+dif]=zibil;
			}
		}
		s+=b[0]*(b[0]-1)/2;
		for(i=1;i<=k/2;i++)
		{ 
			if(i!=k-i) s+=b[i]*b[k-i];
			if(i==k-i) s+=b[i]*(b[i]-1)/2;
		}
		cout<<"Case "<<ii<<": "<<s<<endl;
	}
	return 0;
}

Please, help!

[Nazmul Quader Zinnuree]

make the flag array ready for the next input. re - initialize it with 0's

[Abednego]

I got 3 seconds with read(0, buf, 1024*1024) and a linear-time algorithm. It also helps not to store the numbers that you read. Read them one at a time and throw them away immediately.

[Sumon]

can u pls describe ur algo a little bit.

You can use a%k and store necessary data in a 500 size array and for testing repeat data u can use flag array of size 20000002.

Remember,never try to initialize the full flag array for each test case. Handle it intelligently.

[daveon]

I got 3 seconds with read(0, buf, 1024*1024) and a linear-time algorithm.

So this is the fastest way to get input with C/C++ ?

[Abednego]

I don't know. There might be some assembly language tricks that work better. It's the fastest that I know of.

[Stummer]

make the flag array ready for the next input. re - initialize it with 0's

I don't need initialize it with 0's, because I use different flags for each
test case, i. e. I use flags 1 and 2 for test case 1, 3 and 4 for test case 2
and so... I changed char[20000005] to unsigned char[20000005] but
got WA again

[Sumon]

I don't need initialize it with 0's, because I use different flags for each
test case, i. e. I use flags 1 and 2 for test case 1, 3 and 4 for test case 2
and so... I changed char[20000005] to unsigned char[20000005] but
got WA again

In my implementation, at the end of each test case i have reset values to 0 of those index which i have changed in current test case.

I don't know your idea. I think you are missing some special cases. I couldn't configure the solution with the use of two(1,2) flag in one test case for managing all situation. I had to use three(0,1,2) flags in one test case. If you come to the point that you will use 3 flag then be careful, as test case range is 100 then you have to flag which is at most 300 according to your approach and you cannot store it in unsigned char also.

[Stummer]

I don't need initialize it with 0's, because I use different flags for each
test case, i. e. I use flags 1 and 2 for test case 1, 3 and 4 for test case 2
and so... I changed char[20000005] to unsigned char[20000005] but
got WA again

In my implementation, at the end of each test case i have reset values to 0 of those index which i have changed in current test case.

I don't know your idea. I think you are missing some special cases. I couldn't configure the solution with the use of two(1,2) flag in one test case for managing all situation. I had to use three(0,1,2) flags in one test case. If you come to the point that you will use 3 flag then be careful, as test case range is 100 then you have to flag which is at most 300 according to your approach and you cannot store it in unsigned char also.

Yes, I use 3 flag, but in this way:
Let program works for case #X(from 1 to 100);
Than I use f1=2*X flag for elements which are not unique, f2=2*X-1
flag for elements which are unique yet, and f0<2*X-1 for elements which
are not exist yet. So in the next test case all my 2*X and 2*X-1 flags
becomes f0. And maximum flag is 200. If you don't understand anything,
just say me, or watch my program...
I tired with getting WA on this problem.

[Sumon]

Yes, I use 3 flag, but in this way:
Let program works for case #X(from 1 to 100);
Than I use f1=2*X flag for elements which are not unique, f2=2*X-1
flag for elements which are unique yet, and f0<2*X-1 for elements which
are not exist yet. So in the next test case all my 2*X and 2*X-1 flags
becomes f0. And maximum flag is 200. If you don't understand anything,
just say me, or watch my program...
I tired with getting WA on this problem.

Your idea is ok and nice,i liked it. Have you tried this type of test cases:

Sample Input:

5
5 5
5 5 5 5 5
4 4
2 2 4 0
3 4
2 2 4
5 4
2 2 4 0 4
5 4
-1 3 -3 1 1

Sample Output

Case 1: 1
Case 2: 2
Case 3: 1
Case 4: 3
Case 5: 4

All that i could do for you at this moment.

[Stummer]

Sample Input:

5
5 5
5 5 5 5 5
4 4
2 2 4 0
3 4
2 2 4
5 4
2 2 4 0 4
5 4
-1 3 -3 1 1

Sample Output

Case 1: 1
Case 2: 2
Case 3: 1
Case 4: 3
Case 5: 4

Thanks, but my program outputs the same output.

[daveon]

I don't know. There might be some assembly language tricks that work better. It's the fastest that I know of.

Wow, it's really fast. Maybe this is how people get blazing times. I might recode all of my solutions using this function. Cool and thanks.

[Sumon]

I got 3 seconds with read(0, buf, 1024*1024) and a linear-time algorithm. It also helps not to store the numbers that you read. Read them one at a time and throw them away immediately.

I tried to use this function read(). The judge replied me CE with the following message-

Here are the compiler error messages:

04956549_24.c: In function `int main()':
04956549_24.c:25: implicit declaration of function `int read(...)'

--Can anyone help me to solve this problem