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

still not getting , Why TLE on one approach and AC on the same .
Автор vintage_Petr_Mitrichev, история, 6 лет назад, По-английски

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 .

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)$$$.

→ Ответить