vintage_Petr_Mitrichev's blog

still not getting , Why TLE on one approach and AC on the same .
By vintage_Petr_Mitrichev, history, 6 years ago, In English

AC Solution 1

TLE SOL

the first solution which gets ac , also recur for all the four case , and my 2nd solution also recur for all four cases .

But why i am getting tle at TC 6 , is there something i am missing , or something which is increasing the time complexity of 2nd sol.

someone please tell the mistake .

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Replace the following statements 

   for(ll i = i1 ; i<=j1 ; ++i) {
      left = left + s1[i] ;
    }
    for(ll i = i2 ; i<=j2 ; ++i) {
        right=right+s2[i] ;
    }

with the following

   for(ll i = i1 ; i<=j1 ; ++i) {
      left += s1[i];
    }
    for(ll i = i2 ; i<=j2 ; ++i) {
        right += s2[i];
    }

and check if this change fixes the problem. The second code should just append s1[i] and s2[i] to the end of left and right strings in each iteration, respectively. The complexity of this operation in each iteration should be $$$O(1)$$$, and the complexity of both loops should be $$$O(n)$$$. On the other hand, the first code without compiler optimization should implicitly create a hidden string object that holds the result of appending the character s1[i] or s2[i] to the end of left or right string, respectively. Then, the hidden string object is copied back to the original string. The complexity of this operation in each iteration should be $$$O(n)$$$, and the complexity of both loops should be $$$O(n^2)$$$.

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

    ok .. so the string appendation is creating problem ... in first code string is appended from the place it left while i was doing everytime from start.. thaks .. i will modify it .

    → Reply