alphadr's blog

Double Epic Fail :/
By alphadr, 12 years ago, In English

I thought 215B - Олимпийская медаль 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 :)

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I think, Problem is that you calc (r1*r1)*(b)*(p1)) in ints, 1.0 * r1 *r1 * b * p1 will work

Code: 1987842

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      You multiply, then cast.

      You may use ((double)r1) *r1 * b * p1 to multiply in doubles.

      BTW, You may also multiply in long long's 1987919

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          yep

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            ic...I admit it now being my mistake for overlooking the values..thanks a lot for your helpful clarification :)

            → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it -9 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Another possible formula is r2 = r1/sqrt( (p2*a)/(p1*b) + 1) This avoids overflow in any language.

→ Reply