Author: Abu Sufian Rafi
Problem tag: DP
Editorial:
In this problem, the target string has 9 characters, so we don’t need to consider the entire input string. In fact, we only need a maximum of 9 × 9 = 81 characters. For every target character, we pick the 9 characters from the input that have the minimum cyclic shift cost to that target character. Then, we form a new candidate string using these selected characters. Finally, we apply bitmask dynamic programming on this reduced string to assign characters optimally to the target positions, achieving the minimum transformation cost.

Code:

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

int Cost(char ch1, char ch2) {
    return min({abs(ch1 - ch2), ('Z' - ch1) + 1 + (ch2 - 'A'), (ch1 - 'A') + 1 + ('Z' - ch2)});
}

void solve() {
    string s1, s2 = "", target = "SERIOUSOJ";
    cin >> s1;
    int n = s1.size(), m = target.size();
    vector<bool> vis(n);
    for(int j = 0; j < m; j++) {
        priority_queue<pair<int, int>> pq;
        for(int i = 0; i < n; i++) {
            pq.push({Cost(s1[i], target[j]), i});
            if(pq.size() > 9) pq.pop();
        }
        while(pq.size()) {
            if(vis[pq.top().second] == 0) {
                vis[pq.top().second] = 1;
                s2 += s1[pq.top().second];
            }
            pq.pop();
        }
    }

    vector<vector<int>> dp(512, vector<int> (s2.size(), -1));
    auto rec = [&](auto&& self, int i, bitset<9> &mask) -> int {
        if(mask.count() == 9) return 0;
        if(i >= s2.size()) return 1e9;
        auto& ans = dp[mask.to_ullong()][i];
        if(ans != -1) return ans;
        ans = self(self, i + 1, mask); // not take
        for(int j = 0; j < 9; j++) {
            if(mask[j]) continue;
            mask[j] = 1;
            ans = min(ans, Cost(s2[i], target[j]) + self(self, i + 1, mask));
            mask[j] = 0;
        }
        return ans;
    };
    bitset<9> mask = 0;
    cout << rec(rec, 0, mask) << '\n';
    return;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc = 1;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case " << t << ": ";
        solve();
    }
    return 0;
}