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

Автор Legend_11, история, 8 месяцев назад, По-английски

Hello codeforces community, I am getting a weird TLE on this problem: https://mirror.codeforces.com/contest/1932/problem/E

Here is my code submission : https://mirror.codeforces.com/contest/1932/submission/250505488

I am sure my solution is linear but still I am getting TLE.

I am unable to find the error which is causing TLE. Please help me. Thank you

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

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

The code line res=to_string(a)+res; seems to be the problem since evaluating the concatenation of two strings always takes $$$O(n)$$$ time to compute in C++, even if you are just prepending a single character. Additionally, since a C++ string is extensible at the end only (adding characters to the front causes the entire string to be shifted to the right by one place, taking linear time), calling .insert() on the string would've still taken linear time.

A solution to this problem is to store the contents of the res string in reverse so that every prepending operation becomes an appending operation instead, which takes $$$O(1)$$$ time. (The entire string can be reversed at the end, yielding the correct answer). Alternatively, you can also use a deque<char> instead of a string since the former is able to be extended on both sides.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
8 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
res=to_string(a)+res;

The above code works in $$$O(|res|)$$$ you are doing this $$$O(|res|)$$$ times so it takes $$$O(|res|^2)$$$ time which is bad.

Instead you should append the characters to the back of res and reverse it after the while loop is over to get the same result. (note that for appending string s to t you should use t += s NOT t = t + s).