#include <bits/stdc++.h>
#pragma GCC optimize("trapv")
using namespace std;
typedef int64_t ll;
vector<ll> val[16][16];
vector<int> idx[16];
int prfx[16][100'005];
double dp[1 << 16];
int sum(int g, int l, int r) {
return prfx[g][r + 1] - prfx[g][l];
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(3);
string in;
cin >> in;
int n = in.size();
set<int> chars;
for (auto i : in) {
chars.insert(i);
}
int mp[255]{}, ctr = 0;
for (auto i : chars) {
mp[i] = ctr++;
}
int m = chars.size();
int a[n];
for (int i = 0; i < n; i++) {
a[i] = mp[(int)in[i]];
}
for (int i = 0; i < n; i++) {
idx[a[i]].push_back(i);
for (int j = 0; j < m; j++) {
prfx[j][i + 1] = prfx[j][i];
}
prfx[a[i]][i + 1]++;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
vector<int> cur = idx[j];
val[i][j].resize(cur.size() + 1);
reverse(cur.begin(), cur.end());
val[i][j][0] = 0;
for (auto l : cur) {
val[i][j][0] += sum(i, l, n - 1);
}
for (int k = 1; k <= (int) idx[j].size(); k++) {
val[i][j][k] = val[i][j][k - 1];
val[i][j][k] -= sum(i, cur.back(), n - 1);
val[i][j][k] += sum(i, 0, cur.back());
cur.pop_back();
}
}
}
// for (int i = 0; i < m; i++) {
// for (int j = 0; j < m; j++) {
// for (int k = 0; k <= (int) idx[j].size(); k++) {
// cout << "if we include the first " << k << " in " << j << " passes by " << i << ": " << val[i][j][k] << " times\n";
// }
// }
// }
dp[(1 << m) - 1] = 0;
for (int msk = (1 << m) - 2; msk >= 0; msk--) {
vector<int> bits[2];
for (int i = 0; i < m; i++) {
bits[(msk >> i) & 1].push_back(i);
}
dp[msk] = 1e10;
for (auto i : bits[0]) {
double mn = 1e10;
for (int s = 0; s <= (int) idx[i].size(); s++) {
double cur = 0;
for (auto j : bits[1]) {
cur += val[j][i][s];
}
ll ttl = idx[i].size();
cur += (2ll * s * s - 2ll * s * ttl) / 4.0;
mn = min(mn, cur);
}
mn += (1ll * ttl * ttl - ttl) / 4.0;
dp[msk] = min(dp[msk], mn + dp[msk | (1 << i)]);
}
}
cout << dp[0] << '\n';
/*
for (int j = 0; j <= n; j++) {
ans = min(ans, 1.0 * j * (j - 1) / 4.0 + 1.0 * (n - j) * (n - j - 1) / 4.0);
}
*/
return 0;
}
Compilation message
passes.cpp: In function 'int main()':
passes.cpp:81:26: error: 'ttl' was not declared in this scope
81 | mn += (1ll * ttl * ttl - ttl) / 4.0;
| ^~~
