OJ Board

Posted: **Tue Jul 19, 2005 7:22 pm**

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.

Posted: **Fri Jul 22, 2005 3:24 pm**

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.

Posted: **Fri Jul 22, 2005 4:09 pm**

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.

Posted: **Fri Jul 22, 2005 5:43 pm**

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?

Posted: **Fri Jul 22, 2005 5:56 pm**

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.

Posted: **Fri Jul 22, 2005 6:10 pm**

For the input:

Code: Select all

my accepted program gives:

Code: Select all

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

Posted: **Fri Jul 22, 2005 6:25 pm**

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

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.

Posted: **Mon Jul 25, 2005 5:03 pm**

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.

Posted: **Fri Dec 16, 2005 7:48 am**

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

Posted: **Mon Jan 09, 2006 6:25 pm**

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

Input:

Code: Select all

Output:

Code: Select all

Hope it helps.

Posted: **Tue Apr 11, 2006 4:48 am**

chunyi81 wrote: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

Problem statement wrote: 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...

Posted: **Tue May 16, 2006 9:43 pm**

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

Posted: **Tue May 16, 2006 9:50 pm**

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

Posted: **Tue May 16, 2006 10:03 pm**

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.

Posted: **Wed May 17, 2006 6:11 am**

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

OJ Board

106 - Fermat vs. Pythagoras

106 What is wrong?

106 Fermat Vs Pitagoras wrong sample.

106 Fermat Vs Pythagoras 0.1sec!!