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

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

I cant figure out reason for TLE, code seems to be O(n) with some small constants, any help would be appreciated.

Problem Link : https://codeforces.com/contest/1251/problem/C

Code

Thanks!

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

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

For inputs like $$$\underbrace{9999...9}_{n/2}\underbrace{8888...8}_{n/2}$$$, the number of swapping steps needed is $$$n/2$$$ for each of the $$$8$$$ digits, so it takes $$$(n/2)^2 = O(n^2)$$$ steps in total. Your code seems to simulate each swapping operation step by step, and hence $$$O(n^2)$$$ time complexity.

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

Err... It seems that the code you wrote was much faster.
Sorry to disturb :(