Timing calculation needs to be conservative

[rokicki]

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]

Does Kattis support non integer time limits?

[simonlindholm]

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]

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.)