NSA - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

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:

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 ???

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.
Please explain this;;thanks.

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)

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

Can anyone please tell me what was wrong with my Solution.
Thanks in Advance :slight_smile:

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

How do we arrive at the formula Y=Y0−(B[i][c1]+F[i][c1])+(B[i][c2]+F[i][c2]) ?

Thank you for the clear and informative editorial. It helped me understand and submit a valid solution. Cheers!

Needed little explanation on how we reach to that formula.

because the solutions provided are barely readable.

I wish the editorial to be more explanatory. Maybe by taking an example string and then showing the arrays B and F for that. Next time maybe :slight_smile:

@melfice why are you using int64_t?

Hey, I have a query, If we change the letter at some jth position in the string then why are we not updating all the F[i][c] where i<j because due to the change at jth position there is a possibility that the updated letter at jth position becomes greater than then letter at some ith position but initially the not-updated letter was lower than the letter at that i’th position ?

Can someone point out where my logic goes wrong
https://www.codechef.com/viewsolution/19322490

Can anyone please tell why my code is giving WA for 2 test cases?
https://www.codechef.com/viewsolution/19349035

Please post solution link instead of entire code.

2 Likes

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

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

1 Like