SingingEasy
SRM 653 · 2015-01-29 · by dreamoon
Problem Statement
Alice and Bob are going to sing a song together.
For simplicity, we will assign the numbers 1 through 1,000,000 to the pitches that occur in the song (from the lowest to the highest).
Both Alice and Bob are able to sing all of these pitches.
You are given a
Changing the pitch of one's voice is exhausting. Given a sequence of pitches to sing, the difficulty for the singer can be computed by summing up the differences between consecutive pitches. For example, the difficulty of the sequence 8, 8, 13, 12 is abs(8-8) + abs(13-8) + abs(12-13) = 0+5+1 = 6.
The total difficulty of singing the song can be computed as the difficulty for Alice plus the difficulty for Bob. Return the smallest possible total difficulty of singing the given song.
Constraints
- The number of elements in pitches will be between 1 and 2,000, inclusive.
- all elements in pitch will be between 1 and 1,000,000, inclusive.
{1,3,8,12,13}
Returns: 7
One optimal solution is to let Alice sing the first two notes and Bob the remaining three. Then, Alice will sing the sequence of pitches {1,3} and Bob will sing {8,12,13}. The difficulty for Alice is abs(3-1) = 2. The difficulty for Bob is abs(12-8) + abs(13-12) = 5. Thus, the total difficulty is 2+5 = 7.
{1,5,6,2,1}
Returns: 3
One optimal solution is to let our singers sing in the order Alice-Bob-Bob-Alice-Alice. In this case Alice sings the sequence of pitches {1,2,1} and Bob sings {5,6}. Hence the difficulty for Alice is 2 and the difficulty for Bob is 1.
{5,5,5,5,4,4,4,4}
Returns: 0
{1000000}
Returns: 0
{24,13,2,4,54,23,12,53,12,23,42,13,53,12,24,12,11,24,42,52,12,32,42}
Returns: 188
Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SingingEasy with a public method int solve(vector<int> pitch) · 82 test cases · 2 s / 256 MB per case