sameer_hack's blog

Require Help in Binary Search ( Problem C :-Fly)[Codeforces Round 499]
By sameer_hack, history, 6 years ago, In English

I tried to solve this question using Binary Search. And I am not able to understand why one of my solutions is giving me the wrong answer while other got accepted.
Problem Link
Submission 1 (Wrong)
Submission 2 (Accepted)
Submission 3 (Accepted)

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

if(r>1000000000) ===> Can return the wrong result if you compare 1000000000.0 to 1000000000 due to floating point error

writing if(r>1000000000+0.000001) should be enough

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

WNG has already given the answer to your question, but I would like to add one more thing here. Although, I did the same mistake for this problem and got WA, after reading the editorial I came to know that the test actually was not needed at all. This is what the editorialist did: If any of the a[i]s or b[i]s is 1, then at that planet, with k units of fuel, and m (> 0) total mass, k units of fuel will never be able to lift m + k (> k) units of total mass of rocket, and in that situation the answer will be -1. In any other case (a[i] > 1 and b[i] > 1), we can find some amount k that can lift or land the total mass of rocket. So, in conclusion, if any of the a[i]s or b[i]s is 1, the answer is -1, else the answer exists and we don't need to check for the condition that involves comparison of floating point numbers, so we can directly output l or r.

→ Reply