Statistics

Problem Statement for "TimeLimit"

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 int[] goodTimes and the times for the bad solutions are in the int[] badTimes.

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.

Definition

Class:
TimeLimit
Method:
setTimeLimit
Parameters:
int[], int[]
Returns:
int
Method signature:
int setTimeLimit(int[] goodTimes, int[] badTimes)
(be sure your method is public)

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.

Examples

  1. {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.

  2. {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.

  3. {30, 20, 50, 10, 70, 40, 60}

    {91, 86, 71, 77, 71, 999, 314}

    Returns: 70

  4. {1}

    {1}

    Returns: -1

  5. {1}

    {2}

    Returns: 1

  6. {9999}

    {10000}

    Returns: 9999

  7. {10000}

    {10000}

    Returns: -1

  8. {4700}

    {4699}

    Returns: -1

  9. {1}

    {3}

    Returns: 2

  10. {1}

    {10000}

    Returns: 9999

  11. {3525, 5765}

    {8931, 8979, 9193, 6100, 9962, 7873, 8578, 5765, 9481}

    Returns: -1

  12. {992, 2298, 2936, 137, 1533, 1471, 2106, 3896, 1812}

    {8820, 8466, 3897, 6697, 5502, 8608}

    Returns: 3896

  13. {2765, 452, 3049, 3167, 3581, 1447, 1707, 2477}

    {8132, 3584, 5726, 9915, 5541}

    Returns: 3583

  14. {3637, 2074, 1223, 6224, 4945, 4572, 125, 1396}

    {8797, 9347, 6568, 6229, 9523, 7317, 6534, 8323, 9557}

    Returns: 6228

  15. {1048, 5668, 5669, 1448, 1508, 3849, 1628}

    {5680, 6799}

    Returns: 5679

  16. {2006, 542, 757, 86, 138, 43, 288}

    {8077, 2022, 6213}

    Returns: 2021

  17. {2226, 2870, 1386}

    {2906}

    Returns: 2905

  18. {182, 6206}

    {6277, 7516}

    Returns: 6276

  19. {4476, 8764, 1323}

    {9654, 9187, 9677, 8953, 9808, 9799, 9059, 9954, 9573, 9959}

    Returns: 8952

  20. {3790, 2713, 6523, 8032, 2886, 6185, 2009, 1368, 935}

    {8435}

    Returns: 8434

  21. {670, 556, 393, 495, 71}

    {1475, 9295}

    Returns: 1474

  22. {1499, 1050}

    {7357, 6260, 5667, 9792, 2942}

    Returns: 2941

  23. {824, 5731, 9550, 926, 6421, 4390}

    {3451, 4747, 3428, 7619, 4908}

    Returns: -1

  24. {7217, 5202, 898, 2545, 9508, 7860, 11, 451}

    {7495, 8524, 7175, 4223, 4817, 1680, 4966}

    Returns: -1

  25. {2782, 6932}

    {8152, 6980, 3843, 8247, 9344, 8409}

    Returns: -1

  26. {5129, 9090, 378, 9977, 6215}

    {9656, 9746, 7567, 9148, 2941, 6178, 702, 2976, 2974, 1277}

    Returns: -1

  27. {6735, 988, 3677, 7565, 2883, 9797, 6520, 74}

    {2279, 1193, 9179, 6376, 13, 6298, 8181, 7457, 6115, 2007}

    Returns: -1

  28. {6562, 1673, 1410, 6887, 6750, 9020, 1709, 2865, 8169}

    {7197, 9771, 1536, 6480, 8594, 8285, 5365, 7088}

    Returns: -1

  29. {5184, 6507, 1223, 2172}

    {5457, 1718, 4137, 7954, 1519, 5852, 488, 6465}

    Returns: -1

  30. {1333, 9856, 3674, 8451, 3454, 8320, 4222, 5023, 8194, 9922}

    {9211, 1024}

    Returns: -1

  31. {2905, 8000, 3954, 6626, 7768}

    {9652}

    Returns: 9651

  32. {9979, 3855, 9083, 6130, 1749, 5536, 1054}

    {9665, 1735, 3916}

    Returns: -1

  33. {1311, 2322, 8438}

    {2711, 1266, 1519}

    Returns: -1

  34. {9652, 6452, 5707}

    {6794, 4832}

    Returns: -1

  35. {3598, 5684, 1477, 5148, 1670, 587, 3307, 9161, 2220}

    {1490, 5232, 7029, 8294, 8946, 9382}

    Returns: -1

  36. {8542, 8512, 6972, 7195, 7145, 6769}

    {372, 3192, 5349, 804, 9825, 7021, 1657, 7195}

    Returns: -1

  37. {2033, 1578, 5484, 7163, 967, 5468, 3072, 6698, 7681, 8487}

    {8462, 1959, 3760, 3254, 433, 8847, 8087, 5329}

    Returns: -1

  38. {2685, 4737, 1190}

    {9907}

    Returns: 9906

  39. {725, 104, 4198, 5648, 3150}

    {3524, 6052, 6074, 2190, 3317, 7331, 566, 4942, 9874}

    Returns: -1

  40. {6911, 1816, 6925, 6854, 5694}

    {4208, 744, 9257, 8042, 3764, 4434, 6645, 959}

    Returns: -1

  41. {6441}

    {6838, 6011, 8523, 1454}

    Returns: -1

  42. {5555, 7229, 1111, 1073, 7753, 4372}

    {2659, 3355}

    Returns: -1

  43. {1 }

    {1 }

    Returns: -1

  44. {1200, 1450 }

    {1900, 2100, 9875 }

    Returns: 1899

  45. {10 }

    {10 }

    Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: