You are not logged in. Please login at www.codechef.com to post your questions!

×

Error in CF Round #499 Div2 C (Fly)

Though the editorial mentions a reverse iterative approach to solve the problem with O(N) time complexity, I used binary search to solve the problem. Even after multiple rechecks, I am unable to find the bug in my code that is causing Case 58 to result WA. Hence can anyone please point out the bug in my solution ?

Problem Link

Submission Link

asked 27 Jul '18, 22:32

jagreetdg's gravatar image

3★jagreetdg
2189
accept rate: 9%

1

I also faced same problem,this is happened due to precision loss,for my case my o/p was -1 instead of 1000000000.0000000000. this is because i don't add the error of 10^-6 for more safe you can set the lo=1e9+1 during binary search,i see many people do it only with maths. link to my soln with binary search : http://codeforces.com/contest/1011/submission/40814822 i think this will help :) happy coding:)

(02 Aug '18, 20:12) souradeep19996★

A large no of soln failed on Test Case 58. It's mainly due to precision error with doubles. What I think is this TC was designed so that soln which have incorrect condition to print -1 should fail. Your soln AC with corrections - http://codeforces.com/contest/1011/submission/40856287 Cheers.

link

answered 27 Jul '18, 22:59

aryanc403's gravatar image

5★aryanc403
2.2k1516
accept rate: 10%

edited 27 Jul '18, 23:00

Although @aryanc403 has solved your query, it's just another way of doing binary search on doubles which could make your code a little smaller..instead of checking with epsilon you increment or decrement low and high by given precision. Binary search will terminate when it finds an answer and answer will definitely be of that precision since we have incremented value by that. Have a look at code. May be it's obvious but i found this worth mentioning here if it helps :) Ask if something is not clear

My sol
https://ideone.com/lH4hwr

link

answered 28 Jul '18, 00:59

vishesh345's gravatar image

3★vishesh345
444
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,021
×655

question asked: 27 Jul '18, 22:32

question was seen: 175 times

last updated: 28 Jul '18, 00:59