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

[gkreitz]

https://www.kattis.com/problem-package-format/spec/2023-07-draft.html#problem-timing now specifies how to compute time limits, which seems to boil down to ceil(0.94 * 1.5) in this case (there's also a time_resolution, but this defaults to 1). As legacy does not specify anything, I'm considering just using the 2023-07-draft method for both formats, which would solve this issue.

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

Would non-integer time limits be useful? It's a bit of work, but I don't see any huge difficulties if we wanted to support that. I am a bit doubtful about the practicality of them though, once we get down to time resolutions of .25 or .5 seconds, I'd start worrying about things getting more fragile.

[simonlindholm]

Would non-integer time limits be useful? It's a bit of work, but I don't see any huge difficulties if we wanted to support that. I am a bit doubtful about the practicality of them though, once we get down to time resolutions of .25 or .5 seconds, I'd start worrying about things getting more fragile.

I had the wish for a 0.5 second time limit come up very recently actually. But I agree, it's a rare case, and overuse would come with fragility downsides.

[gkreitz]

While fixing this, I added support for non-integer time limits in problemtools (but with warnings). We still do not support non-integer time limits in Kattis, and don't have any plans to do so at the moment. If there is a strong demand for it, I would consider adding it to Kattis too, but as I mentioned, I feel like it's a bit of a footgun. Many languages can have time overheads that measure ~.2-.5s, so having time limits with that resolution gets fragile fast.