#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()
{
// For some reason I have to comment this:
// ============================
// cin.tie(0);
// ios::sync_with_stdio(0);
// ============================
//s = string(899, 'A');
getline(cin, s);
n = s.size();
for(int i = 0; i < n; i++) {
A[s[i]-'A'].push_back(i);
}
init();
// the hell is this grader?
ll ans = recur(0x7fff);
cout << ans / 4;
if(ans % 4 == 1) {
cout << ".25";
}
else if(ans % 4 == 2) {
cout << ".5";
}
else if(ans % 4 == 3) {
cout << ".75";
}
return 0;
}
/*
AACCAA
HEHEHEHIHILOL
ONMLKJIHGFEDCBAABCDEFGHIJKLMNO
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
*/
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 |
Correct |
12 ms |
596 KB |
Output is correct |
2 |
Correct |
6 ms |
600 KB |
Output is correct |
3 |
Correct |
5 ms |
596 KB |
Output is correct |
4 |
Correct |
7 ms |
572 KB |
Output is correct |
5 |
Correct |
10 ms |
616 KB |
Output is correct |
6 |
Correct |
16 ms |
1520 KB |
Output is correct |
7 |
Incorrect |
17 ms |
1540 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
596 KB |
Output is correct |
2 |
Correct |
8 ms |
596 KB |
Output is correct |
3 |
Correct |
33 ms |
596 KB |
Output is correct |
4 |
Correct |
34 ms |
608 KB |
Output is correct |
5 |
Correct |
20 ms |
612 KB |
Output is correct |
6 |
Correct |
18 ms |
604 KB |
Output is correct |
7 |
Correct |
31 ms |
596 KB |
Output is correct |
8 |
Correct |
23 ms |
596 KB |
Output is correct |
9 |
Correct |
27 ms |
596 KB |
Output is correct |
10 |
Correct |
24 ms |
596 KB |
Output is correct |
11 |
Correct |
24 ms |
604 KB |
Output is correct |
12 |
Correct |
24 ms |
604 KB |
Output is correct |
13 |
Correct |
25 ms |
596 KB |
Output is correct |
14 |
Correct |
26 ms |
600 KB |
Output is correct |
15 |
Correct |
24 ms |
596 KB |
Output is correct |
16 |
Correct |
25 ms |
600 KB |
Output is correct |
17 |
Correct |
27 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
596 KB |
Output is correct |
2 |
Correct |
8 ms |
596 KB |
Output is correct |
3 |
Correct |
33 ms |
596 KB |
Output is correct |
4 |
Correct |
34 ms |
608 KB |
Output is correct |
5 |
Correct |
20 ms |
612 KB |
Output is correct |
6 |
Correct |
18 ms |
604 KB |
Output is correct |
7 |
Correct |
31 ms |
596 KB |
Output is correct |
8 |
Correct |
23 ms |
596 KB |
Output is correct |
9 |
Correct |
27 ms |
596 KB |
Output is correct |
10 |
Correct |
24 ms |
596 KB |
Output is correct |
11 |
Correct |
24 ms |
604 KB |
Output is correct |
12 |
Correct |
24 ms |
604 KB |
Output is correct |
13 |
Correct |
25 ms |
596 KB |
Output is correct |
14 |
Correct |
26 ms |
600 KB |
Output is correct |
15 |
Correct |
24 ms |
596 KB |
Output is correct |
16 |
Correct |
25 ms |
600 KB |
Output is correct |
17 |
Correct |
27 ms |
596 KB |
Output is correct |
18 |
Correct |
8 ms |
596 KB |
Output is correct |
19 |
Correct |
12 ms |
596 KB |
Output is correct |
20 |
Correct |
36 ms |
600 KB |
Output is correct |
21 |
Correct |
37 ms |
596 KB |
Output is correct |
22 |
Correct |
21 ms |
572 KB |
Output is correct |
23 |
Correct |
22 ms |
608 KB |
Output is correct |
24 |
Correct |
28 ms |
596 KB |
Output is correct |
25 |
Correct |
23 ms |
600 KB |
Output is correct |
26 |
Correct |
26 ms |
596 KB |
Output is correct |
27 |
Correct |
23 ms |
600 KB |
Output is correct |
28 |
Correct |
24 ms |
600 KB |
Output is correct |
29 |
Correct |
24 ms |
596 KB |
Output is correct |
30 |
Correct |
26 ms |
600 KB |
Output is correct |
31 |
Correct |
27 ms |
608 KB |
Output is correct |
32 |
Correct |
25 ms |
596 KB |
Output is correct |
33 |
Correct |
25 ms |
600 KB |
Output is correct |
34 |
Correct |
25 ms |
604 KB |
Output is correct |
35 |
Correct |
12 ms |
756 KB |
Output is correct |
36 |
Correct |
13 ms |
836 KB |
Output is correct |
37 |
Correct |
98 ms |
2388 KB |
Output is correct |
38 |
Correct |
119 ms |
2136 KB |
Output is correct |
39 |
Correct |
145 ms |
2260 KB |
Output is correct |
40 |
Correct |
100 ms |
2148 KB |
Output is correct |
41 |
Correct |
97 ms |
2516 KB |
Output is correct |
42 |
Correct |
120 ms |
2580 KB |
Output is correct |
43 |
Correct |
104 ms |
2452 KB |
Output is correct |
44 |
Correct |
96 ms |
2552 KB |
Output is correct |
45 |
Correct |
104 ms |
2556 KB |
Output is correct |
46 |
Correct |
119 ms |
2596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
596 KB |
Output is correct |
2 |
Correct |
6 ms |
600 KB |
Output is correct |
3 |
Correct |
5 ms |
596 KB |
Output is correct |
4 |
Correct |
7 ms |
572 KB |
Output is correct |
5 |
Correct |
10 ms |
616 KB |
Output is correct |
6 |
Correct |
16 ms |
1520 KB |
Output is correct |
7 |
Incorrect |
17 ms |
1540 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |