AI Translated from Chinese
Problem
Problem: Given an n-permutation p[], select an interval [l, r] (l <= r), construct a new permutation: a[r+1:] + a[l:r].reverse() + a[1:l] (using Python slice notation, i.e., left-closed right-open interval). Find the lexicographically largest permutation that can be constructed.
Analysis
Assume the answer is represented by $ ans_i $.
Initial analysis: when $ r = n $, $ ans_1 = r_n $, otherwise $ ans_1 = r_{n+1} $. To ensure lexicographic maximum, we need to select the largest possible $ r $.
It’s easy to know that when $ p_1 = n $, $ r $ should be $ n-1 $, otherwise select $ n $.
After determining $ r $, look at $ l $. There’s a trick: first output a[r+1:] + a[r], then traverse from a[r-1] backward. As long as a[i] < a[1] (indicating that if $ l $ is chosen as $ i $, the operation would make the lexicographic order smaller, so $ l $ is chosen as $ i+1 $), immediately output a[1:i+1] (note this is still a left-closed right-open interval).
This is the CF editorial solution:
In these constraints we could solve the problem for $ O(n^2) $. Let us note that there can be no more than two candidates for the value $r$. Since the first number in the permutation will be either $p_r+1$ if $r<n$, or $p_r$ if $r=n$. Then let’s go through the value of $r$ and choose the one in which the first number in the resulting permutation is as large as possible. Next, if $p_n=n$, then we can have two candidates for $r$ is $n$,$n−1$, but note that it is always advantageous to put $r=n$ in that case, since it will not spoil the answer. Then we can go through $l$, and get the solution by the square, but we can do something smarter.
Notice now that the answer already contains all the numbers $p_i$ where $i>r$. And then we write $p_r$, $p_r−1$, …, $p_l$ where $l$ is still unknown, and then $p_1$, $p_2$, …, $p_l−1$. In that case, let’s write pr as $l≤r$ and then write $p_r−1$, $p_r−2$, … as long as they are larger than $p_1$. Otherwise, we immediately determine the value of $l$ and finish the answer to the end. Thus, constructively we construct the maximal permutation.
Code
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _all(x) (x).begin(), (x).end()
#define _abs(x) ((x >= 0) ? (x) : (-x))
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define PDD pair<double, double>
#define fi first
#define se second
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f;
const LL LINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
using namespace std;
const int N = 2000 + 20;
int n, a[N];
void init() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
}
void solve() {
int r = 1;
// choose r, i.e. find the largest num in a[1:n] and record its index
// if a[i] == n, choose a[r] == n-1
// else a[r] == n
for (int i = 1; i <= n; i++) {
if (a[min(n, r+1)] <= a[min(n, i+1)]) r = i;
}
// cout << a[r+1:]
for (int i = r+1; i <= n; i++) cout << a[i] << ' ';
cout << a[r] << ' ';
// cout << a[r-1]..a[l] << a[1:l]
for (int i = r-1; i > 0; i--) {
if (a[i] > a[1]) {
cout << a[i] << ' ';
}
// find l: l = i-1
else {
for (int j = 1; j <= i; j++) {
cout << a[j] << ' ';
}
break;
}
}
cout << "\n";
}
int main() {
IOS
int test_case;
cin >> test_case;
while (test_case--) {
init();
solve();
}
return 0;
}
The CF editorial solution is brilliant:
int r = 1;
for (int i = 1; i <= n; i++) {
if (a[min(n, r+1)] <= a[min(n, i+1)]) r = i;
}
Equivalent to:
int r = 1;
if (a[1] == n) {
if (a[n] == n-1) {
r = n;
}
else for (int i = 2; i <= n; i++) {
if (a[i] == n-1) {
r = i-1;
break;
}
}
}
else {
if (a[n] == n) {
r = n;
}
else for (int i = 1; i <= n; i++) {
if (a[i] == n) {
r = i-1;
break;
}
}
}
Elegantly compressed my dozen lines of code at the time into just two or three lines.
Summary
I was stuck on this problem at the time. After finding $ r $, I didn’t know how to proceed. Actually, just need to slightly change the way of thinking, think in reverse (￣▽￣)