[CP] IOI'96 Day 2: Problem 1: Sorting a Three-Valued Sequence

Problem: http://olympiads.win.tue.nl/ioi/ioi96/contest/ioi96s.html


Key idea: Counting sort. Time should be O(N).


Algorithm: Time = O(N).

1. Counting each value 1, 2, 3, i.e., Count[1], Count[2], Count[3].
• Count[1] + Count[2] + Count[3] = N
• Target intervals:
• I_1 = [0, Count[1])
• I_2 = [Count[1], Count[1] + Count[2])
• I_3 = [Count[1] + Count[2], Count[1] + Count[2] + Count[3])
2. Counting each value on 3 different target intervals.
• Define Count[i][j] = # of value i in the interval I_j.
3. Swap i and j in min(Count[i][j], Count[j][i]) times for i ≠ j.
4. Swap the rest unsorted values.
• Let T_ij = abs(Count[i][j] - Count[j][i]).
• Property: T_ij = T_jk = T_ki. 
• Let T = T_ij = T_jk = T_jk.
• Swap 1 -> 2 -> 3 cyclically: Take 2T times. 

Code for Subtask A: https://github.com/Meng-Gen/USACOTraining/blob/master/sort3/main.cc

#include <iostream>
#include <fstream>

using namespace std;

int main() {
    ofstream fout("sort3.out");
    ifstream fin("sort3.in");

    int N;
    fin >> N;

    int values[1000] = {0};
    int value_counts[3] = {0};
    int swapping_map[3][3] = {0};
    for (int i = 0; i < N; i++) {
        fin >> values[i];
        value_counts[values[i] - 1]++;
    }

    int begin_pos = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < value_counts[i]; j++) {
            swapping_map[i][values[begin_pos + j] - 1]++;
        }
        begin_pos += value_counts[i];
    }

    int swapping_count = 0;
    swapping_count += min(swapping_map[0][1], swapping_map[1][0]); // 1 <-> 2
    swapping_count += min(swapping_map[1][2], swapping_map[2][1]); // 2 <-> 3
    swapping_count += min(swapping_map[2][0], swapping_map[0][2]); // 3 <-> 1
    swapping_count += 2 * abs(swapping_map[0][1] - swapping_map[1][0]); // 1 -> 2 -> 3
    fout << swapping_count << '\n';

    return 0;
}