#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MXG = 15;
const ll INF = 1e17;
string s;
int n;
vector<ll> A[MXG];
// pref[i][j][k] -> i after j cost from left at k
vector<ll> pref[MXG][MXG];
// suff[i][j][k] -> i after j cost from right at k
vector<ll> suff[MXG][MXG];
ll dp[1 << MXG];
bool visited[1 << MXG];
void init()
{
// pref
for(int i = 0; i < MXG; i++) {
for(int j = 0; j < MXG; j++) {
if(i == j || A[i].empty() || A[j].empty()) continue;
int r = 0;
int cost = 0;
for(int k = 0; k < A[i].size(); k++) {
while(r < A[j].size() && A[j][r] < A[i][k]) {
r++;
}
cost += r;
pref[i][j].push_back(4*cost);
}
}
}
// suff
for(int i = 0; i < MXG; i++) {
for(int j = 0; j < MXG; j++) {
if(i == j || A[i].empty() || A[j].empty()) continue;
int r = A[j].size()-1;
int cost = 0;
for(int k = A[i].size()-1; k >= 0; k--) {
while(r >= 0 && A[j][r] > A[i][k]) {
r--;
}
cost += A[j].size()-1-r;
suff[i][j].insert(suff[i][j].begin(), 4*cost);
}
}
}
}
ll cost(int group, int bitmask, int split)
{
ll sum = 0;
for(int g = 0; g < MXG; g++) {
if(((bitmask >> g) & 1) == 0 || A[g].empty() || g == group) continue;
//cerr << "left: " << (split > -1 ? pref[group][g][split] : 0) << "\n";
sum += split > -1 ? pref[group][g][split] : 0;
//cerr << "right: " << (split+1 < A[group].size() ? suff[group][g][split+1] : 0) << "\n";
sum += split+1 < A[group].size() ? suff[group][g][split+1] : 0;
}
if(split > 0) {
//cerr << "left chance: " << split*(split+1) << "\n";
sum += split*(split+1); // chance to collide between on the left
}
ll cnt = A[group].size() - (split+1);
if(cnt > 1) {
//cerr << "right chance: " << cnt*(cnt-1) << "\n";
sum += cnt*(cnt-1); // chance to collide between on the right
}
return sum;
}
ll recur(int bitmask)
{
if(bitmask == 0) {
return 0;
}
if(visited[bitmask]) {
return dp[bitmask];
}
visited[bitmask] = true;
ll mn = INF;
for(int g = 0; g < MXG; g++) {
if(((bitmask >> g) & 1) == 0) continue;
int bits = bitmask - (1 << g);
ll initial = recur(bits);
if(A[g].empty()) {
mn = min(mn, initial);
continue;
}
int l = -1, r = A[g].size()-1;
while(l < r) {
int mid = l == -1 && r == 0 ? -1 : (l + r) / 2;
ll a = cost(g, bits, mid);
ll b = cost(g, bits, mid+1);
if(a < b) {
r = mid;
}
else {
l = mid+1;
}
}
mn = min(mn, initial + cost(g, bits, l));
}
dp[bitmask] = mn;
return dp[bitmask];
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(0);
//s = string(899, 'A');
cin >> s;
n = s.size();
for(int i = 0; i < n; i++) {
A[s[i]-'A'].push_back(i);
}
init();
cout << fixed << setprecision(6);
cout << recur(0x7fff)/4.0 << "\n";
return 0;
}
/*
AACCAA
HEHEHEHIHILOL
ONMLKJIHGFEDCBAABCDEFGHIJKLMNO
*/
Compilation message
passes.cpp: In function 'void init()':
passes.cpp:28:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int k = 0; k < A[i].size(); k++) {
| ~~^~~~~~~~~~~~~
passes.cpp:29:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | while(r < A[j].size() && A[j][r] < A[i][k]) {
| ~~^~~~~~~~~~~~~
passes.cpp: In function 'll cost(int, int, int)':
passes.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | sum += split+1 < A[group].size() ? suff[group][g][split+1] : 0;
| ~~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
