Tool for auto-tuning time limits

[edomora97]

This is the tracking issue for a tool that selects the best time limit to use for a task, such that every solution gets the correct subtasks.

Inputs

• Solutions with the set of subtask on which they should get AC, and on which they should get TLE (possible thanks to RFC: Automatic validation of solution's subtask status #34)
• A maximum possible time limit
• A specification for computing the bounds

Outputs

• An interval in which the solutions get the correct subtasks

---

After running the solutions with the maximum possible time limit, we know the run times of each solution, of each subtask. Solutions that take more than this time limit can be considered to take this time.

For sure, the resulting time limit should be greater or equal to the maximum time of all the solutions that should get AC. Similarly, it should be lower than the maximum time of each subtask that should get TLE.

This can either produce an interval (a solution exists), or no interval (no solution exists). However, it is beneficial to restrict the bounds further. For example, you may want to add the bound that the result is greater or equal to "twice" the maximum time of all the solutions that should get AC (to be more confident that a solution doesn't get spurious TLE). Similarly, you may want to restrict the upper bound in similar way.

---

Open questions

1. How the "strict" bounds should be specified?
   • Simply a factor? (e.g. 2x in the previous example)
   • A factor and a minimum bound? (e.g. 2x the time, at least +0.5s)
2. And the upper bound?
   • Still a factor?
   • A constant? (e.g. at least +0.5s)
3. This tool should produce just an interval or maybe also a proposed time?
   • Maybe it should produce both a "loose" and a "strict" interval
   • Which are the rules for rounding the proposed time?
4. Name of the tool?
   • task-maker-tools auto-tune-time-limit
   • task-maker-tools auto-tune
   • task-maker-tools find-time-limit
   • task-maker-tools 🐟
   • Other proposals?

[wil93]

Just for reference, verifyproblem (from https://github.com/Kattis/problemtools) does something similar to decide the time-limit based on the execution time of solutions in the submissions/accepted and submissions/time_limit_exceeded folders.

Example run where I mistakenly put a slow solution in submissions/accepted, leading verifyproblem to think I wanted a high TL:

root@08adcf9e1727:/kattis_work_dir/2023/kattis/itacpc22f# verifyproblem .
Loading problem itacpc22f
Checking config
Checking statement
Checking validators
WARNING in input format validators: No validator rejects leading zeros added to integers
Checking graders
Checking data
Checking submissions
   AC submission bitset.cpp (C++) OK: AC [CPU: 2.15s @ test case secret/18]
   AC submission solution.cpp (C++) OK: AC [CPU: 2.58s @ test case secret/18]
   AC submission solution_tl.cpp (C++) OK: AC [CPU: 23.04s @ test case secret/18]
   Slowest AC runtime: 23.041, setting timelim to 115 secs, safety margin to 230 secs
   WA submission lame.cpp (C++) OK: WA [test case: test case secret/21, CPU: 5.26s @ test case secret/18]
itacpc22f tested: 0 errors, 1 warning