914 - Jumping Champion

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

Moderator: Board moderators

Postby 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);
   }
}
hamedv
Learning poster
 
Posts: 98
Joined: Mon May 07, 2007 8:30 am

914 - Jumping Champion

Postby 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.

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

Postby 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
calicratis19
Learning poster
 
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.

914 - Jumping Champion

Postby 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[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;
}
sn23581
New poster
 
Posts: 2
Joined: Thu Jul 29, 2010 2:02 pm

Re: 914 - Jumping Champion

Postby 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.
Zwergesel
New poster
 
Posts: 8
Joined: Tue Jul 27, 2010 7:29 pm

Re: 914 - Jumping Champion

Postby 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
User avatar
plamplam
Experienced poster
 
Posts: 151
Joined: Fri May 06, 2011 11:37 am

Re: 914 - Jumping Champion

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

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

Re: 914 - Jumping Champion

Postby 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 hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5409
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 914 - Jumping Champion

Postby 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.
uvasarker
Learning poster
 
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh

Re: 914 - Jumping Champion

Postby 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 hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5409
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 914 - Jumping Champion

Postby 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.
uvasarker
Learning poster
 
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh

Re: 914 - Jumping Champion

Postby 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 hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5409
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 914 - Jumping Champion

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

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

Re: 914 - Jumping Champion

Postby 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 hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5409
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 914 - Jumping Champion

Postby 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.
hello
New poster
 
Posts: 25
Joined: Sun Mar 10, 2013 7:29 pm

PreviousNext

Return to Volume IX

Who is online

Users browsing this forum: No registered users and 1 guest