When solving problems in competitive programming, it is almost never a good idea to use the following inbuilt C++ functions. You will be hacked or fail a pretest or worse, a systest.
Why? Because they use floating-point numbers. They are designed to be used with a floating-point input and a floating-point output. The issue is that on a floating-point number, the result may not be exact. Worse, floating-point numbers may not be able to accurately encode the integer.
To calculate $$$\lfloor \frac{a}{b} \rfloor$$$ for positive integers $$$a$$$ and $$$b$$$:
- Don't use
floor((double) a / (double) b)
or similar. - Do use
a / b
. It will round down. - Warning: be careful with negative numbers. The answer depends on whether we should round down or towards 0.
To calculate $$$\lceil \frac{a}{b} \rceil$$$ for positive integers $$$a$$$ and $$$b$$$:
- Don't use
ceil((double) a / (double) b)
or similar. - Do use
(a + b - 1) / b
. - Warning: the same caveat goes for negative numbers as before.
To calculate $$$\lfloor \sqrt{a} \rfloor$$$ for a nonnegative integer $$$a$$$:
- Don't use
sqrt(a)
or similar. - Do use binary search to calculate the square root.
To calculate $$$a^b$$$ for nonnegative integers $$$a$$$ and $$$b$$$:
- Don't use
pow(a, b)
or similar. - Do use the naive algorithm. If you really want to do this and $$$a^b$$$ fits in a long long, then it will take no more than 64 steps, unless $$$a = 0$$$ or $$$a = 1$$$, in which case you can just return $$$a$$$.
To calculate $$$\lfloor \log_2 (a) \rfloor$$$ for a positive integer $$$a$$$:
- Don't use
log2(a)
or similar. - Do use
__lg
or an approach based on__builtin_clz
or__builtin_clzll
. The "clz" stands for "count leading zeroes" and it does exactly what it says — on the binary representation of the number. If you have access to C++20, there is also thebit_width
library function. - Warning:
__builtin_clz(0)
and__builtin_clzll(0)
are undefined behavior.
Exceptions
The only major exception is if floating-point numbers are an inherent part of your solution. Most commonly, this happens in problems where the output is itself a floating-point number (especially geometry problems, sometimes probability). There are also some algorithms where you need to work with floating-point numbers even if the input and output are integer (FFT, possibly some LP).
But even in these cases, it's always a good idea to do as much as possible with integers and move to floats as late as possible.
I got WA with one compiler, accepted with another
Most likely it has to do with 64-bit versus 32-bit. Also the widths of the various floating-point types vary. It's possible that in some circumstances your solution is actually correct. However, rely on this only if you know what you're doing.