Legend_11's blog

getting TLE on a problem!!!
By Legend_11, history, 9 months ago, In English

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

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
9 months ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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.

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

    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?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      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!

      → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Thanks it worked. But I dont understand why string is not working?

    → Reply
»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it 
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).

→ Reply