NSA - Editorial

Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov

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:

X = |c_1-c_2|,
Y = Y_0 - (B[i][c_1]+F[i][c_1]) + (B[i][c_2]+F[i][c_2])

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.

1 Like

#include<bits/stdc++.h>
#include

#define ull long long int
#define in(x) scanf("%llu",&x)

using namespace std;

ull t,n,h,i,j,k,l,m,x,y,z,flag,a[100005],b[100005],c[100005],low,mid,high,sumf,sumb,cnt,ans,maxx,ansc;
string s;

int main()
{
in(t);
while(tâ€“)
{
cin>>s;
n=s.size();

    for(i=0; i<=26; i++)
{
b[i]=0;
c[i]=0;
}
for(i=0; i<n; i++)
{
a[i]=(int)s[i]-96;
b[a[i]]++;
}

ans=0;
cnt=0;
maxx=0;

for(i=0; i<n; i++)
{
sumf=0;
sumb=0;

for(j=1; j<=26; j++)
{
sumf+=b[j];
cnt=a[i]-j+sumf;

if(cnt>maxx)
{
maxx=cnt;
//cout<<a[i]<<" "<<i<<" "<<j<<endl;
}
}

for(j=a[i]-1; j>=1; j--)
{
sumb+=c[j];
cnt=j-a[i]+sumb;

if(cnt>maxx)
{
maxx=cnt;
//cout<<a[i]<<" "<<i<<" "<<j<<endl;
}
}

b[a[i]]--;
c[a[i]]++;
ans=ans+sumf;
}

cout<<ans-maxx<<endl;
}
return 0;


}
//can anyone tell why my answer is giving WA ???

2 Likes

If string is abcb
Then B[i][s[i]] = {0,1,2,2}
But it should {0,1,2,1}
because smaller characters before
Last index is 1.

Hi! It indeed is {0, 1, 2, 1}. And code from editorial gives you the same result.

1 Like

Since Y is basically a *slight modification of counting inversions in an array, just wondering, is there a divide and conquer approach to solving this problem?

The best I could come up with was O(N^2logN)

What you are missing is, when you change the character, you only consider impact on one size, you do not consider the impact on the other side. My solution is similar to yours. In case of doubt check https://www.codechef.com/viewsolution/19137734

If testers and authors are not competing why donâ€™t they write more readable code?

3 Likes

My solution is very much similar to the editorial, yet Iâ€™m getting WA. Can someone please check where am I going wrong

https://www.codechef.com/viewsolution/19265284

Y0 += B[B_idx][S[B_idx]];

Why donâ€™t we add values from the F[][] array here as well? Also, wonâ€™t this recount pairs as F[i] is the number of letters less than c before i?

The editorials by @vijju123 hosted contests are much better and explanatory. Can someone help me understand this approach ?

2 Likes

And also we get editorials on time

1 Like

Unluckily editorialist gave all editorials of questions I already solvedâ€¦ And editorials for questions I donâ€™t know are not out yet !!!
Contest Lasts for 10 days and editorialist gets solutions from starting of contestâ€¦ they why this much delay ? If you donâ€™t have time then why to apply as editorialist ???
@mgch
@vijju123

2 Likes

Hi! My apologies for this inconvenience. The reason why editorials are delayed is that I had relocation due to internship and it definitely didnâ€™t go as well, as I expected month ago when I applied to be an editorialist. I even had to live in a hotel for a while, because securing long-term accomodation here is a huge pain. Now when these things are settled, I do my best to prepare editorials as soon as possible. Please, be patient.

If editorials are unclear, please feel free to point me on particular parts which are difficult to understand and Iâ€™ll try to explain it in simpler manner.

2 Likes

Can anyone please tell me what was wrong with my Solution.