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

different time limits
Автор iscsi, 14 лет назад, По-английски

Hi,

I would like to ask what is the difference 1,5 sec, 2 sec and 3 sec time limits? :)
I see some example has different time limits but I don't see when I read the problem how should I use this information? I think the memory limit is easier to calculate of course, but I can't use this time limit information.
Could you give me some idea?

thanks,

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
You have to check the complexity of your algorithm, for example... if you write a O(N3) algorithm and the maximum value of N is 300, then the number of "simple steps" that the algorithm will make is 27.000.000 (easily fits in 1 second time limit)

The reference is: 100 millions operations per second
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I think you are forgot the constant from the big-Oh.. So the best way I should calculate the simple steps exactly before I implement my solution and check is it less then the time limit *10^9?
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Yes, but it is 108
      Anyway a better reference would be: not more than 108 operations (with a very small constant factor)
      → Ответить