PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
DIFFICULTY:
Easy
PREREQUISITES:
Greedy
PROBLEM:
You are given a string S. You can swap adjacent elements, but you can’t swap the same element twice. Determine if you can make S a palindrome and the minimum number of swaps to do so.
QUICK EXPLANATION
We try to make S a palindrome starting from the two ends of S. We move inwards during the process, swapping adjacent elements whenever necessary.
EXPLANATION:
In order for S to be a palindrome, S_0 must match S_{N-1}. Also, since we can’t swap the same element twice, the order that we perform the swaps in does not matter. We will start considering from the ends of S as it’s simpler.
First, if S_0 is already equal to S_{N-1}, it should be intuitive that we don’t need to perform any swaps with those two elements.
Proof
If we only swap one of S_0 and S_{N-1}, then S_0 and S_{N-1} won’t match (unless S_0=S_1 or S_{N-1}=S_{N-2}, but then swapping will be pointless), so we need to swap both.
If S_0=S_{N-1} after swapping, then S looks something like \text{AB}\cdots\text{BA} before the two swaps. After swapping, S=\text{BA}\cdots\text{AB}. We can see that two swaps are useless, as the two swaps won’t change S from a non-palindrome to a palindrome.
Otherwise, S_0 is not equal to S_{N-1}. How can we possibly fix this? There are two things we could do: we could swap S_0 with S_1 or we could swap S_{N-1} with S_{N-2}.
Swapping S_0 with S_1 only works if S_1=S_{N-1} and 1<N-1. Similarly, swapping S_{N-1} with S_{N-2} only works if S_0=S_{N-2} and 0<N-2.
If none of these two conditions are satisfied, then there is no solution. If exactly one of these two conditions is satisfied, then we can perform the swap according to the condition that is satisfied. What if both of these conditions are satisfied? Which swap should we perform?
It turns out that it doesn’t matter. Even though the elements in the pair we choose to swap cannot be swapped again in the future, we won’t need to swap the elements in either pair afterwards.
So after checking some cases, we manage to match S_0 with S_{N-1}. The next thing is to match S_1 with S_{N-2}. How do we do that? We can use the same casework as above.
There’s a small difference, though: We might have already swapped S_1 or S_{N-2}. But this isn’t very hard to fix. Before performing another swap, we will check if the elements we’re swapping have already been swapped before.
Once we make sure S_1=S_{N-2}, we can move on to S_2 and S_{N-3}. In general, we increment the left index and decrement the right index and perform the same process, until we have matched all characters.
Here’s some pseudocode just to make sure you know all of the cases to consider:
- Initialize l=0, r=N-1.
- While l<r, perform the following process (we try to match S_l with S_r):
- If S_l=S_r, we don’t need to do anything.
- If l+1=r, swapping S_l with S_{l+1} or S_r with S_{r-1} will just swap S_l with S_r, which won’t make them match, so there is no solution.
- If S_l has not been swapped before and S_{l+1}=S_r, swap S_l with S_{l+1}.
- If S_r has not been swapped before and S_l=S_{r-1}, swap S_r with S_{r-1}.
- Otherwise, none of the two swaps works and there is no solution.
- Increment l and decrement r.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n;
string s;
int sm_n=0;
int main(){
//freopen("03.txt","r",stdin);
//freopen("03o.txt","w",stdout);
T=readIntLn(1,10000);
while(T--){
n=readIntLn(1,100000);
sm_n += n;
assert(sm_n<=1000000);
s=readStringLn(n,n);
for(int i=0;i<n;i++){
assert('a' <= s[i] && s[i]<= 'z');
}
bool ok=true;
bool L=true,R=true;
int mn=0;
for(int i=0;i<n/2;i++){
if(n% 2 == 0 && i == n/2-1){
if(s[i] != s[n-i-1]){
ok=false;
}
continue;
}
if(s[i] == s[n-i-1]){
L=true;
R=true;
continue;
}
if(s[i+1] == s[n-i-1] && L==true){
swap(s[i],s[i+1]);
L=false;
R=true;
mn++;
continue;
}
if(s[i] == s[n-i-2] && R==true){
swap(s[n-i-1],s[n-i-2]);
L=true;
R=false;
mn++;
continue;
}
ok=false;
break;
}
if(!ok){
cout<<"NO"<<endl;
} else {
cout<<"YES"<<endl;
cout<<mn<<endl;
}
}
assert(getchar()==-1);
}
Tester's Solution
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int n;
int dp[123456][2][2];
int visit[123456][2][2];
string s;
int solve(int ind,int swap1,int swap2){
int opp=n-1-ind,x,y;
if(opp==ind+2){
x=ind-swap1;
y=opp+swap2;
if(s[x]==s[y])
return 0;
if(swap2==0 && s[x]==s[opp-1])
return 1;
//cout<<x<<" "<<y<<endl;
if(swap1==0 && s[y]==s[ind+1])
return 1;
return inf;
}
if(opp==ind+1){
x=ind-swap1;
y=opp+swap2;
if(s[x]==s[y])
return 0;
return inf;
}
if(visit[ind][swap1][swap2])
return dp[ind][swap1][swap2];
visit[ind][swap1][swap2]=1;
x=ind-swap1;
y=opp+swap2;
dp[ind][swap1][swap2]=inf;
if(s[x]==s[y]){
//cout<<ind<<" "<<x<<" "<<y<<endl;
dp[ind][swap1][swap2]=solve(ind+1,0,0);
}
if(swap1==0 && s[ind+1] == s[y]){
dp[ind][swap1][swap2]=min(dp[ind][swap1][swap2],1+solve(ind+1,1,0));
}
if(swap2==0 && s[x]==s[opp-1]){
dp[ind][swap1][swap2]=min(dp[ind][swap1][swap2],1+solve(ind+1,0,1));
}
return dp[ind][swap1][swap2];
}
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
cin>>n;
cin>>s;
if(n==1){
cout<<"YES"<<endl;
cout<<0<<endl;
continue;
}
int i,j,k;
rep(i,n+10){
rep(j,2){
rep(k,2){
visit[i][j][k]=0;
}
}
}
int ans=solve(0,0,0);
if(ans>n+10){
cout<<"NO"<<endl;
}
else{
cout<<"YES"<<endl;
cout<<ans<<endl;
}
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
void solve() {
cin >> n >> s;
int ans=0;
//whether l and r have been swapped
bool bl=0, br=0;
for(int l=0, r=n-1; l<r; ++l, --r) {
if(s[l]==s[r]) {
//l and r match already, we don't need to do anything
bl=br=0;
continue;
}
if(l+1==r) {
//l and r adjacent, swapping is useless
cout << "NO\n";
return;
}
//try to swap l and l+1
if(!bl&&s[l+1]==s[r]) {
swap(s[l], s[l+1]);
bl=1;
br=0;
++ans;
}
//try to swap r and r-1
else if(!br&&s[l]==s[r-1]) {
swap(s[r-1], s[r]);
bl=0;
br=1;
++ans;
}
//nothing works
else {
cout << "NO\n";
return;
}
}
cout << "YES\n" << ans << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
}
HIDDEN TRAPS:
- Missing an edge case mentioned above.
Please give me suggestions if anything is unclear so that I can improve. Thanks 