vintage_Petr_Mitrichev's blog

By vintage_Petr_Mitrichev, history, 7 months 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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your logic is not well explained. So I am not gonna read your code. But I will look at the base cases in recursion if I were you.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    what i am doing is if strings are same i am returning true , else if they are not .

    i divide both string into two parts , lets say s1 , s2 , s3 , s4 .

    now i am checking all 4 cases i.e

    case 1 : (s1 , s3) & (s2 , s4) leftleft rightright

    case 2 : (s1 , s4 ) & (s2 , s3) leftright rightleft

    am i clear .

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

  • »
    »
    7 months 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 .