## 914 - Jumping Champion

Moderator: Board moderators

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 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
Contact:

### 914 - Jumping Champion

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
Contact:

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

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

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

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.

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

### Re: 914 - Jumping Champion

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
Contact:

### Re: 914 - Jumping Champion

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

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
Contact:

### Re: 914 - Jumping Champion

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

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
Contact:

### Re: 914 - Jumping Champion

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

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
Contact:

### Re: 914 - Jumping Champion

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

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

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.