I thought 215B - Olympic Medal was an easy problem, I got the relation fairly easily, but then it gave me WA at test 10.
My first submission was:
double r2=sqrt( ((double)((r1*r1)*(b)*(p1)))/(a*p2+b*p1));
Where r1 and p1 are the maximum possible and p2 is the minimum possible, based on that relation, where its directly proportional with r1 and p2 and inversly proportiona with p2.
So I thought I may need long double, re-submitted with long double, WA again.
Then I thought the std sqrt function was not accurate enough, coded my own sqrt function.
Long story short, I made 11 WAs all trying to figure out whats wrong, until in the end I used the inverse of the relation, and voila AC from the first time !
long double r2=(1.0/(r1*r1))*(((a*p2)/(b*p1))+1); r2=pow(r2,-0.5);
But it was totally useless..the 11 WAs made my rank be 877, the lowest I ever got (so far :/)
I just hate those double precision problems...
Edit: Thanks to riadwaw, I knew what was the mistake. 5000^4 > INT_MAX, I should have kept the numerator as double to avoid the overflow. I totally admit it was my mistake for overlooking the constraints. Hopefully it would be another trick which no one would fall into again :)
I think, Problem is that you calc
(r1*r1)*(b)*(p1))in ints, 1.0 * r1 *r1 * b * p1 will workCode: 1987842
You are right !
My original first submission was:
double r2=sqrt( ((double)((r1*r1)*(b)*(p1)))/(a*p2+b*p1));Now when changed it to
double r2=sqrt( ((double)(1.0*r1*r1*b*p1))/(a*p2+b*p1));submitted it only with that change and got AC !
But shouldn't the implicit casting to double be enough ?! I made sure in my first submission that the whole numerator was casted to double not only the result of the division so it be double/int which should be divided as double. How is that any different ?
You multiply, then cast.
You may use
((double)r1) *r1 * b * p1to multiply in doubles.BTW, You may also multiply in long long's 1987919
Ah..You mean because there would be an overflow ? 5000^4 > INT_MAX so thats why I should have kept the result of multiplication as double ?
yep
ic...I admit it now being my mistake for overlooking the values..thanks a lot for your helpful clarification :)
I think it is better to avoid useless floating point operations, as they can introduce calculation error. In this case it is enough to cast the first operand to
double.Even better,
(double)(r1*r1)*(b*p1)reduces this formula to only one FP operation.I also use C++. I full agree with you.
WA on test 23 made my rank be 832. I wrote in binary search (left+right)/2. After the contest I wrote binary search (left+right)/2.000000000 and get Accepted. It's strange really.
UPD: +1 riadwaw — nice solution with binary search.
You change also next line and it's enough
1988006
Another possible formula is r2 = r1/sqrt( (p2*a)/(p1*b) + 1) This avoids overflow in any language.