4 ms·
> It needed to run in less than 1 second I've always wondered how these competitions measure the program's runtime consistently. I guess the easiest way would
by tinalumfoil 10y ago
> It needed to run in less than 1 second
I've always wondered how these competitions measure the program's runtime consistently. I guess the easiest way would be to specify the CPU the program will run on and use the bash `time` builtin, but that seems inconvenient for participants to obtain that CPU and controlling for the cache might be difficult (maybe a kernel module that clears the cache before the program runs and make sure the program runs fully in cores dedicated to that program and is consistent enough with memory accesses so L3 is comparable).
On the other hand they could just count instructions run, which would be completely deterministic, but might lead to some "optimizations" that don't make sense like using `rep movs` to zero memory instead of loops. Using a higher-level bytecode would have the same problems. They could also give different values to each instruction and possibly memory access, but even then students would be ignoring important real-world cache or pipeline optimizations.
But maybe I'm just overthinking this. This type of problem would be better suited for GPUs anyway.
- ludamad 10y agoThe time limits are overkill except if you chose the algorithm wrong.
- ufo 10y agoIn fact, you can often get a good ballpark-estimate of what big-O runtime your algorithm needs to have, just from the time limit. This can work as a hint on how to solve the problem.
- deleted 10y ago[deleted]
- squeaky-clean 10y agoThe other commenters are right, the time limits were a non-issue if you chose the right algorithm. It might be the difference between solving it in 30 years and 300ms. I'm probably misremembering that specific problem, but they were typically very easy problems, but with a huge n and some small 'gotcha' to the scenario that allowed an algorithmic or dynamic programming trick. Not realistic at all, but they were lots of fun. All of the problems weren't like that, but those were the hardest to get.