ilove_sundarKanya's blog

A Blunder That Stopped Me From Being a Pupil (sqrt DANGEROUS!!!)
By ilove_sundarKanya, history, 3 weeks ago, In English

In today’s Div. 2 contest, I encountered a frustrating issue that taught me the importance of precision in competitive programming.

The problem logic seemed straightforward: identify odd perfect squares. Confidently, I implemented the logic in my code editor (VS Code), tested a few cases locally, and it seemed flawless. However, when I submitted the solution during the contest, it gave Wrong Answer on Test 1 repeatedly.

Problem:

I couldn’t accept that such an easy problem was slipping away. Frustration kicked in as I spent over 40 minutes debugging and even tried different C++ standards like C++17, C++20, and C++23, only to face the same result: Wrong Answer on Test 1. Disheartened, I shifted my focus to solving other problems, managing to complete Question B and Question C before circling back with just 30 minutes remaining.

After some reflection and experimenting, I finally pinpointed the issue:

Incorrect Code

It turns out that floating-point arithmetic caused the issue. sqrt(n) * sqrt(n) does not always yield exact results due to precision errors in floating-point operations.

I replaced it with a safer and integer-based alternative:

Correct Code

This resolved the issue instantly, but by then, the damage was done. The time lost on debugging and the rank I could have earned were irrecoverable.

I hope whoever reads this avoids such a mistake in the future.

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Yeah. The same thing entered my mind when i first saw the problem. I too created a different function for calculating square root. The constraints were very small so it was pretty easy

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it 
int x = sqrt(n);

while (x * x < n) x++;

while (x * x > n) x--;

I saw this trick a while ago, and I think it is the safest option.

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

    Yes I did the same. I got the mistake after 1:30 hour. This was too harmful for me.

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

u can just do sqrtl(r)

always give accurate

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

    I used int everywhere once so that sqrt can be used. But even that didn't worked. But I will try sqrtl. Thanks for the help :)

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

I have seen sqrtl while not completely safe hasn't caused me any issues for sometime, beware of this happening in pow function or any other double returning function.

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

Use binary search

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For problems like this I think it is better to use

if(floor(sqrt(n)) == ceil(sqrt(n))) return true

. This is because if it is a perfect square, it doesn't have anything after decimal so its floor and ceil would be the same. You could implement the condition in 1 line saying

if((floor(sqrt(n)) == ceil(sqrt(n)) && (n&1)) //because square of odd is odd and even is even

Although this clicked me after the contest. I wasted 10 mins on A doing it via binary search by storing the squares I don't know why I did that but it could have been solved in 2 mins if I did what I said just now. Need to work on my implementation. I fucked up the implementation in B too which made my code unnecessarily long which could have been done in much lesser lines.

→ Reply