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

time complexity and time limit
Автор himank, 11 лет назад, По-английски

My code (C++) is having worst case complexity of 10^8 (precisely 9*10^7 )and time limit for the question is 3 sec. I am getting TLE, so what should be worst case complexity to pass the test cases.

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

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

Sorry, question is from ongoing codechef long contest.

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

    In that case, try heavy optimization. Of course, if it's not a DP and you mean just that the complexity is like O(N2K) where N ≤ 103 and K ≤ 90, then there can be a big bad constant factor.

    Try running your code on your system and check how long it runs on some worst cases.

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

      I checked it on my system it was taking around 4 sec for worst case. But finally i corrected it and got it accepted. :) Thanks BTW.

      → Ответить