search

Kattis / problemtools

Tools to manage problem packages using the Kattis problem package format.
MIT License
101 stars 70 forks source link

Timing calculation needs to be conservative #220

Open rokicki opened 1 year ago

rokicki commented 1 year ago

I have one problem where slowest AC is 0.94, and time multiplier is 1.5.

Verifyproblem (and presumably Kattis as well) does the calculation as follows:

round(0.94 * 1.5 + 0.5) => 1s

(See https://github.com/Kattis/problemtools/blob/develop/problemtools/verifyproblem.py#L1400).

giving a 1s time limit. This is much too close to the slowest AC. I propose the actual algorithm should be:

ceil(0.94 * 1.5) => 2s

This would have the effect of adding an everage of 0.5s to all time limits, but it would resolve this important corner case.

meisterT commented 1 year ago

Does Kattis support non integer time limits?

simonlindholm commented 1 year ago

Rather than ceil I guess the mathematically correct thing to do would be to round geometrically, i.e. to whichever one of floor(0.94 1.5) and ceil(0.94 1.5) is closest after taking logs.

Kattis does not support non-integer time limits, unfortunately.

rokicki commented 1 year ago

That seems unnecessarily complex and unintuitive. And it wouldn't even help in this case; it would still round to 1s, which is too close to the worst AC of 0.94 to be reasonable. (log(0.94 1.5/1) = .1492; log(2/(0.94 1.5)) = 0.1518; this algorithm would choose 1s.)