PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
3115
PREREQUISITES:
None
PROBLEM:
You’re given a string S.
In one move, you can pick a prefix of length x and a suffix of length y of S such that x+y \leq N, and swap them.
Find a way to sort S using at most N operations.
EXPLANATION:
Subtask 1 affords us 3N operations, while subtask 2 allows us only N.
Subtask 1
For convenience, let P_i denote the prefix of length i of S, and Q_i denote the suffix starting from index i.
That is, P_i = S[1\ldots i] and Q_i = S[i\ldots N].
There are several different ways to solve this subtask.
Here is one:
Consider some indices 1 \lt i \lt j \lt N.
Then, S_i and S_j can be swapped using three moves, without affecting any other characters, as follows:
- Swap P_i and Q_j. Now, S_i and S_j are the first and last characters of the string respectively.
- Swap the prefix and suffix of length 1, effectively swapping S_i and S_j.
- Once again swap P_i and Q_j, reversing the first operation but with elements flipped.
Using this strategy, the entire string can be sorted as follows:
- First, bring the smallest character to the first position using a single swap.
- Then, bring the largest character to the last position. This is not too hard:
Suppose we want to move S_i to the end. Swap P_1 and Q_i, then swap P_1 and Q_N.
This way, we moved S_i to the front and S_1 to the end, then swapped them. - Now, the first and last characters are set.
- All the characters in the middle can now be sorted using our three-step process from above:
- For each i = 2, 3, \ldots, N-1, if the correct character isn’t at position i, use three operations to bring it there.
This way, the whole string is sorted in at most 3N-3 operations.
Subtask 2
The second subtask has a limit of N moves, meaning we get about one move per index.
The key idea here is that we can build the sorted string from the middle, alternately extending it by one character to the left and right.
That follows from the following construction:
- Suppose S = \{P\} \ldots \ x \ \ldots, where P is the part we’ve constructed so far, and x is the character we want to insert at its beginning.
- Then, we can perform the move
where the chosen prefix is \{P\} and the chosen suffix is everything after x.
In case x is the last element, you can instead swap the prefix P with the entire rest of the string to get the same result.
This way, we’ve extended P to the left by one character using a single move.
Notice that the new sorted segment \{x P\} is now a suffix of the string.
It can be extended to the right by one character, with similar logic; after which it’ll become a prefix again.
This way, we can alternate between prepending and appending a character in a single move, and eventually sort the whole string.
To ensure you don’t run out of append/prepend moves, start the process from the middle (in sorted order) character.
TIME COMPLEXITY
\mathcal{O}(N^2) per testcase.
CODE:
Author's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=5010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n,k;
int rk[N],a[N];
char s[N],t[N];
vector<pair<int,int> > ans;
void swap(int x[],int l,int r)
{
vector<int> v;
for(int i=n-r;i<n;i++) v.push_back(x[i]);
for(int i=l;i<n-r;i++) v.push_back(x[i]);
for(int i=0;i<l;i++) v.push_back(x[i]);
for(int i=0;i<n;i++) x[i]=v[i];
/*
printf("after swap,a[]=");
for(int i=0;i<n;i++) printf("%d ",a[i]);
printf("\n");
*/
}
int main()
{
// freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d%d%s",&n,&k,s);
if(n==2&&s[0]==s[1])
{
printf("0\n");
continue;
}
vector<pair<int,int> > pr;
for(int i=0;i<n;i++) pr.push_back(make_pair(s[i],i));
sort(pr.begin(),pr.end());
for(int i=0;i<n;i++) rk[pr[i].second]=i;
for(int i=0;i<n;i++) a[i]=rk[i];
ans.clear();
for(int i=0;i<n;i++)
{
if(a[i]==n/2)
{
if(i)
{
ans.push_back(make_pair(1,n-i));
swap(a,1,n-i);
}
break;
}
}
for(int i=1;i<n;i++)
{
if(i&1)
{
int mx=-INF,pos;
for(int j=i;j<n;j++)
{
if(a[j]>a[0]) continue;
if(a[j]>mx) mx=a[j],pos=j;
}
if(pos==n-1)
{
ans.push_back(make_pair(i,n-i));
swap(a,i,n-i);
}
else
{
ans.push_back(make_pair(i,n-pos-1));
swap(a,i,n-pos-1);
}
}
else
{
int mn=INF,pos;
for(int j=0;j<n-i;j++)
{
if(a[j]<a[n-1]) continue;
if(a[j]<mn) mn=a[j],pos=j;
}
if(!pos)
{
ans.push_back(make_pair(n-i,i));
swap(a,n-i,i);
}
else
{
ans.push_back(make_pair(pos,i));
swap(a,pos,i);
}
}
}
//
//ans.push_back(make_pair(1,1));
//ans.push_back(make_pair(1,1));
//
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++) printf("%d %d\n",ans[i].first,ans[i].second);
}
//fclose(stdin);
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1000);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(2, 5000);
in.readSpace();
int k = in.readInt(n, 3 * n);
in.readEoln();
assert(k == n || k == 3 * n);
sn += n;
string s = in.readString(n, n, in.lower);
in.readEoln();
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return s[i] < s[j];
});
vector<int> a(n);
for (int i = 0; i < n; i++) {
a[order[i]] = i;
}
vector<pair<int, int>> ans;
auto Add = [&](int x, int y) {
vector<int> b;
for (int i = n - y; i < n; i++) {
b.emplace_back(a[i]);
}
for (int i = x; i < n - y; i++) {
b.emplace_back(a[i]);
}
for (int i = 0; i < x; i++) {
b.emplace_back(a[i]);
}
swap(a, b);
ans.emplace_back(x, y);
};
while (!is_sorted(a.begin(), a.end())) {
int x = 1;
while (x < n && a[x] - a[x - 1] == 1) {
x++;
}
int y = -1;
for (int i = 0; i < n; i++) {
if (a[i] == (a[0] + n - 1) % n) {
y = n - i - 1;
break;
}
}
if (y == 0) {
y = n - x;
}
Add(x, y);
}
cout << ans.size() << '\n';
for (auto [x, y] : ans) {
cout << x << " " << y << '\n';
}
}
assert(sn <= 5000);
in.readEof();
return 0;
}