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

Suggest me remove TLE

Автор BBBB, история, 4 года назад, По-английски

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 ??

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

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

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

Use these two lines after main function

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      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.

      → Ответить