TimeLimit
TCO20 South America · 2020-07-18 · by misof
Problem Statement
You are preparing a problem for a programming contest. You have already prepared all test cases and written multiple correct solutions. Some of those correct solutions are labeled as good (i.e., they should be accepted) and some are labeled as bad (i.e., they should be rejected for exceeding the time limit).
You have executed all the solutions you have on all the prepared tests.
For each solution you recorded its maximum running time.
The times for good solutions are given in the
You now want to set the time limit for this problem. The time limit must have the following properties:
- Each good solution must pass. (A solution passes if its running time for each test case is less than or equal to the time limit.)
- Each bad solution must fail.
- The time limit must be an integer.
- The time limit must be as large as possible.
Return the time limit you should set, or -1 if it is not possible to set a valid time limit that has the properties listed above.
Notes
- All times in this problem (both the inputs and the return value) are in milliseconds.
Constraints
- goodTimes will contain between 1 and 10 elements, inclusive.
- badTimes will contain between 1 and 10 elements, inclusive.
- Each element of goodTimes will be between 1 and 10,000, inclusive.
- Each element of badTimes will be between 1 and 10,000, inclusive.
{1200, 1450}
{1900, 2100, 9875}
Returns: 1899
We have two good solutions and three bad ones. One of the good solutions needs 1200 ms in the worst case, the other needs 1450 ms.
{1000, 3000}
{5000, 2000, 4000, 2976}
Returns: -1
It is not possible to set a valid time limit: it must be at least 3000 for each good solution to pass, but then at least two bad solutions pass as well.
{30, 20, 50, 10, 70, 40, 60}
{91, 86, 71, 77, 71, 999, 314}
Returns: 70
{1}
{1}
Returns: -1
{1}
{2}
Returns: 1
Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TimeLimit with a public method int setTimeLimit(vector<int> goodTimes, vector<int> badTimes) · 45 test cases · 2 s / 256 MB per case