PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Yash Goyal
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
2875
PREREQUISITES:
None
PROBLEM:
Given two strings A and B, each of length N, where string B is a permutation of string A.
You can perform the following operation on string A:
- Break string A into 3 substrings (may be empty) S_1, S_2, and S_3 such that S_1+S_2+S_3=A, where |S_1|, |S_2|, |S_3| \ge 0;
- Replace A with S_3+S_2+S_1.
Note that, + denotes the concatenation of two strings and |S| denotes the length of the string S.
You have to convert string A to string B by performing no more than N operations.
EXPLANATION:
A quick observation: if A is a cyclic shift of B, then with 1 operation we can bring A to B. Therefore, instead of directly constructing B from A in N operations, we can instead try to construct a cyclic shift of B from A in N - 1 operations. This relaxation from a fixed string to a cyclic string will help us a lot in the problem. Additionally, instead of thinking of A and B as strings, let’s think of them as permutations: B is the identity permutation, while A is some permutation of values from 1 to N (this will make explaining much easier).
Suppose the array is currently A = [A_1, A_2, A_3, \dots, A_i, \dots, A_N], where A_i = (A_N + 1) \bmod N). We want to move A_i to right behind A_N, and we can do so with this operation:
- i - 1, 1, N - i, which turns A into A = [A_{i + 1}, A_{i + 2}, \dots, A_N, A_i, A_1, A_2, \dots, A_{i - 1}].
Now that we have moved A_i to right after A_N, let’s “group” A_N and A_i into a single element called A', so the array A turns into A = [A_{i + 1}, A_{i + 2}, \dots, A_{N - 1}, A', A_1, A_2, \dots, A_{i - 1}]. This grouping ensures that from the current operation onwards, A_N and A_i will be locked being consecutive. Therefore, we have effectively reduce the size of A by 1, and now we can keep doing this operation until the size of A is 1, which is when A becomes a cyclic shift of B.
TIME COMPLEXITY:
Time complexity is O(N^2) per test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double pi = acos(-1);
#define _time_ 1.0 * clock() / CLOCKS_PER_SEC
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(),a.end()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn=1e5+5;
void solve(){
int n;
cin >> n;
string a,b;
cin >> a >> b;
vector<string> x,y;
vector<vector<int>> ans;
for(int i=0;i<n;i++){
x.push_back(string(1,a[i]));
y.push_back(string(1,b[i]));
}
auto perform_op = [&](int i,int j,int k){
int l1,l2,l3;
l1=l2=l3=0;
vector<string> x1,x2,x3;
for(int u=0;u<i;u++){
l1 += (int)x[u].size();
x1.push_back(x[u]);
}
for(int u=i;u<i+j;u++){
l2 += (int)x[u].size();
x2.push_back(x[u]);
}
for(int u=i+j;u<i+j+k;u++){
l3 += (int)x[u].size();
x3.push_back(x[u]);
}
x2[0] = x3.back()+x2[0];
x3.pop_back();
x=x3;
x.insert(x.end(),x2.begin(),x2.end());
x.insert(x.end(),x1.begin(),x1.end());
ans.push_back({l1,l2,l3});
};
while(x.size()!=1){
int j = find(y.begin(),y.end(),x.back())-y.begin();
y[j] += y[(j+1)%(int)y.size()];
j++;
j%=(int)y.size();
string ch = y[j];
y.erase(y.begin()+j);
int i=0,k=0;
j=0;
for(int z=0;z<x.size();z++){
if(ch.size()==x[z].size() && x[z]==ch){
i=z;
j=1;
k=x.size()-1-z;
break;
}
}
perform_op(i,j,k);
}
for(int i=0;i<n;i++){
int ok=1;
for(int j=i;j<i+n;j++){
if(b[j-i]!=x[0][j%n]){
ok=0;
}
}
if(ok){
ans.push_back({0,i,n-i});
break;
}
}
cout << ans.size() << "\n";
for(auto u:ans){
for(auto v:u){
cout << v << " ";
}
cout << "\n";
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("input4.txt", "r", stdin);
// freopen("output4.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;
cin >> t;
while(t--){
solve();
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n;
vector<int>f[226];
vector<int>p;
vector<pair<int,int> >q;
vector<pair<int,int> >fmap(vector<int> v){
vector<pair<int,int> >z;
for(auto c:v){
if(!z.empty() && z.back().se+1==c) z.back().se++;
else z.push_back({c,c});
}
return z;
}
vector<int>gmap(vector<pair<int,int> >z){
vector<int>v;
for(auto c:z){
for(int i=c.fi; i<=c.se ;i++) v.push_back(i);
}
return v;
}
int len(pair<int,int> c){
return c.se-c.fi+1;
}
typedef array<int,3> arin;
vector<arin>ans;
void move(int s1,int s2,int s3){
//cout << "move " << s1 << ' ' << s2 << ' ' << s3 << endl;
ans.push_back(arin{s1,s2,s3});
auto pp=p.begin();
reverse(pp,pp+s1);
reverse(pp+s1,pp+s1+s2);
reverse(pp+s1+s2,pp+s1+s2+s3);
reverse(p.begin(),p.end());
}
void solve(){
cin >> n;ans.clear();
p.resize(n);
for(int i=0; i<n ;i++){
char c;cin >> c;f[c].push_back(i);
}
for(int i=1; i<=n ;i++){
char c;cin >> c;
p[f[c].back()]=i;f[c].pop_back();
}
while(true){
q=fmap(p);/*
cout << "iter " << endl;
for(auto c:p) cout << c << ' ';cout << endl;
for(auto c:q) cout << c.fi << ',' << c.se << ' ';cout << endl;*/
if(q.size()==1) break;
else if(q.size()==2) move(len(q[0]),len(q[1]),0);
else if(q.size()==3) move(len(q[0]),len(q[1]),len(q[2]));
else if(q[0].fi!=1 && q[0].se!=n){
int pos=1;
while(q[pos].se+1!=q[0].fi) pos++;
int lena=len(q[0]);
int lenb=0;
for(int i=1; i<=pos ;i++) lenb+=len(q[i]);
move(lena,lenb,n-lena-lenb);
}
else if(q.back().fi!=1 && q.back().se!=n){
int bb=q.size()-1;
int pos=bb-1;
while(q.back().se+1!=q[pos].fi) pos--;
int lenc=len(q[bb]);
int lenb=0;
for(int i=pos; i<bb ;i++) lenb+=len(q[i]);
move(n-lenb-lenc,lenb,lenc);
}
else if(q[0].se==n){
int pos=1;
while(q[pos].se+1!=q[0].fi) pos++;
int lena=0;
int lenb=len(q[pos]);
for(int i=0; i<pos ;i++) lena+=len(q[i]);
move(lena,lenb,n-lena-lenb);
}
else{
move(1,0,n-1);//sad but once only
}
//system("Pause");
}
cout << ans.size() << '\n';
for(auto c:ans){
cout << c[0] << ' ' << c[1] << ' ' << c[2] << '\n';
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;while(t--) solve();
}