Connection Status:
Competition Arena > Singing

Singing

SRM 653 · 2015-01-29 · by Chmel_Tolstiy

SRM 653 · 2015-01-29 · by Chmel_Tolstiy · Graph Theory
Class Name: Singing
Return Type: int
Method Name: solve
Arg Types: (int, int, int, vector<int>)
Problem Statement

Problem Statement

Alice and Bob are going to sing a song together. You are given three ints: N, low, and high. For simplicity, we will assign the numbers 1 through N to the pitches that occur in the song (from the lowest to the highest). Alice is only able to sing pitches between low and N, inclusive. Bob is only able to sing pitches between 1 and high, inclusive. (It is guaranteed that the ranges of their voices overlap.)

You are also given a int[] pitch containing the pitches of all notes in the song, in order.

Each note of the song must be sung by exactly one person: either Alice or Bob. Each person can only sing notes that are within their range. All notes with the same pitch must be sung by the same person. The number of times the singer changes during the song must be as small as possible.

Formally, a switch is a pair of consecutive notes that are sung by different persons. Compute and return the smallest possible number of switches when Alice and Bob sing the song.

Notes

  • A singer is not required to sing a consecutive sequence of pitches. For example, sometimes Bob may sing pitches 1 and 3 while Alice sings pitches 2 and 4.

Constraints

  • N will be between 1 and 1,000, inclusive.
  • low will be between 1 and N, inclusive.
  • high will be between low and N, inclusive.
  • The number of elements in pitch will be between 1 and 1,000, inclusive.
  • All elements of pitch will be between 1 and N.
Examples
0)
3
2
2
{1,2,3,2,1,2}
Returns: 2

There are 3 pitches. Alice is able to sing pitches 2 and 3, while Bob is able to sing pitches 1 and 2. Thus, there are only two different ways in which they can sing the notes of the given song: Either they will sing in the order Bob-Alice-Alice-Alice-Bob-Alice (3 switches), or in the order Bob-Bob-Alice-Bob-Bob-Bob (only 2 switches). The second way of singing the song is better.

1)
10
3
7
{4,4,5,5,6,5,3,6}
Returns: 0

Alice can sing the entire song. In that case there are no switches.

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

In the optimal solution Bob sings the first three notes (pitches 5, 3, and 1), and Alice sings the next three notes.

3)
10
4
5
{1,4,3,5,2,5,7,5,9}
Returns: 3
4)
100
20
80
{2,27,3,53,53,52,52,60,85,89,100,53,60,2,3,53,100,89,40,42,2,53,2,85}
Returns: 5

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 Singing with a public method int solve(int N, int low, int high, vector<int> pitch) · 117 test cases · 2 s / 256 MB per case

Submitting as anonymous