__Aniket__'s blog

Why is same logic in java not working?
By __Aniket__, history, 6 weeks ago, In English

I was trying to solve Problem B from previous contest — round 976 div2. My solution is failing a testcase, its NOT TLE. Initially I thought maybe its due to Integer or Long overflow. To make sure I am not making any implementation errors, I even tried used the exact same code as given in editorial, still my code is failing testcase 8. Am I missing something, I tried reading other java solutions, but I think they encountered same problems, that's why most people used different approach while solving in java.

I am implementing the Code 1 of problem B in editorial.
Problem Link — https://mirror.codeforces.com/contest/2020/problem/B
Link to editorial — https://mirror.codeforces.com/blog/entry/134516
Link to my submission — https://mirror.codeforces.com/contest/2020/submission/284059093

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Most likely due to sqrt precision loss. Better use something like extra binary search to find an integer square root of a number. Or something like this:

https://mirror.codeforces.com/contest/2020/submission/284065784

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

    Thanks for your help, it worked! I guess it's about time I start studying the implementation of built in functions so that I understand their limitations. You taught me something new, I wouldn't have thought that people implement their own square root functions because of precision issues, I always thought they just did it for speed.

    → Reply