Page 2 of 3

Posted: Mon Sep 11, 2006 5:08 pm
by vinay
ok i understood...
so apply sieve of eratosthenes...???? :lol:

I rather thank the problem setter.

Posted: Tue Sep 12, 2006 9:42 am
by moonstruck
I rather thank the problem setter.

Do you know why the system analyst gets high price than a programmer? Because, he has to specify the requirements of the software from his client

Posted: Tue Sep 12, 2006 5:14 pm
by Darko
This is mainly a problem solving site. I guess sometimes it is a problem-setter's-mind-reading site, we can't avoid that. But to praise someone for setting the problem that way?!?
If problem is simple then it's simple. If the statement is vague, that doesn't make the problem harder, it just makes the experience of solving it less satisfying.

This could've been a nice problem if the problem statement was written properly. I just hope it wasn't set that way on purpose.

moonstruck, I have no idea how you can even try to compare this to the "real world". Probably 95% of these problems are completely made up. Say this one, for example. Is it useful in any way? For it to be useful, you should be able to tell if a 500-digit number is a composite prime and what are the primes that compose it, and do it efficiently, or something like that. Or all of those "guess the input format" type problems. That is realistic? I like the problem statements of the type "ya, ya, we know this is BS, but just play along". At least they don't pretend these translate into some "real life" problems.

There are challenges and then there are challenges. This type of problems I don't consider to be challenging, just annoying. Too bad this type of setting ruins the underlying problems, no matter how easy (or hard) they are.

Oh, I forgot my usual rant - in real world, I wouldn't be forced to use C to solve this problem. (Not that there is anything wrong with it)

Posted: Tue Sep 12, 2006 8:08 pm
by Rainy Day
If the problem is simple & specific, then where is our challenges?
so from ur point of view it's a challenging problem , what's the challenge , to write a simple
sieve without any optimization. :-? :D :)

Posted: Tue Sep 12, 2006 9:30 pm
by Vexorian
This time it was an avoid-the-lame-symbol-confusion problem which was simply bad. With N used for 3 different things in the problem for no reason. Because of that it was not a vague problem it was just a wrong problem.

I personally think that interpreting a prompt even if it is vague is part of problem solving. Making a program that would work for every possible input case also is part of problem solving. But beating ambiguous and contradictory prompts isn't.

Posted: Wed Sep 13, 2006 7:56 am
by rabby
Yes problem-setter used N for three purposes.
1. Set of natural Number is N
2. Input Integer is N.
3. Constraints N <=2^20.

I think 3 is pointed to 2. Actually in two different puposes N is used.
This is not a problem at all. first N is in the problem description and 2nd N is in real problem I/O.
So i can say, to compare with real life problem it's trends us to make challenge.

Posted: Thu Sep 14, 2006 6:43 pm
by Darko
I don't know why you thought that 2 and 3 refered to the same N, but anyway...

This ticked me off enough so I retried a buffered I/O until it finally worked! I thought that you couldn't use System.in.read(byte[],int,in), because I tried it before, but, it turns out, with buffer sizes that were too large. Actually, 2048 worked, 4096 didn't, I don't know if there is something in between.

There, beat Java time :P

(sorry for 40+ submitions)

Re: I rather thank the problem setter.

Posted: Fri Sep 15, 2006 12:03 am
by Sumon
moonstruck wrote:If the problem is simple & specific, then where is our challenges?
So, you think a problem which is !(specific & simple),that is challenging?

!(specific & simple) = (!specific) || (!simple)

Ok, i am giving you a simple and (!specific) problem-
#Find A+B where A>10 && B>10 (It's not typing mistake it's really A,B>10).

~~What is the challenge here. You can guess maximum A,B as 10^100 , 10^100000 or 10^10000000000........... Here,the !(specific) thing made it a boring guess game. Do u think programming contest is a guessing game contest?

Now, i am giving u a specific problem.
#Find hamilton cycle for a given simple graph where node can be at most 10000.

~~Everything specific here. Do you think there is no challenge in this problem?

Posted: Fri Sep 15, 2006 8:25 pm
by CodeMaker
i did not code this problem during the contest because of its poor description. i thought in the worst case i will be given 1 million(2^20) numbers, each of them can be as large as 2^31.

i knew what i have to do to solve it, but could not fit that limit neither in memory nor in time. i wondered that someone may have discovered a new formula. now i know what that formula is :x

only someone having the same experience will understand how painful it is.

i got AC by applying sieve on 2000000 , may be even less required.

Posted: Sat Nov 25, 2006 10:07 pm
by jan_holmes
EDIT : ACed.... :)

11086 - TLE

Posted: Sat Jun 21, 2008 1:11 pm
by nahid
I'm having TLE for this code. anyone pls fix my probs. here is code.

Code: Select all

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

#define MAX 2000000
#define PRIME 0
#define NOTPRIME 1

unsigned char flag[MAX];

void seive()
{
	int i,j,sq;

	flag[0]=flag[1]=NOTPRIME;
	flag[2] = PRIME;


	sq = (int) sqrt(MAX);

	for (i = 4; i < MAX; i += 2)
        flag[i] = NOTPRIME;

	for(i = 3; i < sq; i+= 2)
	{
		if(flag[i] == PRIME)
		{
			for(j = i*i; j < MAX; j+= i)
			{
				flag[j] = NOTPRIME;
			}
		}
	}
}

int main()
{
	int N,Nn,i,count,sq;
	seive();

	while(scanf("%d",&N)!=EOF)
	{
		count = 0;
		while(N--)
		{
			scanf("%d",&Nn);
			sq = sqrt(Nn);
			if(flag[Nn] == NOTPRIME)
			{
				for(i=2;i<=sq;i++)
				{
					if(flag[i] == PRIME && Nn%i == 0 && flag[Nn/i] == PRIME)
					{
							count++;
							break;
					}
				}
			}
		}
		printf("%d\n",count);
	}
	return 0;
}

Re: 11086 - Composite Prime

Posted: Thu Jan 15, 2009 11:45 pm
by deadangelx
test case

Code: Select all

5
999997 999998 999999 1000000 1000001
answer

Code: Select all

2

Re: 11086 - Composite Prime

Posted: Tue Mar 17, 2009 7:46 pm
by Bitta
I am getting TLE.plzz help me...

Code: Select all

#include<stdio.h>
#define MAX 1048580

bool isnp[MAX+3],cp[MAX+3];

int main()
{
	long int i,j,p,n,c,flag,b,x;

	isnp[1]=isnp[0]=true;

    for(i=2;i*i<=MAX;i++)
    {    
		if(!isnp[i])
		{  
			for(j=i*i;j<=MAX;j+=i)
                isnp[j]=true;
		}
	}


	while(scanf("%ld",&n)==1)
	{
		x=0;

		for(i=0;i<n;i++)
		{
			scanf("%ld",&b);

			if(b==0 || b==1)
				cp[b]=false;

			else if(isnp[b]==false)
			{	
				cp[b]=false;
			}

			else
			{
				flag=0;

				for(j=2;(j*j)<=b;j++)
				{
					c=0;
					if(b%j==0)
					{
						p=b/j;
						c=1;
					}

					if(c==1 && (isnp[j]==true || isnp[p]==true))
					{
						flag=1;
						break;
					}
				}
				if(flag==1)
					cp[b]=false;
				else
					cp[b]=true;
			}

			if(cp[b]==true)
				x++;
		}

		printf("%ld\n",x);
	}

	return 0;
}
thanks in advance.

Re: 11086 - Composite Prime

Posted: Wed Mar 18, 2009 7:03 am
by Obaida
You will never get acc with this method.
Try to use a faster method to pass this. You need to learn more about primes.

11086 - Composite Prime

Posted: Sat Oct 23, 2010 9:11 pm
by sazzadcsedu
what is the number of composite prime less than 2^20(1048556).Is it 227886??