G - "redocta".swap(i,i+1) Editorial by en_translator Editorial for printing
Solution 1. Search
We can determine how many operations is needed at minimum to make \(S\) equal atcoder in manner of BFS, regarding the current string as a vertex.
During the implementation, it is useful to use a queue or a map (associative array).
The complexity is \(O(|S|!)\) (but this time, the complexity is constant because \(|S|\) is fixed to \(7\).)
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
map<string,int> mp;
queue<string> q;
mp[s]=0;
q.push(s);
while(!q.empty()){
string current=q.front();q.pop();
if(current=="atcoder"){
cout << mp[current] << "\n";
return 0;
}
for(int i=1;i<7;i++){
string next=current;
swap(next[i-1],next[i]);
if(mp.find(next)==mp.end()){
q.push(next);
mp[next]=mp[current]+1;
}
}
}
return 0;
}
Solution 2. Use the “inversion number”
Since atcoder consists of \(7\) distinct characters, we may consider replacing the \(i\)-th character of atcoder with an integer \(i\).
For example, an input catredo can be replaced with a sequence \((3,1,2,7,6,5,4)\).
What is the minimum number of swaps required to make the sequence equal \((1,2,3,4,5,6,7)\)? This is a famous problem called “inversion number.”
We do not explain the specific way to solve, but for example, Chokudai Speedrun 001-J is exactly the problem that asks to find the inversion number.
The time complexity is \(O(|S| \log |S|)\) (but just as before, \(|S|\) is fixed to \(7\), so this is a constant time too.)
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
vector<int> bit;
int sum(int i){
int s=0;
while(i>0){
s+=bit[i];
i-=i&(-i);
}
return s;
}
void add(int i,int x){
while(i<bit.size()){
bit[i]+=x;
i+=i&(-i);
}
}
int main(){
bit.resize(10);
for(int i=0;i<10;i++){bit[i]=0;}
string s;
cin >> s;
map<char,int> mp;
string atc="*atcoder";
for(int i=1;i<=7;i++){
mp[atc[i]]=i;
}
vector<int> a={-1};
for(int i=0;i<7;i++){
a.push_back(mp[s[i]]);
}
int res=0;
for(int i=1;i<=7;i++){
res+=(i-1-sum(a[i]));
add(a[i],1);
}
cout << res << "\n";
return 0;
}
posted:
last update: