simp1eton's blog

Floating Point Woes in VK Cup Round 2
By simp1eton, 12 years ago, In English

Hi all,

I refer you to the problem Lemmings from VK Cup Round 2.

I wrote a binary search solution, and I set my EPSILON value in binary search to 1e-12. My code is given here.

However, I still get wrong answers. For one testcase, the optimal solution will give 9.999999^-5, but my solution gave 0.0001. Can someone help me and tell me what I should do?

Also in general, may I know what most coders do when they need to have extremely accurate floating point values? I don't like coding fractions D=.

Thank you very much!

EDIT: I read the analysis, so I changed my EPSILON to 1e-18. But then I get TLE. Afterwards, I changed my code so that I run 90 iterations of binary search (Code here), but I still get wrong answer on the same testcase (testcase 12)!!

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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

vector<long long> S. long long? S.push_back((ll)(VAL * V[A[i]] / H)). casting to long long result of division? Seems suspicious.

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

    Hi,

    I need to typecast to an integer because I want to know the maximum ledge this lemming can go on to. I used long long because I was afraid that if I use int, there might be overflow.

    May I know what you recommend?

    → Reply