### chromate00's blog

By chromate00, 2 months ago,

On todays contest, at 1737B - Ela's Fitness and the Luxury Number, a lot of contestants were hacked or FSTed. This is due to the inaccurate nature of floating-point types. While I do think this happening on a B is not a good thing, but it happened anyways. So as we experienced a failure this time (myself a long time ago multiple times), we need to prepare for the next time it happens.

My solution to this was using Python's isqrt function. It receives a non-negative integer, and returns $\lfloor \sqrt{x} \rfloor$. It is guaranteed to return the accurate value, so this is the perfect tool for the job. I read this blog as well, and his points are valid. I still thought telling people about the isqrt function would be a great addition to the community as well. Shoutout to -is-this-fft- for writing that blog.

Including this time, there will be many situations where there is a better tool for the job. It is a good idea to actively look for them and use them to your advantage. This is the exact reason I am writing this blog, and other blogs such as the STL in CP series as well. I hope you try to do the same when learning and practicing CP as well.

p.s. I think there should be other languages with builtins serving the same functionality, or ways to do it in the language you use. Please suggest it in the comments section below! It would be a great addition to the topic.

UPD: I just found that this wikipedia page exists, please take a look if you're interested in other methods to do this!

• +36

 » 2 months ago, # | ← Rev. 3 →   0 I shall start the addition with one possible method in C++. You can use the sqrt function, and compensate its errors linearly. As it's represented with the closest possible floating-point value, the linear search will run a constant amount of times at maximum. Here is the code. Code for C++#include #include #include using namespace std; // isqrt function follows template T isqrt(T x) { T v=sqrtl(x); if(v*v<=x)while(v*v<=x&&(v+1)*(v+1)<=x)v++; else while(v*v>x)v--; return v; } int main() { // testing code follows long long val=99999999999999999LL,a=isqrt(val); cout<val); } 
 » 2 months ago, # |   +1 for c++ use sqrtl() instead of sqrt() to get the right answer for big numbers
•  » » 2 months ago, # ^ |   +6 This works quite often, but doesn't ensure a 100% chance it will pass. It still relies on floating-point calculation, so it will be inaccurate in some way. That blog I linked in the middle of the blog explains it better than I can, shoutout to him :D
 » 2 months ago, # |   0 sir you are very orzorz chromate00
 » 2 months ago, # |   0 You can also code a Binary Search Square Root function that returns an integer. Its complexity is logarithmic and its accuracy is guaranteed
 » 2 months ago, # |   +5 i apvtoed ser
•  » » 2 months ago, # ^ |   +2 sor I thenk bot swannia peepl r vry frendly
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +2 thek u sur far lvoe nd sppot
•  » » 2 months ago, # ^ |   -6 fhenk u sur it hleps a lot
 » 2 months ago, # |   +2 i too apvtoed ser ^^ Botswanians stanting for eash atha