Блог пользователя latfire

Автор latfire, история, 6 лет назад, По-английски

Hello. I recently solved the problem C of Round #490, Div3 (Alphabetic Removals). I am getting a TLE on the solution and I can't seem to find the error. My solution takes O(4*10^5) time, which should work fine. Please help. Below is my code. 39534219 999C - Alphabetic Removals

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

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
ans=ans+s[i];

This takes linear time, not constant

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    So is there no way to append a char to string in constant time?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      string.push_back(char) is amortized constant time.

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

        OK. It runs now! Thanks a lot everyone. Can't believe I spent 2 hours trying to optimize this. Never using '+' to concatenate again.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Edit: Apparently, writing ans+=s[i] also works just fine. But isn't it just another way of writing 'ans=ans+s[i]'? Can someone explain this please?

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

            ans += s[i] is add s[i] after ans

            ans = ans + s[i] is rewrite "ans + s[i]" to ans

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

              zdw1999 Though that is not true for Java. In Java, it always makes a new string, whether we write it as ans+=s.charAt(i) or ans=ans+s.charAt(i). So one has no option other than to use a character array or StringBuilder