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

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

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

Here is my code submission : https://codeforces.net/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 Проголосовать: не нравится

    even this code : https://codeforces.net/contest/1932/submission/250509019 in which I am appending the character to the string is not working . is there any problem with using strings?

    → Ответить
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится 
      while(res[0]=='0')
{
    res=res.substr(1);
}

      I think this block of code may be causing the TLE, since the .substr() method creates a new string, which costs $$$O(n)$$$ time. Since the method is called repeatedly in the loop, the time cost can be large enough to cause TLE.

      Instead, I think a better approach may be to find the position of the first nonzero digit, store the position, and then call .substr once. I have made this modification to your code (https://codeforces.net/contest/1932/submission/250510146) and now it runs under the time limit. Hope this helps!

      → Ответить
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Dont use strings. I modified your code: https://codeforces.net/contest/1932/submission/250507393

→ Ответить
»
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).

→ Ответить