sam96's blog

[HELP] Getting TLE in Problem 747E Comments (round #387)

By sam96, history, 8 years ago, In English

I have written an O(n) solution using DFS but still i am getting TLE on test number 29. I don't understand why and hence i am unable to resolve the issue. I also tried using fast cin and cout but still i am getting TLE. Here is the link to the problem and link to my solution.

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

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The problem is word = word + s[i];.

The compiler interpret it as word.operator=(word.operator+(s[i]));, and both string::operator+ and string::operator= is O(n). So the loop

while(s[i]!=',') {
    word = word+s[i];
    ++i;
}

is O(n2). You can generate a very long comment "ccccccc...c,0" and test your program with it. To fix this use word += s[i]. It's amortized time complexity is O(1).

In C++, a += b is not exactly same as a = a + b. Actually they can be totally different.

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

    Thank you for the help. I did not know that. Got an AC after making that change.

    → Reply