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

Автор nipungupta37, история, 5 лет назад, По-английски

https://codeforces.net/contest/1251/submission/76981021 can someone tell why this code is giving TLE? the complexity seems fine to me?

question link... https://codeforces.net/problemset/problem/1251/C

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

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

Auto comment: topic has been updated by nipungupta37 (previous revision, new revision, compare).

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Because you worst case time complexity is O(n^2).

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

      isnt it O(10*n)?

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

        Look at this line from your code (there are 3 such lines):

        s3 = s3 + s[j];
        

        At worst, this is executed $$$n$$$ times per iteration of the outer loop. Each time, the program creates the concatenation of s3 and s[j], which could take $$$O(n)$$$ time, then assigns this concatenation to s3, which takes another $$$O(n)$$$ time to delete the old version of s3 and assign the new string. To fix this, you would want to do s3 += s[j], which doesn't re-create the string every time, or even better: s3.push_back(s[j]), which is faster performance-wise.