Hi, in my solution below, I created a algorithm that uses only addition, subtraction, and some simple functions to get my answer. https://mirror.codeforces.com/contest/1811/submission/202086856 However, this O(1) solution times out to this problem : https://mirror.codeforces.com/contest/1811/problem/B
Can I have an in depth explanation as to why this is the case? I suspect it is because I'm using doubles, but even then I don't see how this can cause such it to be so slow.
I can confirm, if you use int instead of doubles then this code passes easily (taking 20~30x less time for each test case)
https://mirror.codeforces.com/contest/1811/submission/202277743
So somehow float max(), conversions between float/int/str, or float abs() is very slow. But I haven't noticed anything like that before. Super strange
O_O
Reading floating point number is very slow. Read them as int and convert it to floating point numbers.
Why is that? Since I am only passing in integer values, shouldn't it just be an integer conversion from an integer input to a double value? Pardon my ignorance, I am not too familiar with IO
Nope. You're passing in a text file, for some reason parsing that to double with
cinis very slow. You need to usescanfor read it as integers. Definitely an annoying thing in contests.Good day, reading float values with
cinis slow because it performs formatted input. When you read a float value withcinit has to parse the input stream character by character, checking for digits, decimal points, signs and exponent symbols. once it has parsed the input, it has to convert the string representation of the number into a floating-point value, which involves a lot of arithmetic operations.on the other hand, when you read an integer value with cin, it's much simpler because the input is a sequence of digits with no decimal point.
In general, implicit conversions can be slow because they involve more complex operations than explicit conversions. There are a lot of reasons for that such as:
when
std::ios::precisionis called with a value ofstd::numeric_limits<double>::max_digits10, it sets the precision to the maximum number of significant digits that can be represented by a double value. while this can be useful for ensuring that the full precision of the input value is retained, it can also slow down the reading of floats with cin, as the program has to process a potentially large number of digits for each input operation... --------------I tried a few solutions. Other than the obvious solution of using
scanf, I tried1- using
_controlfp(_DN_FLUSH, _MCW_DN);to set the program to flush-to-zero, but it did not work.2- using
getlineandstringstreambecause they allow you to read in the input data as a string and then parse it into a floating-point value. but that made it even slower...3- using
getcharandputcharalongside with fast input output user-defined functions. Since CodeForces uses WindowsOS to compile, using those would be optimal. (still, please just use printf and scanf and avoid writing spaghetti code).The template that I used was inspired by Sergey Kopeliovich ( https://acm.math.spbu.ru/~sk1/algo/lib/optimization.h.html ). But upon reading my AC code, you will see that my version is slightly different from his. The reason for that is I don't like standard templates as they make your code practically unreadable. Here is my AC answer.