914 - Jumping Champion

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

Moderator: Board moderators

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

Post by hamedv » Wed Aug 15, 2007 9:09 am

I'm getting WA
I tried all of IO above

Code: Select all

#include <stdio.h>
#include <string.h>

int main()
{
	const int MAX = 1000000;
	bool prime[MAX+1];
	memset(prime, 1, sizeof prime);
	prime[0] = prime[1] = 0;
	for (int i = 2; i <= MAX; i++)
		if (prime[i])
		{
			int k = (MAX+1) / i;
			for (int j = 2; j <= k; j++)
				prime[j*i] = 0;
		}
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int L, H, lp = 0, d[500];
		memset(d, 0, sizeof d);
		scanf("%d%d", &L, &H);
		for (int i = L; i <= H; i++)
		{
			if (prime[i] && lp)
				d[i-lp]++, lp = i; else
			if (prime[i]) lp = i;
		}
		int max = 0, maxn = 0, c = 0;
		for (int i = 1; i < 50; i++)
			if (d[i] > max)
			{
				max = d[i];
				maxn = i;
				c = 1;
			} else
			if (d[i] ==  max) c++;
		if (c > 1) puts("No jumping champion\n"); else printf("The jumping champion is %d\n", maxn);
	}
}

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

914 - Jumping Champion

Post by calicratis19 » Wed Oct 08, 2008 4:21 pm

deleted
Last edited by calicratis19 on Sat Jan 10, 2009 1:21 am, edited 1 time in total.
Heal The World

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 914 - Jumping Champion..WA.pls help.

Post by calicratis19 » Sat Jan 10, 2009 1:20 am

i have tested all the io above.but still wa

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
long a[1000100],c[1000100],i,j,cnt,coun,minus,test,ll,ul,end,start,b,g,m,k;
int main()
{
 	a[1]=-1;
	for(i=2;i<=1000000;i++)
		if(a[i]!=-1)
			for(j=2*i;j<=1000000;j+=i)
				a[j]=-1;
	memset(c,0,sizeof(c));
	scanf("%ld",&test);
	for(cnt=0;cnt<test;cnt++)
	{
		scanf("%ld %ld",&ll,&ul);
		if(ll>ul)
		{
			coun=ul;
			ul=ll;
			ll=coun;
		}
		coun=0;
		minus=0;
		b=0;
		m=0;
		for(i=ll,j=0;i<=ul;i++)
		{
			if(a[i]!=-1)
			{
				if(b!=0)
				{
					minus=abs(b-i);
					b=i;
					c[j++]=minus;
					m++;
				}
				else
				{
					b=i;
					m++;
				}
			}
		}
		if(m<2)
		{
			printf("No jumping champion\n");
			continue;
		}
		m=0;g=0;
		for(i=0;i<j;i++)
		{
			if(c[i]!=-1)
			{
			for(k=i+1,coun=1;k<j;k++)
			{
				if(c[i]==c[k])
				{
					coun++;
					c[k]=-1;
				}
			}
			if(coun>m)
			{
				g=0;
				m=coun;
				minus=c[i];
			}
			else if(coun==m)
				g=1;
			}
		}
		if(g==1)
			printf("No jumping champion\n");
		else
			printf("The jumping champion is %ld\n",minus);
	}
	
return 0;
}




Heal The World

sn23581
New poster
Posts: 2
Joined: Thu Jul 29, 2010 2:02 pm

914 - Jumping Champion

Post by sn23581 » Thu Jul 29, 2010 2:20 pm

i tried my code for all the inputs given above nd found no error... still WA :( ... can anyone help me plz??


#include<stdio.h>
#define MAX 1000001
char milo[MAX];
int main()
{
long i,j;
long n,t;
long l,u;
long cou,res,res2,c,p;

for ( i=2; i<MAX; i++)
{
if ( !milo)
{
for ( j=i*2; j<MAX; j+=i)
{
milo[j]=1;
}
}
}
milo[1]=1;
milo[0]=1;
scanf("%ld",&t);

for ( ; t>0; t--)
{
c=0;
scanf("%ld%ld",&l,&u);
res=0;
res2=0;
long check[10000]={0};
for ( i=l; i<=u; i++)
{
if ( !milo)
{
cou=1;
for ( j=i+1; milo[j]; j++) cou++;
if (j<=u)
{
check[cou]++;
i+=(cou-1);
}
}
}
for ( i=1; i<20; i++)
{
if ( check>res)
{
res2=i;
res=check;
}
}
p=0;
for ( i=1; i<20; i++)
{
if (check==res) p++;
if (p>1)
{
if (l>=0) printf("No jumping champion\n");
c=1;
break;
}
}
if (l<0) printf("The jumping champion is 2\n");
else if (!res2 && !c) printf("No jumping champion\n");
else if (!c) printf("The jumping champion is %ld\n",res2);
}
return 0;
}

Zwergesel
New poster
Posts: 11
Joined: Tue Jul 27, 2010 7:29 pm

Re: 914 - Jumping Champion

Post by Zwergesel » Mon Aug 09, 2010 6:22 pm

You have a compiler warning:
forum.cpp:7: warning: unused variable ‘n’
I think this might cause WA, because it's written to stdout when the program compiles. Try removing that variable and submitting your code again. If this was the cause of your problem, remember to compile your programs with the "-Wall" parameter in the future.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 914 - Jumping Champion

Post by plamplam » Tue Jun 14, 2011 5:17 am

Here are some critical inputs for these problem. I found out all these inputs after I got Wrong Answer on my first try.
Try these, I think these will surely help you solve this problem :)

7
0 12
The jumping champion is 2
2 12
The jumping champion is 2
7 11
The jumping champion is 4
6 12
The jumping champion is 4
1 1000000
The jumping champion is 6
492227 492113
The jumping champion is 114
491013 495773
The jumping champion is 6
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 914 - Jumping Champion

Post by uvasarker » Fri Feb 17, 2012 6:48 am

Please, help me anyone. I am getting TLE. WHY?
Here is my code:

Code: Select all

#include <cstdio>
#include <cmath>

bool sieve[10001011]={0};

int main()
{
	unsigned long T, i, j;
		sieve[0]=1; sieve[1]=1;  // 0 == prime  & 1 == non-prime
		
		for(i=3 ; i<=1000000 ; i+=2)
		{
			sieve[i+1]=1;
				if(sieve[i]==0 && i<=1000)
				{
						for(j=i*i ; j<=10001008 ; j+=2*i)
						{
								sieve[j]=1;
						}
				}
		}

	scanf("%lu",&T);
	while(T--)
	{
		unsigned long L,U, I;
		unsigned long k=0,prim[100000];
		unsigned long dif[100000];		
		
		scanf("%lu %lu",&L,&U);
		for( i=L ; i<=U ; i++)
		{
				if(sieve[i]==0)
				{
								prim[k]=i;
								k++;
				}
		}
		if(k>3)
		{
			unsigned long v=0;
			for( I=0 ; I<k-1 ; I++)
			{
					v++;
					dif[I]=prim[I+1]-prim[I];
			}
			
			
				unsigned long cham,max=0,fag,temp;
				for( i=0 ; i<k-1 ; i++)
				{
						temp=dif[i],fag=0;
						for( j=0 ; j<k-1 ; j++)
						{
								if(temp==dif[j])
									fag++;
						}
						if(fag>max)
						{
							max=fag;
							cham=dif[i];
						}
				}
				if(max>=2 && max!=v)
					printf("The jumping champion is %lu\n",cham);
				else
					printf("No jumping champion\n");
				
		}
		else
				printf("No jumping champion\n");
		
	}
	
	return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 914 - Jumping Champion

Post by brianfry713 » Fri Feb 17, 2012 9:48 pm

Don't check every number between L and U to see if it's prime at every test case. First precompute an array of all the primes. Then binary search to find the start and end of this array and find the jumping champion.

Your code should be able to handle this input in less than 3 seconds.

Code: Select all

10
1 999999
1 999999
1 999999
1 999999
1 999999
1 999999
1 999999
1 999999
1 999999
1 999999
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 914 - Jumping Champion

Post by uvasarker » Mon Jun 04, 2012 6:28 pm

Hi boss still TLE.

Code: Select all

Cuttttttttttttt
Last edited by uvasarker on Mon Jun 11, 2012 8:27 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 914 - Jumping Champion

Post by brianfry713 » Mon Jun 04, 2012 11:34 pm

Your sieve could be faster.

You're iterating on every integer from L to U. Instead only consider each prime between L and U.
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 914 - Jumping Champion

Post by uvasarker » Mon Jun 11, 2012 8:26 pm

Boss Updated. But, till T L E

Code: Select all

/* Stupid problem. Try this if you want to increase the temperature of you head */
Last edited by uvasarker on Tue Jun 12, 2012 8:16 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 914 - Jumping Champion

Post by brianfry713 » Mon Jun 11, 2012 11:48 pm

Ok, now you're only checking every other integer between L and U, which of course is twice as fast, but still too slow. It looks like you have an array PRIM that lists the primes. Don't iterate from L to U. Use a binary search to find the index of L in PRIM or the smallest prime number greater than L, and another binary search to find the index of U in PRIM or the largest prime number less than U. Then you only have to iterate the index of PRIM, which is much faster.
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 914 - Jumping Champion

Post by uvasarker » Tue Jun 12, 2012 8:12 pm

Guru,
I think I can't solve this problem. Updated according to your suggestion but TTTTT LLLLLLL EEEEE

Code: Select all

#include <cstdio>
#include <cmath>

bool sieve[10001011]={0};

int main()
{
	unsigned long T, i, j;
	unsigned long KK=1,PRIM[100001],S=1,E,M;
		sieve[0]=1; sieve[1]=1;  // 0 == prime  & 1 == non-prime
        PRIM[0]=2;
		for(i=3 ; i<=1000000 ; i+=2)
		{
			sieve[i+1]=1;
				if(sieve[i]==0 && i<=1000)
				{
						for(j=i*i ; j<=10001008 ; j+=2*i)
						{
								sieve[j]=1;
						}
				}
                if(sieve[i]==0)
                {
                    PRIM[KK]=i;
                    KK++;
                }
		}
/*        for(i=3 ; i<=1000000 ; i+=2)
        {
                if(sieve[i]==0)
                {
                    PRIM[KK]=i;
                    KK++;
                }
        }*/
    //freopen("in-914.txt","r",stdin);
	scanf("%lu",&T);
	while(T--)
	{
		unsigned long L,U, I,key,k=0, ff,ll;
		unsigned long prim[100001];
		unsigned long dif[100001];

		scanf("%lu %lu",&L,&U);
		if(L%2==0) L+=1;

                key=L;
                S=1;
                E=KK;
                M=(int)((S+E)/2);
                while( (S<=E) && (PRIM[M]!=key) )
                {
                    if(PRIM[M]>key)
                        E=M-1;
                    else
                        S=M+1;
                    M=(int)((S+E)/2);
                }
                if(PRIM[M]==key)
                {
                    prim[k]=key;
                    k++;
                    ff=M;
                }
                else
                {
                    prim[k]=PRIM[M+1];
                    k++;
                    ff=M+1;
                }
		while(PRIM[ff]<=U)
		{
                prim[k]=PRIM[ff];
                k++;
                ff++;
		}

		if(k>3)
		{
			unsigned long v=0;
			for( I=0 ; I<k-1 ; I++)
			{
					v++;
					dif[I]=prim[I+1]-prim[I];
			}


				unsigned long cham,max=0,fag,temp;
				for( i=0 ; i<k-1 ; i++)
				{
						temp=dif[i],fag=0;
						for( j=0 ; j<k-1 ; j++)
						{
								if(temp==dif[j])
									fag++;
						}

						if(fag>max)
						{
							max=fag;
							cham=dif[i];
						}
				}
				if(max>=2 && max!=v)
					printf("The jumping champion is %lu\n",cham);
				else
					printf("No jumping champion\n");

		}
		else
				printf("No jumping champion\n");

	}

	return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 914 - Jumping Champion

Post by brianfry713 » Tue Jun 12, 2012 11:58 pm

You don't need to copy all the primes from L to U from PRIM to prim.

Your main problem is you're using an O(k*k) algorithm to determine the jumping champion after you fill the dif array, where in your code k is the number of primes between L and U. The biggest difference between consecutive primes below 1000000 is 114. Think of a O(k) method of finding the jumping champion. My code uses C++ STL functions lower_bound, max_element, and count.
Check input and AC output for thousands of problems on uDebug!

hello
New poster
Posts: 25
Joined: Sun Mar 10, 2013 7:29 pm

Re: 914 - Jumping Champion

Post by hello » Tue Jul 23, 2013 7:47 pm

Where is the problem .......... I have already check all the i/o from this forum.....

Code: Select all

  :lol: got the problem
Last edited by hello on Wed Jul 24, 2013 8:33 am, edited 3 times in total.

Post Reply

Return to “Volume 9 (900-999)”