Blog entries - Codeforces

#	User	Rating
1	tourist	3856
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3462
9	ecnerwala	3451
10	heuristica	3431

#	User	Contrib.
1	cry	167
2	-is-this-fft-	162
3	Dominater069	160
4	Um_nik	158
5	atcoder_official	156
6	Qingyu	154
7	djm03178	152
7	adamant	152
9	luogu_official	150
10	awoo	147

I was solving this problem 2069D\ - Palindrome Shuffle. It is giving me Runtime error on test 2. My idea to solve this problem is to first know how many chars from the beginning of the string equal chars from the end, so these chars don't have to be swapped with any other char. Then in the rest of the string I should use suffix or prefix of the string to make it palindrome. To calculate the answer to the problem, it is just the max distance between the end of the string and a char I used to do the swap. My code is in the spoiler.

Spoiler

void solve() {

string s;
cin>>s;

int n=sz(s);
int mx=0;
for (int i=0;i<n/2;i++){
    if (s[i]==s[n-1-i]){
        mx++;
    }
    else break;
}

string g=s.substr(mx,n-2*mx);
string g2="";
for (int i=sz(g)-1;i>=0;i--){
    g2+=g[i];
}
//cout<<g<<' '<<g2<<endl;
int m=sz(g);
int ans=m;
vector <vector <int> > v(26),v2(26);
for (int i=0;i<m;i++){
    v[g[i]-'a'].pb(i);
}
mx=0;
for (int i=m-1,j=0;i>j;i--,j++){
    if (g[i]!=g[j]){
        int a=g[i]-'a',b=g[j]-'a';
        int l=sz(v[b])-1;
        if (l==-1){
            mx=INT_MAX;
            break;
        }
        mx=max(mx,m-v[b][l]);
         int ind=sz(v[a])-1;
          int x=v[b][l];
          int y=v[a][ind];
        v[a][ind]=x;
          v[b][l]=y;
        swap(g[i],g[x]);

    }
    v[g[i]-'a'].pop_back();
}
//cout<<g<<endl;
ans=min(ans,mx);
mx=0;

for (int i=0;i<m;i++){
    v2[g2[i]-'a'].pb(i);
}
for (int i=m-1,j=0;i>j;i--,j++){
    if (g2[i]!=g2[j]){
        int a=g2[i]-'a',b=g2[j]-'a';
        int l=sz(v2[b])-1;
        if (l==-1){
            mx=INT_MAX;
            break;
        }
        mx=max(mx,m-v2[b][l]);
         int ind=sz(v2[a])-1;
          int x=v2[b][l];
          int y= v2[a][ind];
          v2[a][ind]=x;
          v2[b][l]=y;
        swap(g2[i],g2[x]);

    }
    v2[g2[i]-'a'].pop_back();
}
//cout<<g2<<endl;
ans=min(ans,mx);
cout<<ans<<endl;

}

Full text and comments »

mahmoud13's blog