gfonn's blog

ICPC World Finals time limit
By gfonn, history, 8 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

→ Reply