NSA - Editorial

#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:

1 Like

@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

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 CodeChef: Practical coding for everyone