-
Asked by: bandaram_Sumanth on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.
QUICK EXPLANATION:
Precalculate Y0
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 c1 to letter c2 having following formulas:
X=|c1−c2|,
Y=Y0−(B[i][c1]+F[i][c1])+(B[i][c2]+F[i][c2])
Whole solution works in O(N⋅Σ)
.
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 Y0 for unchanged string, it will be possible for us to recalculate Y after we change letter at position i from c1 to c2
(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;
source : https://discuss.codechef.com/questions/131400/nsa-editorial
comment if you don't understand this solution