latfire's blog

Getting TLE when it shouldn't
By latfire, history, 6 years ago, In English

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

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

Comments Comments (7)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it 
ans=ans+s[i];

This takes linear time, not constant

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      string.push_back(char) is amortized constant time.

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

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            ← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              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

              → Reply