OJ Board

Posted: **Wed Oct 30, 2013 9:27 pm**

generate a list of primes p
for(i = 0; ; i++)
  break if you find n - p[i] in a binary search of p

Posted: **Thu Oct 31, 2013 1:22 am**

Thanks, it worked.
But I cant see how it is faster; it is like O(n lgn) while mine was O(n)!

Posted: **Thu Oct 31, 2013 8:44 pm**

You can also get AC using two nested for loops like:

Code: Select all

void findGold (vi &a, int &x, int &y, int e){
  for(x = 0; ; x++) {
    for(y = x; y < a.size() && a[x] + a[y] < e; y++);
    if(a[x] + a[y] == e)
      return;
  }
}

but it's not as fast as using binary search. Your original code iterates from both ends of the prime array so it's slower if the two primes are close together and small.

Posted: **Fri Nov 01, 2013 12:08 am**

I added this to the beginning of the original findGold

Code: Select all

	y= lower_bound(a.begin(), a.end(), e)-a.begin()+1;
	if (y>=a.size())
		y=a.size()-1;

and it got the best time among my submissions.

I guess the worst input for the original code was 6, because the answer is 3 + 3 and "y" was to iterate through the whole array,
but when I run it myself and enter 6 it outputs in no time! How is that?!

Posted: **Sat Nov 02, 2013 12:05 am**

In my code, I generate 78,497 primes. I tested all possible inputs, on average the small prime is only in the 5.2 position, with an average value of 19.8
So the average number of iterations of the binary search code would be 5.2 * log2(78497) = 84.6 for any n value.
My guess is most of the judge's input is small n, and your original code would have to iterate from the end of the prime list almost to the front. For an n of 6 your original code is going to have around 78497 iterations.
Try testing the different versions of your code on an input file with many small n values and you should be able to see the difference in running time.
On some problems the average running time is more important than the worst case.

Posted: **Sun Nov 03, 2013 1:01 am**

Let's make something clear,
I assume that the time is the maximum of every single testcase's running time.
Am I wrong?! Is it their sum?

Posted: **Tue Nov 05, 2013 12:34 am**

There is one input file with many values for n. The run time is the sum of your programs time to print the output for all values of n in the input file.

Posted: **Tue Nov 05, 2013 10:36 pm**

Well then, it explains how.
Thanks again!

Posted: **Thu Mar 27, 2014 3:41 pm**

getting TLE!! what is the wrong

Code: Select all


#include<iostream>
#include<stdio.h>
#include<cmath>

using namespace std;

long int num1;
long int num2;
long int g=0;
bool prime_num[1100002];
long calculate_prime(long int p)
{


    for(long int k=4;k<=p;k+=2)
        {
            prime_num[k]=true;
        }
        for(long int i=3;i<=(int)sqrt(p);i+=2)
        {

                for(long int k=(i*i);k<=p;k+=2*i)
                {
                    prime_num[k]=true;
                }



        }


    for(long int i=2;i<p;i++)
    {
       if(prime_num[i]==false && prime_num[p-i]==false)
        {

             num2=i;
             num1=p-i;
             g++;
             break;

        }



        }




}




void show(int p)
{



        if(g==0)
        {
        printf("Goldbach's conjecture is wrong. \n");
        }
        else
        {
            printf("%d = %d + %d\n",p,num2,num1);
            g=0;
        }





}

int main()
{
    long int p;
    while(scanf("%d",&p)==1)
    {
        if(p==0)
            break;
        else
        {
          calculate_prime(p);
          show(p);
        }


    }


        return 0;

    }

Posted: **Thu Apr 17, 2014 2:34 pm**

Bluefin wrote:I do not look throught your code, but my algorithm is like this:

(1) use sieve of Eratosthnenes to find all the prime numbers up tp 1000000

(2) add the smallest prime number and the largest prime number which is smaller than n

(3) if the sum is equal to n, print them, else continue step 2

Thanks for sharing. This is the approach that was the most clear to me - especially since I know that the code I wrote when I first thought of this would result in a TL.

Here's some input / output that I found useful during testing / debugging.

Input:

Code: Select all

Output:

Code: Select all

999968 = 7 + 999961
6 = 3 + 3
568 = 5 + 563
43422 = 11 + 43411
989838 = 7 + 989831
46 = 3 + 43
10 = 3 + 7
999998 = 19 + 999979
748386 = 7 + 748379
8 = 3 + 5

Posted: **Fri Jun 27, 2014 4:23 pm**

i got wa.here is my code...

Code: Select all

#include<stdio.h>
#include<math.h>
int p(int n);
int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i=0;
        if(n==0) return 0;
        if(n>=6 && n<1000000)
        {

        int as=1;
        for(i=3;i<=(int)sqrt(n)+1;i=i+2)
        {
            int k=0;
            int j=p(i);
            if(j==2)
            {
                k=p(n-i);
                if(k==2)
                {
                    printf("%d = %d + %d\n",n,i,n-i);
                    as=0;
                    break;
                }

            }
        }
        if(as==1) printf("Goldbach\'s conjecture is wrong.\n");
    }
    }
    return 0;
}
int p(int n)
{
    int i;
    int flag=3;
    for(i=2;i<=(int)sqrt(n)+1;i=i+1)
    {
        if(n%i==0)
        {
            flag=0;
            return 3;
            break;
        }
    }
        if(flag!=0&&n>1)
        {
            return 2;
        }
        else if(n<=1)
        {
            return 3;
        }
}
]

please..anyone help.

Posted: **Sat Jun 28, 2014 6:52 am**

sampad74 wrote:i got wa.here is my code...

Right. So if you're sharing code and do use code tags at least make sure they're actually being used. How legible do you think your code looks in the post above?

Also, try putting in the statement

Code: Select all

return 0;

at the end of your main function.

Posted: **Mon Jul 07, 2014 9:12 pm**

brianfry713 wrote:

Code: Select all

generate a list of primes p
for(i = 0; ; i++)
  break if you find n - p[i] in a binary search of p

308 = 31 + 277

Posted: **Tue Nov 18, 2014 7:01 am**

Why I am getting time limit
any one please help me
here is my code

Code: Select all

#include<stdio.h>
#include<math.h>
int p[100000];
int h;
int prime(int n)
{
    int i=0,j=0,k=0,m=0;

    for(i=2;i<n;i++)
    {
        m=0;
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
               m++;
               break;
            }
        }
        if(m==0)
        {
            p[k]=i;
            k++;
        }
    }
}
int main()
{
    int i,j,n,a=0,b=0;
    //freopen("63f.txt","r",stdin);
    while(scanf("%d",&n)==1)
    {
        if(n==0)
            break;
        a=0,b=0;
        if(n%2==0)
        {
            prime(n);
            i=0;
            while(p[i])
            {
                //printf("%d ",p[i]);
                i++;
            }
            h=i;
            for(i=0;i<h;i++)
            {
                for(j=h-1;j>=0;j--)
                {
                    if(p[i]+p[j]==n)
                    {
                        a=p[j];
                        b=p[i];
                        break;
                    }
                }
            }
        }
        
        if(a>0&&b>0)
        {
            printf("%d = %d + %d\n",n,a,b);
        }
        else
            printf("Goldbach's conjecture is wrong.\n");
    }
    return 0;
}

Posted: **Tue Nov 18, 2014 9:32 pm**

brianfry713 wrote:

Code: Select all

generate a list of primes p
for(i = 0; ; i++)
  break if you find n - p[i] in a binary search of p

OJ Board

543 - Goldbach's Conjecture

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

543

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??

Re: 543 - Goldbach's Conjecture

Re: 543-goldbach's conjecture..WHY AM I GETTING TLE??