10512 - A Day in Math-land

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Not so bad this time

Post by shahriar_manzoor » Sun Jun 22, 2003 3:26 pm

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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Sun Jun 22, 2003 5:40 pm

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 ?
[]s
Mauricio Oliveira Carneiro

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

mail me

Post by shahriar_manzoor » Sun Jun 22, 2003 5:58 pm

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 :(

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

One suggestion

Post by shamim » Mon Jun 23, 2003 8:25 am

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
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

Post by erfan » Mon Jun 23, 2003 9:44 am

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

You r right

Post by shahriar_manzoor » Mon Jun 23, 2003 10:14 am

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
New poster
Posts: 5
Joined: Fri May 23, 2003 1:45 pm

WA Pelase Help

Post by Ronaldo » Tue Jul 01, 2003 9:16 pm

[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
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Post by hujialie » Sun Jul 13, 2003 3:57 pm

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.
Retired from SJTU Accelerator 2004

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

Post by erfan » Mon Jul 14, 2003 3:42 pm

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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Sun Aug 03, 2003 8:13 am

carneiro wrote: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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Wed Aug 06, 2003 10:45 am

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
New poster
Posts: 16
Joined: Mon Jan 06, 2003 9:27 pm
Location: Grosskrut, Austria

10512 - Where's the tricky input?

Post by ericschmidt » Sun Aug 10, 2003 8:14 am

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
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master » Fri Aug 29, 2003 12:40 pm

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
New poster
Posts: 10
Joined: Wed Jun 25, 2003 1:39 pm

Can anybody post some tricky Input/Output test cases

Post by mhacm » Sun Aug 31, 2003 3:03 pm

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
New poster
Posts: 2
Joined: Thu Aug 21, 2003 2:53 pm
Location: Romania
Contact:

Printing long long or __int64 fails with cout or printf!?!?!

Post by AndreiCsibi » Sun Aug 31, 2003 10:40 pm

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.

Post Reply

Return to “Volume 105 (10500-10599)”