weakestOsuPlayer_244's blog

Dealing with '+' and append in C++

By weakestOsuPlayer_244, history, 4 years ago, In English

Hello guys.

I was trying the problem https://mirror.codeforces.com/contest/182/problem/D

The intended complexity of my solution is supposed to be $$$O(n\sqrt{n})$$$ but somehow I was repeatedly getting TLE. When I switched the concerned part where I was using + for concatenation of two strings with append it got accepted.

I went over to stackoverflow for figuring out the cause but I couldn't understand much of it besides trying the reserve keyword. I also tried using the reserve keyword for reserving space for the string but it resulted in TLE as well.

Here are my submissions:-

https://mirror.codeforces.com/contest/182/submission/82678284 -Using append.

https://mirror.codeforces.com/contest/182/submission/82677975 -Using + for concatenation.

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

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

Using temp1=temp1+temp2 takes O(n) as it copies the first string, adds the second to it and then stores it back in first Edit: Someone please correct me in the comments if I am wrong

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

    It's probably O(n) for a single operation but repeating it over and over seems to tend towards higher complexity. (Otherwise my code would have gotten accepted)

    I think so..

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

Basically s=s+t creates a new object by copy s, then appends t, then moving the result to s. s+=t simply appends t, without copying s.

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

If there are 'n' strings of length 'x' then time complexity of concatenation will be O(x*n^2). Appending gives a linear time complexity.

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

I ran and got AC with your code by replacing a=a+b with a+=b. The runtime difference is strikingly large. The AC submission ran for just 124ms

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

    Yes thanks for your reply. I changed it and it got AC too. Using a+=b; probably prevents creation of the new object as stated above by spookywooky.

    → Reply