Блог пользователя Delta-Sagittarius

A question about FPC
Автор Delta-Sagittarius, история, 3 года назад, По-английски

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

Теги fpc
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      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++)

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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).

        → Ответить
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится

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

          → Ответить
»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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).

→ Ответить