Connection Status:
Competition Arena > MayTheBestPetWin

MayTheBestPetWin

SRM 593 · 2013-06-25 · by tozangezan

SRM 593 · 2013-06-25 · by tozangezan · Brute Force, Dynamic Programming, Simple Math
Class Name: MayTheBestPetWin
Return Type: int
Method Name: calc
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

The pony Rainbow Dash wants to choose her pet. There are N animals who want to be her pet. Rainbow Dash numbered them 0 through N-1.

To help her make the decision, Rainbow Dash decided to organize a relay race for the animals. The race track is already known, and for each animal we know how fast it is. More precisely, you are given int[]s A and B with the following meaning: For each i, the animal number i will take between A[i] and B[i] seconds (inclusive) to complete the track.

For the race the animals will be divided into two competing teams. This is a relay race, so the team members of each team will all run the same track, one after another -- when the first team member finishes, the second one may start, and so on. Thus the total time in which a team completes the race is the sum of the times of all team members. Note that we can use the estimates given by A and B to estimate the total time for any team of animals.

Given two teams S and T, the value maxdiff(S,T) is defined as the largest possible difference in seconds between the time in which team S finishes the course and the time in which team T finishes the course.

Rainbow Dash now needs to assign each of the animals to one of the two competing teams. She wants to see a close competition, so she wants the teams to finish as close to each other as possible. Formally, she wants to divide all animals into teams S and T in a way that minimizes maxdiff(S,T). Return the smallest possible value of maxdiff(S,T).

Notes

  • The teams are not required to contain the same number of animals.

Constraints

  • A will contain between 2 and 50 elements, inclusive.
  • A and B will contain the same number of elements.
  • Each element of A will be between 1 and 10,000, inclusive.
  • Each element of B will be between 1 and 10,000, inclusive.
  • For each i, B[i] will be greater than or equal to A[i].
Examples
0)
{3,4,4,7}
{3,4,4,7}
Returns: 2

In this test case we know the exact time in which each of the animals completes the track. An optimal solution is to choose teams S={0,3} and T={1,2}. Then team S will certainly complete the track in 3+7 = 10 seconds, and team T in 4+4 = 8 seconds. Thus, maxdiff(S,T)=2.

1)
{1,3,5,4,5}
{2,5,6,8,7}
Returns: 5

Here one of the optimal solutions is S={2,3} and T={0,1,4}. For these two teams we have maxdiff(S,T)=5. For example, it is possible that S will complete the track in 6+8 = 14 seconds, and T will complete it in 1+3+5 = 9 seconds. It is also possible that S will complete the track up to 5 seconds before T does.

2)
{4184,4202}
{6933,7208}
Returns: 3024
3)
{1859,4221,568}
{2205,4264,9622}
Returns: 5901
4)
{3614,4326,6021,5881}
{9988,7408,6393,6939}
Returns: 5494

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

Coding Area

Language: C++17 · define a public class MayTheBestPetWin with a public method int calc(vector<int> A, vector<int> B) · 156 test cases · 2 s / 256 MB per case

Submitting as anonymous