ycperson's blog

What is going on with this problem's test case 3?
By ycperson, history, 4 hours ago, In English

I was doing this problem: https://codeforces.net/contest/1730/problem/B and I have submitted 3 versions of binary searching on the answer and all of them are failing on test case 3 (wrong answer 36th numbers differ — expected: '40759558.0000000', found: '40759600.0000000', error = '0.0000010') -- all of them produce the same "wrong" answer.

I might be missing something stupidly obvious here but I am actually losing my mind right now. Could someone take a look at what could be going wrong?

In case you do not want to read the problem statement itself:

  • Given a bunch of functions of the form f(x) = |x — x_i| + t_i and if we define a new function g(x) as being the max across all the functions at x, we want to find the x value that minimizes g(x).

Submissions:

https://codeforces.net/contest/1730/submission/292825262 (binary searching on the position since the time function is convex) https://codeforces.net/contest/1730/submission/292826727 (binary searching on the time since it is monotonic)

Scroll to the bottom for the actual code. Thanks in advance.

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

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ycperson (previous revision, new revision, compare).

→ Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Try printf("%.9lf", ans) or std::cout << std::setprecision(9) << ans?

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

    I tried it right now and it gets to testcase 14 and has a similar issue...

    I also then tried using long double instead but no luck.

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

      Put std::setprecision(9) before possible(x, t, (l+r)/2.0).second.

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

        Yeah that worked! Thanks. I have used setprecision before but did not realize there is a difference between its placement in the printing statement.

        → Reply