106 - Fermat vs. Pythagoras

[Joel J. Hernandez]

Here is my code, if you test in your computer you will see that it gives the correct answer for every input, but the judge keeps replying WA....

What is wrong?????

Code: Select all

#include <iostream> 
#include <cmath> 
using namespace std; 
struct triple 
{ 
    int x, y, z; 
}; 
void q_sort(triple numbers[], int left, int right) 
{ 
    int l_hold, r_hold; 
    triple extra; 
    int pivot; 
    l_hold = left; 
    r_hold = right; 
    pivot = numbers[left].z; 
    extra.x=numbers[left].x; 
    extra.y=numbers[left].y; 
    extra.z=numbers[left].z; 
    while (left < right)  
    { 
        while ((numbers[right].z >= pivot) && (left < right)) 
            right--; 
        if (left != right) 
        { 
            numbers[left].x = numbers[right].x; 
            numbers[left].y = numbers[right].y; 
            numbers[left].z = numbers[right].z; 
            left++; 
        } 
        while ((numbers[left].z <= pivot) && (left < right)) 
            left++; 
        if (left != right) 
        { 
            numbers[right].x = numbers[left].x; 
            numbers[right].y = numbers[left].y; 
            numbers[right].z = numbers[left].z; 
            right--; 
        } 
    } 
    numbers[left].x = extra.x; 
    numbers[left].y = extra.y; 
    numbers[left].z = extra.z; 
    pivot = left; 
    left = l_hold; 
    right = r_hold; 
    if (left < pivot) 
        q_sort(numbers, left, pivot-1); 
    if (right > pivot) 
        q_sort(numbers, pivot+1, right); 
} 
void quickSort(triple numbers[], int array_size) 
{ 
    q_sort(numbers, 0, array_size - 1); 
} 
void main() 
{ 
    int i, j, k, a, b, c, ax1, bx1, cx1, c1, c2; 
    int n; 
    int temp[750000];
    triple t[250000]; 
    while(cin>>n)
	{ 
		c1=0; c2=0; 
		if(n<5)
		{
			cout<<c1<<" "<<n<<endl;
		}
		else
		{
            for(i=0; i<=n; i++) 
            { 
                temp[i]=0; 
            } 
            i=1; k=0;
            t[0].x=3; t[0].y=4; t[0].z=5;
            while(k<i)
 	        {
                a=t[k].x;
	            b=t[k].y;
		        c=t[k].z;
	            cx1=2*a-2*b+3*c;
		        bx1=2*a-b+2*c;
		        ax1=a-2*b+2*c;
		        if(cx1<=n)
	            {
                    t[i].x=ax1;
		            t[i].y=bx1;
		            t[i].z=cx1;
		            i++;
			        c1++;
		        }
	            cx1=2*a+2*b+3*c;
		        bx1=2*a+b+2*c;
		        ax1=a+2*b+2*c;
		        if(cx1<=n)
	            {
	                t[i].x=ax1;
			        t[i].y=bx1;
			        t[i].z=cx1;
			        i++;
			        c1++;
		        }
	            cx1=3*c+2*b-2*a;
		        bx1=b+2*c-2*a;
		        ax1=2*b+2*c-a;
		        if(cx1<=n)
	            {
		            t[i].x=ax1;
		            t[i].y=bx1;
		            t[i].z=cx1;
	                i++;
		            c1++;
	            }
	            k++;
	        }
            quickSort(t, c1); 
			i=1;  
            while(t[0].z*i<=n) 
            { 
                for(j=0; j<=c1; j++) 
                { 
                    if(t[j].z*i>n) 
                    { 
                        break; 
                    } 
                    temp[(t[j].z)*i]=(t[j].z)*i; 
                    temp[(t[j].x)*i]=(t[j].x)*i; 
                    temp[(t[j].y)*i]=(t[j].y)*i; 
                } 
                i++; 
			}
			for(i=1; i<=n; i++) 
            { 
				if(temp[i]==0) 
                { 
                    c2++; 
                } 
            } 
			cout<<c1+1<<" "<<c2<<endl; 
        } 
    }
}

Thanks in advance.

[Joel J. Hernandez]

Ok thanks anyways guys.
I finally got ACC, I used dynamic memory and also my method for finding all triples is quite fast, like O(nlogn).

I submitted this program more than 30 times and always got WA or RE and it was because of the arrays thing, so be carefull.

Thank you.

I'm so happy!!!!!

[little joey]

Hi Joel,

I'm very glad for you that you got accepted, but in the process of getting there you created four new threads for a problem that has many threads already. Please conform to the forum rules, and only create a new thread if there is no existing thread for your problem, otherwise post in an existing thread.

lj

[fernando]

most problems in UVA will show Time Limit Exceeded if they run for more than 10 seconds, so maybe you are misunderstanding the meaning of your result, it means that your program ran during 10.1 seconds, and as it didn't finish you got Time Limit Exceeded, the exact time your program solved the problem is unknown

[klam]

im just wondering, can't post like this one be removed? cause this is the kind of post that makes finding what you want heavy.

[Darko]

It generates all relatively prime triples, not sure where that "some" part came from. Some numbers occur in more than one triple, but they are still relatively prime.

I just solved this, generating relatively prime triples is ok (my source is Ore's Number Theory and Its History), but counting unused numbers takes forever (5s+ with Java).

There seems to be a better way than to just count them every time, but I can't come up with it. I thought about marking them all, but then, for instance, 6 would be marked (because (3 4 5) -> (6 8 10)), but if n==6, it should be counted as unmarked.

Any suggestions?

[nev4]

Hi,
i found 13 of them as N = 100, too.
10) 56 33 65
12) 16 63 65
15) 36 77 85
These don't belong, do they?
33 = 11 * 3; 65 = 5 * 13;
63 = 7 * 9;
77 = 11 * 7; 85 = 5 * 17;
what's wrong here?

[nev4]

ah, the triple cant have the same dividers... It's hard to get right meaning.

[rk]

i am getting Invalid memory reference in 106. the prob works fine on my pc. no idea abt the error, please help....

code is

Code: Select all

# include <iostream.h>
# include <stdio.h>
using namespace std;
int p(int x,int y)
	{int a,b=(x<y?x:y);
	 for(a=2;a<=b;a++)
	 	if(x%a==0 && y%a==0) return 0;
	 return 1;
	}
int main()
	{int x,y,n,a,b,c,d,*X;
	 while(scanf("%d",&n)>0)
	 	{X=new int[n+1];for(a=0;a<n;a++) X[a]=0;
	 	 for(a=1,x=0,y=n;a<=n/2;a++) for(b=a+1;b<=n/2;b++)
	 		{d=a*a+b*b;
	 		 if((a%2==0 || b%2==0) && p(a,b) && d<=n)
	 			{x+=1;
	 			 if(!X[b*b-a*a-1]) {X[b*b-a*a-1]=1;y--;}
	 			 if(!X[2*a*b-1]) {X[2*a*b-1]=1;y--;}
	 			 if(!X[a*a+b*b-1]) {X[a*a+b*b-1]=1;y--;}
	 			 for(c=2;;c++)
	 			 	if(d*c<=n) 
	 			 		{if(!X[c*b*b-c*a*a-1]) {X[c*b*b-c*a*a-1]=1;y--;}
	 			 		 if(!X[c*2*a*b-1]) {X[c*2*a*b-1]=1;y--;}
	 			 		 if(!X[c*a*a+c*b*b-1]) {X[c*a*a+c*b*b-1]=1;y--;}
	 			 		}
	 			 	else break;
	 			}
	 		}
	 	 cout<<x<<" "<<y<<"\n";delete []X;
	 	}
	 return 0;
	}

thnx

[rk]

the idea used was

Any primitive Pythagorean triplet (m,n,p) is of the form
p=x*x+y*y
m=x*x-y*y
n=2*x*y
where x and y are co prime and at least one of x and y is even. Also all other Pythagorean triplets are simply obtained by taking multiples of these. These are well known results from number theory, and should be used to solve this problem.

[nev4]

if u get RE u probably get outside of array bounds

[hedgehog1204]

Try using less multidimensional arrays. Here is the example of my code in Python:

Code: Select all

def prime(i, j, k):						
	myMax = max([i, j, k])
	for l in range(2, myMax):
		if i%l==0 and j%l==0 and k%l==0:
			return False
	return True

file = open('input.txt')
for line in file:						
	nTriple = 0							
	n = int(line.strip())				
	triple = [0 for i in range(n+1)]		
	for i in range(1, n-1):				
		for j in range(i+1, n):
			for k in range(j+1, n+1):
				if i*i + j*j == k*k:
					triple[i], triple[j], triple[k] = 1, 1, 1
					if prime(i, j, k):
						nTriple += 1
	notPartOfTriples = 0				
	for i in range(1, n+1):
		if triple[i] == 0:
			notPartOfTriples += 1
	print nTriple, notPartOfTriples					
file.close()

Its slow but it works (with the problem statement examples that is lol)

[ulgerang]

I had "Time Limit Exceeded
I don't know what wrong is.
please , give me advice.



#include <stdio.h>
#include <math.h>

#define N 1000000
#define SQRT_N 1000

bool RP_map[SQRT_N+1][SQRT_N+1];
bool integers[N+1];



void fill_RP_map( )
{
int i,j;

for(i=0;i<=SQRT_N;i++)
{
RP_map[0]=false;
RP_map[1]=true;
}

for(i=0;i<=SQRT_N;i++)
for(j=2;j<i;j++)
RP_map[j]= RP_map[j][i%j];
}


int main()
{
unsigned long n;
unsigned long i,j,k;
unsigned long sqrt_n;
unsigned long n_prime;
unsigned long n_elements;
unsigned long sq_i,sq_j,x,y,z;


fill_RP_map();
while(scanf("%ld",&n))
{
for(i=1;i<=n;i++)
integers=0;

sqrt_n= sqrt(n);

n_prime=0;
n_elements=0;
for(i=1;i<=sqrt_n;i++)
for(j=1;j<i;j++)
{

sq_i=i*i;
sq_j=j*j;

z=sq_i+sq_j;

if(z > n )
break;

y=2*i*j;
x=sq_i-sq_j;

integers[x]=true;
integers[y]=true;
integers[z]=true;

if( (i+j)%2 && RP_map[j]==1)
{
n_prime++;

for(k=2; k*z <n;k++)
{
integers[x*k]=true;
integers[y*k]=true;
integers[z*k]=true;
}
}
}

for(i=1;i<=n;i++)
n_elements+=integers;

printf("%ld %ld\n",n_prime,n-n_elements);
}

return 0;
}

[helloneo]

you have to search first..
and don't open a new thread if one already exists

check this out

http://online-judge.uva.es/board/viewtopic.php?t=1429

[ubernewb]

I tried all the inputs I found on this board, and the output matches the correct output, but I'm still getting WA on this one. Some sample input/output here.
Input:

Code: Select all

10
100
1000
10000
100000
1000000
123
1234
12345
123456

Output:

Code: Select all

1 4
16 27
158 205
1593 1669
15919 14844
159139 133926
19 26
197 238
1963 2058
19644 18142

Any ideas? I can PM or post my source code if someone with ACC wants to see it.
Thanks