AIO 2021 Q3: Melody - Late Night Code

Contest Source: AIO 2021

There are three ‘categories’ of notes: the first note in each triple, the second node in each triple, and the third note in each triple. The first observation is noticing that we can handle each of these three categories separately, since the notes in any one category do not affect how you have to pick any of the other categories at all.

Now for a given category, we obviously want to change all of them to the most frequent note in that category, in order to make the least number of changes. We can use modulo to figure out what category a number is in. The overall complexity of this solution is \(O(N)\).

#include <bits/stdc++.h>
using namespace std;

int main () {
    freopen("melodyin.txt", "r", stdin);
    freopen("melodyout.txt", "w", stdout);

    int N, K;
    cin >> N >> K;

    int cnt[3][100005] = {0}; // cnt[i][j] = the number of note j's in category i.
    for (int i = 0; i < N; i++) {
        int note;
        cin >> note;
        cnt[i%3][note]++;
    }

    // find the maximum occurence of a note in each category
    int best[3] = {0};
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < K+5; j++) {
            best[i] = max(best[i], cnt[i][j]);
        }
    }

    // we now just add up the cost of converting every other note to that note
    int ans = ((N/3)-best[0]) + ((N/3)-best[1]) + ((N/3)-best[2]);
    printf("%d\n", ans);
}