10533 - Digit Primes

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

Moderator: Board moderators

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

now RTE, 10533

Post by deena sultana » Wed Jun 28, 2006 7:00 pm

i m very much annoyed with this 10533, 1st it get tle & tle, and now its getting RTE. :evil:
now it seems very hard for me to think more about this problem.
Anyone help me, plz?plzzzzzzzzzzz.

here is my code:

Code: Select all


removed after AC.
thanx for reading.
Last edited by deena sultana on Thu Jun 29, 2006 9:06 pm, edited 1 time in total.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Wed Jun 28, 2006 8:16 pm

You're declaring large arrays in the main() function. Declare them static or global. Moreover, you might get memory limit exceeded.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Thu Jun 29, 2006 12:33 pm

The cause of RTE is because of the declaration of huge Array inside the main function..
.. making it global will solve the problem. [ like mamun said ]

But it will not get MLE since two integer array of size 10^6 and 1 boolean array of size 10^6 doesn't exceed the given memory limit..

Your code is correct, I made the necessary changes and it did get AC.

And remove your code after submitting... :)

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

Post by deena sultana » Thu Jun 29, 2006 9:04 pm

Sohel n Mamun,

thank u soooooooooooo much.

At last i get AC. :D .

So kind of u both.

Thanks again.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Tue Jul 04, 2006 2:39 pm

Well,
I also got ACC in that problem but thats not what i am bothered about but its the timing . It took me 2.090 CPU and what I found in the list that people solved it much more efficiently .

My algo is as same as it was told here. Can anyone tell me whether there is a better algorithm to solve this problem more efficiently ?
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

10533 digit primes WA

Post by ayeshapakhi » Thu Jul 06, 2006 2:55 pm

i wonder wheres the mistake!
pls help!!!
thanks for any help;;;

Code: Select all

#include <stdio.h>  // 10533 submit
#include <math.h>

#define L 1
#define U 1000005
#define D 1000005

bool all[D];
bool digit[D];
inline void seive(void);
long count[D];

   *********removed after AC
/*
12 
1 999999 
1 1 
1 10 
9 12 
240320 240350 
3 20 
204525 505639 
200 300 
1000 3000 
2056 31256 
999984 999999 
999985 999985 


OUTPUT: 

30123 
0 
4 
1 
0 
4 
9096 
8 
133 
1364 
0 
0
*/
pls supply me some critical I/O
thanks again.
Last edited by ayeshapakhi on Wed Aug 02, 2006 6:54 am, edited 1 time in total.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10533 digit primes WA

Post by Martin Macko » Sun Jul 23, 2006 11:32 pm

ayeshapakhi wrote:i wonder wheres the mistake!
pls help!!!
thanks for any help;;;
Your solution's not working for:

Code: Select all

10
291188 931733
638630 694459
238760 749751
762142 886106
517246 642611
203388 491378
369474 521162
515894 899808
181906 384967
89477 457040
My AC's output is

Code: Select all

18179
1558
14793
3382
3592
8699
4463
10686
6237
11553

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10533 digit primes WA

Post by Martin Macko » Sun Jul 23, 2006 11:38 pm

And btw, there is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question instead of creating a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=11056, http://online-judge.uva.es/board/viewtopic.php?t=7453, http://online-judge.uva.es/board/viewtopic.php?t=3600 and http://online-judge.uva.es/board/viewtopic.php?t=4503)

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

thanks to martin

Post by ayeshapakhi » Wed Aug 02, 2006 6:58 am

dear martin,
thanks a tonnn for ur help.
ur i/o helped me much.
what a stupid i am. i flagged an array but using another in my code.....
foolish!!!!
thanks a lot..

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Sat Mar 31, 2007 3:22 pm

i used normal sieve mathod to count. that is the number and digit prime or not.
but OJ says memory limit exceded. now how can i minimize the memory limit?

if i changed the prime[10000001] to prime[1000001] it gets CE!
but why?

Code: Select all


#include<stdio.h>
#include<math.h>

void set_prime(void);
long sod(long);

long prime[10000001];

int main()
{
	long tc,t1,t2,j,count;

	set_prime();
	scanf("%ld",&tc);
	while(tc--)
	{
		scanf("%ld %ld", &t1,&t2);
		count = 0;
		for(j = t1; j <= t2; j++)
		{
			if(prime[j])
			{
				if(prime[sod(j)])
					count++;
			}

		}
		printf("%d\n", count);
	}
	return 0;
}

void set_prime()
{
	long i,j,index;
	for(i=1;i<=1000000;i++)
		prime[i]=1;

	prime[1] = 0;
	for(i=2;i<=sqrt(1000000);i++)
		if(prime[i]==1)
			for(j=2;i*j<=1000000;j++)
				prime[i*j]=0;
}


long sod(long num)
{
	long sum = 0;
	while(num)
	{
		sum += num % 10;
		num = num / 10;
	}
	return sum;
}



advanced thanx!

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

TO NEWTON...

Post by nymo » Sat Mar 31, 2007 5:14 pm

to Newton, your algo is slow... even if you don't get CE, it will probably be a TLE...

in your code, you use

Code: Select all

long prime[10000001]; 
just for marking whether i is prime or not; 1 and 0 respectively.
you can obviously use

Code: Select all

#define SIZE THE_SIZE_YOU_WANT
char prime[SIZE];
it will reduce the size to 1/4 :) char is 1 byte and it can be used to hold integers in that range.

you can use this SIEVE code :)

Code: Select all


#define SIZE THE_SIZE_YOU_WANT

char composite[SIZE];

void sieve(void)
{
	int i, j, k;

	composite[0] = 1;
	composite[1] = 1;

	for (i=4; i<SIZE; i+=2)
	{
		composite[i] = 1;
	}

	for (i=3; i<SIZE; i+=2)
	{
		if (!composite[i])
		{
			k = SIZE / i;
		
			for (j=i; j<=k; j+=2)
			{
				composite[i * j] = 1;
			}
		}

	
	}
}
you can use the fact that global arrays are initialized with 0 :)
regards,
nymo

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

I have got ACC in 1.7 sec, Is there any better method?

Post by tanaeem » Tue May 15, 2007 8:51 am

I have detected prime by ruunig seive.
Then created a dprime array, if ith element id a digit prime then put there 1. I have done this using the seive, if both i and digitsum(i) is prime then dprime=1;

then created another array containing cumilitive sum of the dprimr array.
Then printed output as input given in constant time.
But it took 1.7 sec time. is there any better method?
I see someone have got AC in 0.250 time.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue May 15, 2007 9:04 am

There are optimized versions of finding primes using sieve.
Since you are printing the output in constant time, I guess your 'sieve method' isn't fast enough.

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

10533(Runtime error)

Post by ishtiaq ahmed » Tue Jul 24, 2007 1:32 pm

Hi, i cannot understand why i am facing runtime error. I have checked array size again and again. Please try to help me. Here is my code

Code: Select all

#include<stdio.h>

#define SIZE 1000001

long  a,b,data[SIZE]={0},cas,i,j;
void s (void);
long sum_prime(void);


int main()
{
	long k,result,cas;
	s();
	scanf("%ld",&cas);
	for(k=1;k<=cas;k++)
	{
		scanf("%ld %ld",&a, &b);
		result=sum_prime();
		printf("%ld\n",result);
	}
	return 0;
}



void s(void)
{
	long i,j;
	data[0]=1;
	data[1]=1;
	for(i=4;i<SIZE;i+=2)
		data[i]=1;
	for(i=3;i<SIZE;i+=2)
		for(j=i;i*j<SIZE;j++)
			if(!data[i*j])
				data[i*j]=1;
}



long sum_prime(void)
{
	int sum=0,dum,m=0,z;
	for(i=a;i<=b;i++)
		if(!data[i])
		{
			z=i;dum=0;
			while(z)
			{
				m=z%10;
				dum +=m;
				z /=10;
			}
			if(!data[dum])
				sum++;
		}
	return sum;
}
No venture no gain

with best regards
------------------------
ishtiaq ahmed

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Tue Jul 24, 2007 3:53 pm

change your sieve function to

Code: Select all

void s(void)
{
   long i,j;
   data[0]=1;
   data[1]=1;
   for(i=4;i<SIZE;i+=2)
      data[i]=1;
   for(i=3;i<SIZE;i+=2)
      for(j=2;i*j<SIZE;j++)
      {
         if(!data[i*j])
            data[i*j]=1;
			}
}

Post Reply

Return to “Volume 105 (10500-10599)”