Connection Status:
Competition Arena > RatingProgressAward

RatingProgressAward

2017 TCO Semi 2 · 2017-03-31 · by cgy4ever

2017 TCO Semi 2 · 2017-03-31 · by cgy4ever · Graph Theory
Class Name: RatingProgressAward
Return Type: int
Method Name: maximalProgress
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Fox Ciel is in college. She still needs to take n courses before she can graduate. Those courses are numbered 0 through n-1.

There may be some dependencies between the courses. For each valid i, Ciel must take course a[i] before taking course b[i]. The courses are numbered in such a way that for each valid i we have a[i] < b[i]. Note that this means that Ciel can always finish all her courses: for example, she may take them in the order 0, 1, ..., n-1.

Most colleges use GPA (grade point average) to grade their students, but Ciel's college is different. They use a rating system similar to the one used at TopCoder. Ciel's initial rating is 1200. For each course, Ciel has estimated how well she will perform in the course and how this will influence her rating. Thus, we know that for each i, taking course i will increase Ciel's rating by change[i]. Note that this amount remains the same regardless of when Ciel takes the course. Also note that for some courses the value change[i] may be negative. For example, change[7] = -200 means that taking course 7 will reduce Ciel's rating by 200.

The college is going to give a Rating Progress Award to one of the students. This award is given to the student who had the largest rating progress during their studies. The rating progress of a student is defined as follows: Let r[0], r[1], ..., r[n] be the sequence of the student's ratings. (Here, r[i] is the rating the student had after finishing i courses.) The student's rating progress is the value max { r[i] - r[j] | 0 <= j <= i <= n}.

Ciel wants to win the Rating Progress Award. You are given the int[] change with n elements and the int[]s a and b that describe the dependencies between the courses. Compute and return the largest possible rating progress Ciel can have if she chooses the optimal order in which to take her n courses. Remember that she needs to choose an order that satisfies all the given dependencies.

Constraints

  • n will be between 1 and 50, inclusive.
  • change will contain exactly n elements.
  • Each element in change will be between -1,000 and 1,000, inclusive.
  • a will contain between 0 and 1,000 elements, inclusive.
  • a and b will contain the same number of elements.
  • For each i, 0 <= a[i] < b[i] < n.
Examples
0)
{1,-1,10,-10,100,-100}
{}
{}
Returns: 111

There are no dependencies - Ciel can take the courses in any order she likes. The optimal solution is to take all courses with a positive rating change consecutively. For example, suppose she takes the courses in the order { 0, 2, 4, 1, 3, 5 }. The sequence of her ratings will be {1200, 1201, 1211, 1311, 1310, 1300, 1200}. Thus, her rating progress will be 1311 - 1200 = 111.

1)
{1,-1,10,-10,100,-100}
{0,1,2,3,4}
{1,2,3,4,5}
Returns: 100

This time the given dependencies mean that Ciel has no choice: she must take the courses in increasing order. When she does so, the sequence of her ratings will be {1200, 1201, 1200, 1210, 1200, 1300, 1200}. Thus, in this case her rating progress is only 1300 - 1200 = 100.

2)
{8,-10,5,1,-3,6,-7,2,-1,-4,0,-2}
{0,1,2,4,5,6,8,9,10}
{1,2,3,5,6,7,9,10,11}
Returns: 14
3)
{8,-10,5,1,-3,6,-7,2,-1,-4,0,-2}
{0,1,2,4,5,6,8,9,10,1}
{1,2,3,5,6,7,9,10,11,5}
Returns: 12
4)
{1000,-1000,1000}
{0,0,0,1,1,1}
{1,1,1,2,2,2}
Returns: 1000

Submissions are judged against all 117 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RatingProgressAward with a public method int maximalProgress(vector<int> change, vector<int> a, vector<int> b) · 117 test cases · 2 s / 256 MB per case

Submitting as anonymous