NeverMa573r's blog

A O(1) solution times out to a problem that has constraints t <= 2e5
By NeverMa573r, history, 19 months ago, In English

Hi, in my solution below, I created a algorithm that uses only addition, subtraction, and some simple functions to get my answer. https://codeforces.net/contest/1811/submission/202086856 However, this O(1) solution times out to this problem : https://codeforces.net/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.

  • Vote: I like it
  • +29
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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://codeforces.net/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

→ Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

O_O

→ Reply
»
19 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Reading floating point number is very slow. Read them as int and convert it to floating point numbers.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Nope. You're passing in a text file, for some reason parsing that to double with cin is very slow. You need to use scanf or read it as integers. Definitely an annoying thing in contests.

      → Reply
»
19 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Good day, reading float values with cin is slow because it performs formatted input. When you read a float value with cin it 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::precision is called with a value of std::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 tried

1- using _controlfp(_DN_FLUSH, _MCW_DN); to set the program to flush-to-zero, but it did not work.

2- using getline and stringstream because 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 getchar and putchar alongside 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.

→ Reply