# 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,b,c,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.
Thanks in Advance @melfice can you explain this problem in a simpler way. I am facing difficulty with understanding the dp part.

B[i][c] - number of letters less than c before position i.
So adding up all B[i][S[i]] = Base cost.
F[i][c] - number of letters greater than c after position i.
This is computed because to calculate the cost of changing a char we need to know its impact on the right side of the string.

Try printing out the variable cunt for different input strings and see if it is correct.

1 Like

hey guys why u’r making editorial so hard to learn??