TopCoder problem "ChuckContest" used in TCO09 Round 4 (Division I Level Two)



Problem Statement

    

After having beaten Michael Schumacher in F1 and Garry Kasparov in chess, Chuck Norris has decided to beat Petr in an ACM contest.

An ACM contest is a problem solving contest where each participant is given the same set of numProblems problems. A participant's score consists of two components: the number of problems he has solved so far, and the penalty time he has accumulated. Initially, both of those values are zero. At any time, a participant may submit a solution to a problem. This solution is tested against all the test cases prepared by the contest jury. If it doesn't pass all the test cases, the submission is considered wrong, and the participant's score does not change. If it passes all the test cases, then it is considered solved - the number of problems solved by the participant increases by 1 and his penalty increases by T + 20 * R, where T is the time of the correct submission (rounded up to the nearest minute) and R is the number of wrong submissions by that participant for that problem. After a participant solves a problem successfully, he is not allowed to submit any more solutions for that problem.

Participants are ranked as follows. If participant A has solved N1 problems and his penalty is P1, and participant B has solved N2 problems and his penalty is P2, then participant A's score is considered strictly better than participant B's score (i.e., A is ranked higher than B) if N1 > N2 or (N1 = N2 and P1 < P2).

For any problem, Chuck is able to produce a successful solution immediately. However, he doesn't want to solve all the problems immediately because it will reveal his superhuman abilities. Fortunately, he is also able to purposefully produce a failing solution to any problem immediately. Therefore Chuck has decided to divide the whole contest into n parts. These parts are described by the int[] partTimes containing exactly n elements. The first part consists of minutes 1 through partTimes[0], inclusive, the second part consists of minutes partTimes[0]+1 through partTimes[1], inclusive, and so on. The n-th part consists of minutes partTimes[n-2]+1 through partTimes[n-1], inclusive, and the whole contest lasts exactly partTimes[n-1] minutes. He can submit any number of solutions during each part of the contest, and he can even submit multiple solutions within the same minute. He has given himself a set of restrictions that he must follow. These restrictions are given in the String[]s lowerBounds and upperBounds, each of which contains exactly n elements, where each element is formatted "problems_solved penalty" (quotes for clarity), where both problems_solved and penalty are integers without extra leading zeros. Chuck wants his score immediately after the i-th part (0-based) to be strictly better than the score described in lowerBounds[i] and strictly worse than the result described in upperBounds[i].

Of course, Chuck wants his score at the end of the contest to be as good as possible while adhering to the given constraints. Return this best possible score as a String formatted "problems_solved penalty" (quotes for clarity), where problems_solved and penalty contain no extra leading zeroes. If it's not possible to follow all the given constraints, return an empty String instead.

 

Definition

    
Class:ChuckContest
Method:chuckRules
Parameters:int, String[], String[], int[]
Returns:String
Method signature:String chuckRules(int numProblems, String[] lowerBounds, String[] upperBounds, int[] partTimes)
(be sure your method is public)
    
 

Constraints

-numProblems will be between 1 and 60, inclusive.
-lowerBounds will contain between 1 and 50 elements, inclusive.
-lowerBounds, upperBounds and partTimes will contain the same number of elements.
-Each element of partTimes will be between 1 and 1500, inclusive.
-The elements of partTimes will be distinct and sorted in ascending order.
-Each element of lowerBounds and upperBounds will be formated "problems_solved penalty" (quotes for clarity), where problems_solved and penalty are integers with no extra leading zeros.
-In each element of lowerBounds and upperBounds, problems_solved will be between 1 and numProblems, inclusive, and penalty will be between problems_solved and 100000, inclusive.
 

Examples

0)
    
10
{"1 31"}
{"1 10"}
{1}
Returns: "1 21"
This contest lasts just 1 minute and consists of only one part. Chuck could solve all the problems correctly on his first attempt during the first minute, but according to lowerBounds and upperBounds, he must solve exactly one problem with penalty time between 11 and 30, inclusive. So the best possibility for him is to submit an incorrect solution and then submit a correct solution on the same problem. This will result in score "1 21".
1)
    
10
{"10 31"}
{"10 10"}
{1}
Returns: "10 30"
The same case as example 0, but now Chuck must solve 10 problems. The only possibility for him is to make an incorrect attempt (on any problem) and then solve 10 problems in a row. This will result in score "10 30".
2)
    
10
{"10 30"}
{"10 10"}
{1}
Returns: ""
Now the only possibliity from example 1 is no longer available because of the changed lower bound.
3)
    
60
{"60 60"}
{"1 100000"}
{1500}
Returns: ""
According to lowerBounds[0], Chuck must solve at least 60 problems, and according to upperBounds[0], he must solve no more than 1 problem. Obviously, it's not possible to satisfy both these constraints simultaneously.
4)
    
10
{"1 21", "1 23"}
{"1 19", "1 21"}
{20, 60}
Returns: ""
After the first part, Chuck must have 1 problem solved with penalty time 20. After the second part, he must still have 1 problem solved, but with penalty time 22. As he can't solve more problems in the second part, there's no possibility for him to change his penalty time.
5)
    
10
{"1 3", "1 100000"}
{"1 1", "10 10"}
{30, 31}
Returns: "10 281"
Chuck must submit one correct solution in the second minute and 9 correct solutions in the 31st minute.
6)
    
17
{"4 982", "5 182", "14 103"}
{"14 14", "9 703", "17 440"}
{6, 10, 16}
Returns: "17 441"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10370

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13762&pm=10370

Writer:

DStepanenko

Testers:

PabloGilberto , legakis , ivan_metelsky

Problem categories:

Dynamic Programming