Delta-Sagittarius's blog

A question about FPC
By Delta-Sagittarius, history, 3 years ago, In English

https://codeforces.net/contest/1620/submission/139785121

Here is my code, anyone can find this code is O(n) time complexity. I tried to read the string using different read methods, but I got a verdict of exceeding the time limit at the fifth test point.

https://codeforces.net/contest/1620/submission/139786622

After converting the FPC code to C++ code, I get the Accepted verdict.

I would like to know why FPC is getting out of time limit.

Thanks in advance for reading and replying.

Tags fpc
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

strlen is $$$O(string_{length})$$$ no matter how many times you run it, not $$$O(1)$$$, so not even your C++ code won't run in linear time per test.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    You are ignoring C++'s compiler optimization, where the result of strlen is automatically saved before the loop.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Sorry, I didn't know that, but your point is still weird. Maybe you will need to use a judge which evaluates your code with -O0, or maybe you will have to use a compiler which doesn't employ this optimization.

      I looked online now and your point is in a comment, but other people argue that having the string declared globally or not having the string const char * could stop the optimization from taking place.

      I still think that using strlen like this in a loop condition is dumb and could easily backfire, especially when you can use std::string with size() or length() or even for (int _ = strlen(s), i = 0; _; _--, i++)

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I merely agree with your point. However, there are 2 things I want to notice:

        1) Providing the code is executed with -O0, it runs in $$$O(n^2)$$$, and the upper bound for output is the same. So, in fact, the complexity is fine.

        2) I personally do not like the style for (int _ = strlen(s), i = 0; _; _--, i++). Too easy to make a mistake. I would prefer smth like this: for (int _ = strlen(s), i = 0; i < _; ++i).

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          I agree with both of your arguments! Your way of writing the foris objectively better, I just wanted to show an example.

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

It seems that outputting string character by character is way too slow in pascal. I've copied your code, replaced many outputs with one and got AC: 139885829 (out += chr(13) is the way to append new line symbol to the string).

→ Reply