Problem 3 - Melody

Summary

You're given a sequence of notes (represented by integers), which you'd like to turn into a sequence of three repeating notes by changing as few integers in the sequence as possible.

Solution

Let's colour our sequence yellow, blue, white, yellow, blue, white...

The important thing to notice is that for our song to be nice:

• all the yellow notes will need to be turned into the same note,
• all the blue notes will need to be turned into the same note, and
• all the white notes will need to be turned into the same note.

This useful observation lets us split the problem into three independent parts; what note should we choose for the yellow, blue and white sections?

Let's focus on the blue section. If our goal is to minimize the number of changes we need to make, we should choose whichever note in the blue section occurs the most (the mode), in this case, 3. If two types of notes both occur the same number of times, we can take any of them.

To calculate which note occurs the most, we can just loop through the array, and keep a count of how many of each note we've seen.

Code

import sys

S = [None for x in range(100005)]

input_file = open("melodyin.txt", "r")
output_file = open("melodyout.txt", "w")

input_line = input_file.readline().strip()
N, K = map(int, input_line.split())

for i in range(0, N):
    S[i] = int(input_file.readline().strip())

sections = [[], [], []]

for i in range(0, N):
    sections[i%3].append(S[i])

def calculate_mode(a):
    count = [0 for x in range(K+1)]
    for note in a:
        count[note] += 1
    return max(count)

kept_the_same = 0
kept_the_same += calculate_mode(sections[0])
kept_the_same += calculate_mode(sections[1])
kept_the_same += calculate_mode(sections[2])

answer = N - kept_the_same

output_file.write("%d\n" % (answer))

input_file.close()
output_file.close()