10512 - A Day in Math-land

[shahriar_manzoor]

Yes my judge solution thinks about this case and handles it but while setting the problem I willfully did not keep two traps to keep it solvable during contest:

a) This trap. Giving such inputs such that x<y

b) Giving such input where the value of x and y will be very nearly integers to give floating point users some trouble.


And now I stick to my generousity although I am a mercyless problemsetter in general

[carneiro]

but how does your solution handles it Shahriar ? I've madethe test you suggested, i've created a 84 MB file of X's and Y's, then from this file I generated a P's a Q's file (84 MB of data). Then I ran my program on the P and Q file, and used DIFF on my solution and the original xy file. The result was flawless.

I tried it several times and always flawless results. So, I'm affraid I don't know what else I can do.

This input you are talking about, the 45 4 , my program replies Impossible. Which is correct by the problem statement. What else could I do shaahriar ?

[shahriar_manzoor]

carneiro, mail me your code at shahriar@neksus.com if it is written in C/C++. As I got another Pascal code to judge but could not do it as I don't have a good pascal compiler

[shamim]

I considered one additional thing,

It may be the case that X is an integer, but Y is a floating point value, this case will not yield a desired answer.

[erfan]

if any code gives the result such that
input 45 4
output 4 5
it should WA(as my one code which AC)
when the output Impossible
then it AC.
Am i wrong or correct Shahriar?

[shahriar_manzoor]

U r right but there is no such inputs in judge input file as I explained. so that does not count. Actually the generator was written in that way.

It does not matter what your code gives output for 45 4, as there is no such input.

[Ronaldo]

[cpp]
#include<iostream.h>
#include<math.h>
long x,y,p,q;
long A[50000];
int main()
{
bool k;
long E,e,D1,D2,arm;
cin>>E;
bool sxal;

for(e=0;e<E;e++)
{
k=1;
sxal=1;
cin>>p>>q;
long h;

D1=(long)pow(p+3*q,2)-8*q*q;
arm=(long)sqrt(D1);
if(D1<0 || arm*arm!=D1)
{
cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";
continue;
}

if((p+3*q-arm)%4==0)
{
D2=(p+3*q-arm)/4;
if(D2>=0)
{
arm=(long)sqrt(D2);
if(arm==0)
{
if(p>=0)
{
h=(long)sqrt(p);
if(h*h==p)
{
x=arm;
y=-h;
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
}
goto qqq;
}
if(arm*arm==D2 && (arm*arm-q)%arm==0)
{
x=-arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}

}
}
}
qqq:
arm=(long)sqrt(D1);
if((p+3*q+arm)%4==0)
{
D2=(p+3*q+arm)/4;
if(D2>=0)
{
arm=(long)sqrt(D2);
if(arm==0)
{
if(p>=0)
{
h=(long)sqrt(p);
if(h*h==p)
{
x=arm;
y=-h;
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
else
{
cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";
continue;
}
}
else
{
cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";
continue;
}

}
if(arm*arm==D2 && (arm*arm-q)%arm==0)
{
x=-arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
x=arm;
y=(x*x-q)/x;
if((x+y)*y==p && (x-y)*x==q && x>=y)
{
cout<<"Case "<<e+1<<":\n";
cout<<x<<" "<<y<<endl;
continue;
}
}
}
}


cout<<"Case "<<e+1<<":\n";
cout<<"Impossible.\n";


}

return 0;

}[/cpp]

[hujialie]

I nearly got despaired about this problem!

When I use integar, I got Time Limit Exceeded,
when I change to double, wrong answer.
Who can give some additional tests?
My programme could pass all tests mentioned above in this post.

Thank you.

[erfan]

You don't need critical judge data cause you can create it.
by using random function in following equation:
(x+y)*y=p;
(labs(x-y))*x=q;
You can create two file in where one is for
x y
and another is for
p q
Now make second file is your problem's(10512) input and first file is judge output.Find difference between your code's output and judge output and solve them.Mind it, input may be negative.

[LittleJohn]

alright, i've written both solutions, one with doubles and another with integers and my hand-made sqrt with binary search, using long long, and both still WA.

My Baskara coeficients are :

a = 2;
b = ((-3)*P) - Q;
c = P*P;

this is for finding (y*y). Isn't that wrigth Shahriar ?

I got the same coefficients as carneiro's.
But I have a problem, how can I determine whether b*b-4ac is a square number or not?
b*b-4ac = (-3P-Q)^2 - 4*2*P^2 = P*P+6*P*Q+Q*Q
In worst case, P=Q=(2^31-1)
and P*P+6PQ+Q*Q will probably larger than 2^64 (unsigned long long)
I wander why long long or double can solve that.
Or I have to get another coeffieients?

[windows2k]

I got the same coefficients as carneiro's.
But I have a problem, how can I determine whether b*b-4ac is a square number or not?
b*b-4ac = (-3P-Q)^2 - 4*2*P^2 = P*P+6*P*Q+Q*Q
In worst case, P=Q=(2^31-1)
and P*P+6PQ+Q*Q will probably larger than 2^64 (unsigned long long)
I wander why long long or double can solve that.
Or I have to get another coeffieients?

I use long long and get accept
I assume the condition which is larger than 2^64 doesn't exist.

[ericschmidt]

Dear Shahriar, dear carneiro,

First of all I want to congratulate You, Shahriar, on this very interesting problem 10512 (A Day in Math-land) which is exactly my taste. I've got AC (after a few "learning cycles") and I've also chosen the "pure" integer arithmetic solution (using long long and a self written sqrt-routine).

I would like to add some remarks to your posting.

I'm quite sure the programmer trying to solve 10512 is able to derive the algebraic equation for X = f(P,Q) and Y = f(Q,X). The "widest" expression within this equation is (P*P + 6P*Q + Q*Q). With the restriction of |P| < 2^31 and |Q| < 2^31 this still would need 67(!) bit (signed) integer arithmetic ... which is beyond the C-type long long. Due to the special "counteracting manner" of the terms (X+Y) in P and (X-Y) in Q (and the limitation of X and Y to 16 bit signed integer) the valid solutions do in fact leave the upper expression within the range of long long. This does not mean that long long overflows need not be looked after! But they can easily be detected and then are treated as "Impossible.".

The following valid input combination is such a case (result: Impossible.):
1344981044 1749643350
the mathematical solution would actually be: X=52325, Y=18887 (where X is outside the specified 16 bit signed integer range).

I assume that this range of input numbers is also part of the test cases.

I've not really managed to "prove" that P-Q-combinations with the upper expression beyond 64 bits cannot lead to valid solutions ... but this is what I've learned from my experiments with random test data.

I've learned another thing from the random test data: If you pick an arbitrary X-Y-combination and calculate P = Y*(X+Y) and Q = X*(X-Y) as input data from it, the program "always" calculates the same X-Y-combination as output and never the "2nd possible solution". Even after running through millions of test cases I could not see that happen yet. Due to the restrictions of both solutions having to be integer dividers of P or Q these "two solution cases" are very very rare. Has anybody found one of these yet? They should also be used for the test cases ... but this could also be an idea for another computer programming problem.

Yours, Eric

[Master]

I have got this problem AC just now.
i have found a great help on this bord.
Though my code is large but it work very fast.
I use double.

you can try te following input.

0 0
1 0
0 -1
1 1
-1 -3

M H rasel
Cuet Old sailor

[mhacm]

Can anybody post some tricky Input/Output test cases.

I have read the previous posts and tried all the cases posted already.
My code passes all those tests but I get WA after 1 second. I still think there must be some tricky test cases where my code fails.

So please post some tricky cases where your AC code passes those tests.

Thanks

[AndreiCsibi]

After I used all the tricks in this section and also used long long and __int64, I got TLE. I tried to print these types with gcc 4.9.8 and Visual C++ with cout or printf and %lld or %I64d and these functions don't know how to print negative numbers!!! Please tell me where's the mistake.
P.S. What is the compiler used by the online Judge? I couldn't find it!

Andrei Csibi.