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

Автор gfonn, история, 8 лет назад, По-английски

Hi! I was reading the problems of WF 2015 and I noticed that the time limit is HUUUGE, for example this https://icpc.kattis.com/problems/tiles

Why is it so much big? I know that there are many test cases in just one input, but I have seen the same in other problems from WF 2015 that have only one test per input.

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

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

I just want an answer, please don't downvote without explaining why.

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

The bigger time limits are, the bigger can limitations be. Then we can distinguish solutions better.
You have probably heard that polynomial solutions are better than exponential. Oh really? n should be up to 60 to prove that O(n10) soltuion is better than O(2n). But both solutions will work almost infinitely on such an input. If we could set TLs like 1 year, it will be almost impossible to sqeeze O(n2) solutions when needed.