8. Ešte nás vidíš? vzorové riešenie

#!/usr/bin/python3

def constr_graph(k, s):
    m = len(s) // k
    E = [[len(s) for _ in range(k)] for _ in range(k)]
    se = [[len(s) for _ in range(k)] for _ in range(k)]
    
    for i in range(k):
        for j in range(k):
            if i == j:
                continue;
            E[i][j] = 0
            se[i][j] = 0
            for l in range(m):
                if s[l * k + i] != s[l * k + j]:
                    E[i][j] += 1
                if l > 0 and s[l * k + i] != s[(l - 1) * k + j]:
                    se[i][j] += 1
    return (E, se)

def solve(k, s):
    E, se = constr_graph(k, s)
    
    # print(E, se)
    
    dp = [[[len(s) for _ in range(2)] for _ in range(k)] for _ in range(1 << k)]
    
    dp[1][0][0] = 0
    
    for a in range(1 << k):
        for v in range(k):
            if ((1 << v) & a) == 0 or (a % 2 == 0):
                continue
            # print(a, v, dp[a][v])
            for w in range(k):
                if ((1 << w) & a) == 0:
                    # print(w)
                    dp[a | (1 << w)][w][0] = min(dp[a | (1 << w)][w][0], dp[a][v][0] + E[v][w])
                    dp[a | (1 << w)][w][1] = min(dp[a | (1 << w)][w][1], dp[a][v][1] + E[v][w], dp[a][v][0] + se[w][v])
    res = len(s)
    en = (1 << k) - 1

    for v in range(k):
        res = min(res, dp[en][v][1] + E[v][0], dp[en][v][0] + se[0][v])
    print(res)
    
k = int(input())

solve(k, input())
                

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)  for(int i=0;i<(int)n;i++)

typedef complex<long double> point;

template<class T>
T get() {
    T a;
    cin >> a;
    return a;
}

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {
    out << "[" << par.first << ";" << par.second << "]";
    return out;
}

template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    out << "}";
    return out;
}

template <class T, class U>
ostream& operator<<(ostream& out, const map<T,U> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    out << "}"; return out;
}

template <class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    FOR(i, v.size()){
        if(i) out << " ";
        out << v[i];
    }
    out << endl;
    return out;
}

bool ccw(point p, point a, point b) {
    if((conj(a - p) * (b - p)).imag() <= 0) return false;
    else return true;
}

pair<vector<vector<int> >, vector<vector<int> > > construct_graph(int k, string &s) {
    vector<vector<int> > E(k, vector<int>(k, 0)), start(k, vector<int>(k, 0));
    int m = s.size() / k;
    FOR (i, k) {
        E[i][i] = s.size();
        start[i][i] = s.size();
        FOR (j, k) {
            if (i == j) continue;
            FOR (l, m) {
                if (s[l * k + i] != s[l * k + j]) E[i][j] ++;
                if (l && s[l * k + i] != s[(l - 1) * k + j]) {
                    start[i][j] ++; 
                } 
            }
        }
    }
    return {E, start};
}

void solve() {
    int k = get<int>();
    string s = get<string>();
    int n = s.size();
    
    auto blah = construct_graph(k, s);
    auto E = blah.first, start = blah.second;
    
    int res = n;
    
    vector<vector<vector<int> > > dp(k, vector<vector<int> >(1 << k, vector<int>(2, n)));
    
    dp[0][1][0] = 0;
    for (int a = 1; a < (1 << k); a ++) {
        FOR(j, k) {
            FOR (b, 2) {
                FOR(l, k) {
                    if (a & (1 << l)) continue;
                    dp[l][a | (1 << l)][b] = min(dp[l][a | (1 << l)][b], dp[j][a][b] + E[j][l]);
                    if (!b) dp[l][a | (1 << l)][1] = min(dp[l][a | (1 << l)][1], dp[j][a][b] + start[l][j]);
                }
            }
        }
    }
    FOR(j, k) {
        res = min(res, dp[j][(1 << k) - 1][0] + start[0][j]);
        res = min(res, dp[j][(1 << k) - 1][1] + E[j][0]);
    }
    cout << res << endl;
    
    
}

int main() {
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    solve();
}