BBBB's blog

Suggest me remove TLE

By BBBB, history, 4 years ago, In English

Dear guys I face TLE problem .. here I use only loop bt face this tle on test case 11 .. https://codeforces.com/contest/1354/submission/83116758?fbclid=IwAR2sL6R3we-kMkjMkvGJQJ1Kep1Dj8j-ovhb-MD5omCM18trUbm3tTwLUU0 What's the time complexity of my code what should I need to change ??

  • Vote: I like it
  • +1
  • Vote: I do not like it

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

ios_base::sync_with_stdio(false); cin.tie(NULL);

Use these two lines after main function

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your code runs in O(N^2) worst case, since C++ STL accumulate is O(N). I don't completely understand your code, but this problem should be solvable using two pointers. Or if you want you could probably optimize accumulate into some sort of running sum.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    after your suggestion i solve it another way use only loop and dont use stl accumulate ..bt this time i get tle on test case 17 https://codeforces.com/contest/1354/submission/83216445 i dont understand what happened on this ..

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Why are you so lazy? Look at test case 17, and try to run your code on something similar (1212121212.....12123). You will quickly realize that your code runs >2s on lengths as small as 60000, suggesting that it runs in O(N^2). Since you have only one cycle, put int cnt = 0; before it and cnt++; inside. You will notice that cnt ~ N^2, meaning that you don't increase i every time in your cycle (spoiler: for each s[l] you run the loop l+1 times!). Just debug your code on your sample and you will understand what goes wrong.

      → Reply