914 - Jumping Champion

[hamedv]

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]

deleted

[calicratis19]

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;
}






[sn23581]

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[i])
{
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[i])
{
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[i]>res)
{
res2=i;
res=check[i];
}
}
p=0;
for ( i=1; i<20; i++)
{
if (check[i]==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]

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]

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

[uvasarker]

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]

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

[uvasarker]

Hi boss still TLE.

Code: Select all

Cuttttttttttttt


[brianfry713]

Your sieve could be faster.

You're iterating on every integer from L to U. Instead only consider each prime between L and U.

[uvasarker]

Boss Updated. But, till T L E

Code: Select all

/* Stupid problem. Try this if you want to increase the temperature of you head */


[brianfry713]

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.

[uvasarker]

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]

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.