106 - Fermat vs. Pythagoras

[Sedefcho]

Callosciurus, there was really some slightly strange interpretation
here in that problem. After looking at my code ...

... I can give you the following information.

(x = 996600, y = 1004791, z = 1415209 ) is the last primitive
triple I have pregenerated. I have 245217 primitive ones in
total ( maybe the last several ones are useless ).

Anway. Now to the point. How do I calculate the second answer ?
Well, I simply do this. I assume first the answer is N ( this means
I include them all ). In the code below this is reflected with the line:

Code: Select all

count = N;

Well, I will just post then the relevant piece of my code:
My explanations are then below.

Code: Select all

	count = N;

	for (NAT i=0; i<cnt_prim_triples; i++){
		xx = x_prim[i];	
		yy = y_prim[i];
		zz = z_prim[i];
		// if (xx>N) break;
		k = 1;
		while (k*zz<=N){
			NAT x0 = k*xx;
			NAT y0 = k*yy;
			NAT z0 = k*zz;
			if (!is_there[x0]){
				is_there[x0] = 1;
				count--;
			}
			if (!is_there[y0]){
				is_there[y0] = 1;
				count--;
			}
			if (!is_there[z0]){
				is_there[z0] = 1;
				count--;
			} 
			k++;
		} 
	}

What do we have here ?

1) cnt_prim_triples = 245217 as I have already said
2) is_there[] is just an array of 1000001 integers ( flags ),
which prior to this cycle I set all to a zero value
3) x_prim , y_prim, z_prim are the primitive triples ,
I have already pregenerated.

Note: I store my primitive triples in the following
order x_prim < y_prim < z_prim. But it is not always the case
that x_prim[i+1] > x_prim . Anyway, these are now just details.

These two numbers are

1. not part of any of our pregenerated triples

and they are also

2. not part ot any triple of the form (k*x,k*y,k*z),
where x,y,z is some of our pregenerated primitive
triples , k>=2 and k*z <= N.


So actually why do we have the number 2 as second output for N=2,...5
The reason is that the count 2 corresponds to the numbers 1 and 2
( see my definition above )
Why are the answers for 6 and 7 -> 3 and 4 respectively ?
Well, if you follow the definition above you will see that N = 6 is really
part of the triple (2*3, 2*4, 2*5) BUT the biggest element in that
triple Z = ( 2*5 ) is not >= N = 6. So 6 is not counted as an element
of some triple.

Same happens with N=7. I mean 7 is part of the tripple
(7,24,25) BUT the biggest element here Z = 25 is not >= 7. So 7 is
not counted as an element of some triple.

That is the interpretation the Judge expects from us. I agree it does
not fully match to what is written in the problem statement.

Hope this helps.

[Callosciurus]

Hi Sedefcho,

thanks for your immediate reply. IMHO the inconsistency remains: let's consider N=3. Using your definition, we know that 3 is element of the triple (3,4,5), but since z > N holds, we do not count 3. Since (3,4,5) is the smallest existing triple N = 3 cannot be part of any other triple with the same argument. Thus the output for N = 3 should be 0 3.

My program generates the same output as yours for the queries you posted before (except for N = 3, 4). Can you possibly post some more test cases? Or send me personally? That could help me to figure out what is going wrong.

Thanks.

[Sedefcho]

I have this piece of code:

Code: Select all

	cached_answers1[1] = 0;
	cached_answers1[2] = 0;
	cached_answers1[3] = 0;
	cached_answers1[4] = 0;

	cached_answers2[1] = 1;
	cached_answers2[2] = 2;
	cached_answers2[3] = 2;
	cached_answers2[4] = 2;

Which means that I handle the values N = 1,2,3,4 in a special way.

For the rest possible values of N I am doing what I described above.
Just do this and you will get ACC. What does your program print
now for N=3 ? If you print
0 3
of course you will be getting WA.

I know what I am saying for the values 1,2,3,4 does not make
much of a sense but I am pretty sure you will get ACC if you
implement it that way.

[mf]

What does your program print
now for N=3 ? If you print
0 3
of course you will be getting WA.

Why? My accepted program also prints 0 3 for N=3, and I believe this is the correct answer, since there are no triples with x,y,z in {1,2,3}.
Or have you found such a triple?

[Callosciurus]

I am desperate!

I submitted this problem so many times now, no matter whether I output 0 3 or 0 2 for this query, they all give WA. All queries I found on the board work fine. The only thing that is not entirely clear to me is what you pointed out , mf (the problem is clear, the correct way to solve it not). May I ask you to give me more queries?

Thank you.

[mf]

For the input:

Code: Select all

1
2
3
4
5

my accepted program gives:

Code: Select all

0 1
0 2
0 3
0 4
1 2

Post the source code of your program here, or send me it by PM. I'll try to help you.

[Sedefcho]

mf,

Judging by your output I would say the Judge has no
test cases with N = 2,3,4

If we assume the contrary one of us would have gotten WA.

More test cases - below.


I N P U T

Code: Select all

33221
33222
33333
33337
33339
33344
33354
33355
33356
33357
99960
99961
99962
99963
99964
99965
99966
99967
99968
99969
99970
99980
99990
99995
99999
100000
999991
999992
999993
999994
999995
999996
999997
999998
999999
1000000

O U T P U T

Code: Select all

5287 5187
5287 5187
5303 5204
5307 5205
5307 5206
5307 5206
5309 5208
5309 5207
5309 5207
5309 5208
15909 14841
15910 14841
15910 14842
15910 14842
15910 14842
15912 14842
15912 14842
15912 14842
15912 14843
15912 14843
15912 14841
15916 14841
15919 14844
15919 14844
15919 14844
15919 14844
159137 133923
159137 133924
159137 133925
159137 133926
159137 133924
159137 133925
159139 133925
159139 133926
159139 133926
159139 133926

Callosciurus, you may check these tests now.

If you still match them I would (99% sure) bet it's some input
reading problem or something like that. I mean something which
has nothing to do with your algorithm.

[Callosciurus]

Dear Sedefcho, dear mf,

thanks a lot for your help. Sedefcho, you were perfectly right, the algorithm was ok, I almost don't dare to tell you that I missed to initialize the last field of my array . I submitted both versions we discussed for the cases N=3,4 and both were accepted.

[gladiatorcn]

Here is my source code. It computes the no of relatively prime triangles correctly, but gets wrong no of non-triangle numbers. I think my calculation is right, and the answer provided wrong?

#include <iostream>
#include <math.h>
#include <map>

using namespace std;

int common_divisor(int a,int b)
{
if(a<b)
{
a=a+b;
b=a-b;
a=a-b;
}
while(b!=0)
{
int t=a%b;
a=b;
b=t;
}

return a;
}

bool prime(int a,int b)
{
return common_divisor(a,b)==1;
}

int main()
{
int n;
map<int,bool> M;

while(cin>>n)
{
int m=(int)sqrt(n);
int c1=0;

for(int i=1;i<=m;i++)
for(int j=i;j<=m;j++)
{
if(i*i+j*j<=n&&j*j-i*i>0&&2*i*j<=n)
{
M[i*i+j*j]=true;
M[j*j-i*i]=true;
M[2*i*j]=true;
if(prime(i,j)&&((i%2==0&&j%2!=0)||(i%2!=0&&j%2==0))) c1++;
}
}

cout<<c1<<" "<<n-M.size()<<endl;
}

return 0;
}

[Jan]

Try the I/O set. In my compiler your code returns wrong...

Input:

Code: Select all

10
100
1000
10000
200
300
400
500

Output:

Code: Select all

1 4
16 27
158 205
1593 1669
32 49
47 66
63 89
80 107

Hope it helps.

[smilitude]

Chocobo, your method is ok, but I think there is another way.

Use an array to mark out numbers used in all triples in the given range, maintaining the count of numbers that are not marked as in a triple. The final count you obtain is the second number.

Using C++ or Java, use a bool(C++) or boolean array. In C, a simple int array is sufficient.

I used this process to build a table in dynamic programming style. Its showing wrong output for any input! Again the problem statement says

The second number is the number of positive integers that are not part of any triple whose components are all <= N

as i went building gradually the table, i cannot see whats wrong.

Code: Select all

/*
 * this program is showing wrong output
 * first part is right, second part wrong
 *
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Triplet Triplet;
struct Triplet {
    int x,y,z;
    int highest;
};

struct{
    int total;
    long unused;
}table[1000000];

Triplet triplet[203000];
int k;
bool state[1000000];

int max(int a, int b) {
    if(a>b) return a;
    return b;
}

int gcd(int a,int b) {
    if(b==0) return a;
    return gcd(b,a%b);
}

int compare(const void *va, const void *vb) {
    Triplet *a,*b;
    a=(Triplet *)va;
    b=(Triplet *)vb;
    return (a->highest - b->highest);
}    

void init() {
    int i,j;
    k=-1;
    memset(state,0,sizeof(state));
    for(i=1;i<=1000;i++) {
        for(j=i+1;j<=1000;j++) {
            if(gcd(i,j)!=1) continue;
            if(i%2 && j%2) continue;
            
            //if(k%1000==0) printf("k--> %d\n",k);
            triplet[++k].x=j*j+i*i;
            triplet[k].y=j*j-i*i;
            triplet[k].z=2*i*j;
            /*
            state[triplet[k].x]=true;
            state[triplet[k].y]=true;
            state[triplet[k].z]=true; */
            
            triplet[k].highest=max(triplet[k].x,max(triplet[k].y,triplet[k].z));
            
            
        }
    }
}

void build() {
    long i,j;
    long trip=0, used=0;
    j=0;
    table[0].total=0;
	for(i=1;i<1000000;i++) {
        trip=0;
        //if(state[i]==false) unu++;
        //table[i].unused=unu;
        table[i].total=table[i-1].total;
        for(;triplet[j].highest<=i;j++) {
			if(!state[triplet[j].x]){
				state[triplet[j].x]=true;
				used++;
			}
            if(!state[triplet[j].y]){
				state[triplet[j].y]=true;
				used++;
			}
			if(!state[triplet[j].z]){
				state[triplet[j].z]=true;
				used++;
			}
			trip++;
		}

		table[i].unused=i-used;
        table[i].total+=trip;
    }
}
                       

int main() {
    int d;
    long x;
    init();
    //printf("total --> %d\n",k);
    //printf("memory --> %.2lf\n",(double)sizeof(state)/1000000);
    //scanf("%d",&d);
	qsort(triplet,k+1,sizeof(triplet[0]),compare);
    build();
	
	while(scanf("%d",&x)==1) {
       // printf("%d %d %d highest %d\n",triplet[x].x,triplet[x].y,triplet[x].z,triplet[x].highest);
		printf("%d %lld\n",table[x].total,table[x].unused);
    }
return 0;
}

    

Who is the prometheus to show me the light?
Looking forward for you...

[Joel J. Hernandez]

I need some serious help. Unless I'm blind I think sample is wrong.
Here is why:

Input: 25

There are only 4 primitive triples: (3, 4, 5), (15, 8, 17), (5, 12, 13), and
(7, 24, 25).
This is ok, so answer to the first question is fine.

But second part I think it's wrong and here is why:
Besides the above mentioned triples, we also have the following triples:
(8, 6, 10), and (12, 16, 20).....Now if we write the numbers that have appeared in any triple so far we get:

3, 4, 5, 6, 7, 8, 10, 12, 13, 15, 16, 17, 20, 24, 25.

Therefore, the following numbers are not in any triple:

1, 2, 9, 11, 14, 18, 19, 21, 22, 23. AND THIS IS 10 NUMBERS, which differs from sample output that is 9.

Anybody..????

[mf]

How about the triple (9, 12, 15)?

[Joel J. Hernandez]

Oooppppsssssssssssss.............
You are right.
Thanks so much. I guess then my method for finding all triples(not just primitive triples is wrong).

This is what I do for that:

loop a) starts at 1 and keeps going as long as i^2 + (i+1)^2 <=n

nested loop b) starts at i+1 and keeps going as long as k<=limit, where limit = (int)sqrt(n)

Then inside loop b) I check that i^2 + k^2<=n, if true:
I calculate the values of the numbers of the triples and then I insert that number into an array, the calculated numbers go in the array in the position of the number: e.g, x=7, then I put 7 into array[7].

Then at the end I traverse the array(which has been initialized to 0) and whenever I find a 0 I increment a counter.

this counter is the answer to question 2, since we only find 0's in the array in those position so that those numbers are not part of any triples.

Do you see anything wrong in my logic.

Thanks a lot again.

[Joel J. Hernandez]

Hi there.
I'm very sad.
My program runs in 10.1 sec which is only 0.1 sec more than the limit for this proglem....

Here is my code, which I'll romove soon.
Hope somebody gives me a hint...

#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;
struct triple
{
double x, y, z;
};
int gcd(int x, int y)
{
if(y==0)
{
return x;
}
else
{
return gcd(y, x%y);
}
}
void q_sort(triple numbers[], int left, int right)
{
int l_hold, r_hold;
triple extra;
double 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, (int)pivot-1);
if (right > pivot)
q_sort(numbers, (int)pivot+1, right);
}
void quickSort(triple numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
void main()
{
int i, j, c1, c2;
int limit;
double n;
double temp[30005];//The size of this array messes up my program.
triple triples[10005];
while(cin>>n){
c1=0; c2=0;
for(i=0; i<=n; i++)
{
temp=0;
}
limit=(int)sqrt(n);
for(i=1; ((i*i)+(i+1)*(i+1))<=n; i++)
{
for(j=i+1; j<=limit; j+=2)
{
if((i*i)+(j*j)<=n)
{
if(gcd(j, i)==1)
{
triples[c1].z=j*j+i*i;
triples[c1].y=j*j-i*i;
triples[c1].x=2*j*i;
c1++;
}
}
else
{
break;
}
}
}
quickSort(triples, c1);
i=1;
while(triples[0].z*i<=n)
{
for(j=0; j<c1; j++)
{
if(triples[j].z*i>n)
{
break;
}
temp[(int)(triples[j].z)*i]=(triples[j].z)*i;
temp[(int)(triples[j].x)*i]=(triples[j].x)*i;
temp[(int)(triples[j].y)*i]=(triples[j].y)*i;
}
i++;
}
for(i=1; i<=n; i++)
{
if(temp==0)
{
c2++;
}
}
cout<<c1<<" "<<c2<<endl;
}
}