srijon_32's blog

Stuck in problem. sqrt ( mid ) * sqrt ( mid ) > mid how? please help.
By srijon_32, history, 2 hours ago, In English

I was looking for a solution to a problem. I saw this in a function of that solution:

bool good(ll mid) { ll x = sqrt ( mid ); while( x * x > mid ) x-- ; while( ( x + 1 ) * ( x + 1 ) <= mid ) x++ ; return mid -x >= k; }

how is it possible that: sqrt ( mid ) * sqrt ( mid ) > mid ? or ( sqrt ( mid ) + 1 ) * ( sqrt ( mid ) + 1 ) <= mid ?

all this sqrt has floor value.

That problem link: https://mirror.codeforces.com/contest/2020/problem/B

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

»
119 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
52 minutes ago, # |
  Vote: I like it +1 Vote: I do not like it

sqrt acts on floating point, so there can be slight imprecision issues that require you to shift it around to get it to be correct. But it's much faster to use this to find the integer square root than to binary search.

→ Reply