PROBLEM LINK:
Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov
DIFFICULTY:
EASY
PREREQUISITES:
Basic dynamic programming
PROBLEM:
You are given string S of length N consisting of lowercase English letters. You may change one letter of this string to any other lowercase English letter with the cost of absolute difference between their ASCII codes. Let this cost be X.
Consider number of pairs 1\leq i < j \leq N such that S_i < S_j in resulting string. Let this number be Y.
You are to calculate minimum value of X+Y possible.
QUICK EXPLANATION:
Precalculate Y_0 for unchanged string and arrays B[i][c] and F[i][c] holding number of letters less than c before position i and number of letters larger than c after position i correspondingly. After that you can try each single switch on position i from letter c_1 to letter c_2 having following formulas:
Whole solution works in O(N \cdot \Sigma).
EXPLANATION:
Your solution has to be subquadratic to get 100 points. Thus it would be okay if you try to change every single letter and calculate new value of Y. What is the impact single letter c in position i makes for the whole Y? It’s number of letters less than c before i plus number of letters larger than c after i. If we calculate those values in advance for all possible i and c alongside with some initial Y_0 for unchanged string, it will be possible for us to recalculate Y after we change letter at position i from c_1 to c_2 (see formulas from quick explanation). We can calculate values as follows:
string S;
cin >> S;
for(auto &it: S) {
it -= 'a';
}
int N = S.size();
int Sigma = 26;
int B[N][Sigma], F[N][Sigma];
memset(B, 0, sizeof(B));
memset(F, 0, sizeof(F));
int64_t Y0 = 0;
for(int i = 1; i < N; i++) {
int B_idx = i, F_idx = N - i - 1; // we run B_idx from 1 to N-1 and F_idx from N-2 to 0.
for(int c = 0; c < Sigma; c++) {
B[B_idx][c] = B[B_idx - 1][c] + (S[B_idx - 1] < c);
F[F_idx][c] = F[F_idx + 1][c] + (S[F_idx + 1] > c);
}
Y0 += B[B_idx][S[B_idx]];
}
Now we can try every possible switch and choose the best option:
int64_t ans = Y0;
for(int i = 0; i < N; i++) {
for(int c = 0; c < Sigma; c++) {
int X = abs(S[i] - c);
int64_t Y = Y0 - (B[i][S[i]] + F[i][S[i]]) + (B[i][c] + F[i][c]);
ans = min(ans, X + Y);
}
}
cout << ans << endl;
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
