latfire's blog

By latfire, history, 3 months 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  

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by latfire (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it
ans=ans+s[i];

This takes linear time, not constant

  • »
    »
    3 months 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?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      string.push_back(char) is amortized constant time.

      • »
        »
        »
        »
        3 months 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.

        • »
          »
          »
          »
          »
          3 months 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?

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What I do is store string as a list and when I need to print the string I just do

          print ''.join(arr)