PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: khaab_2004
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
3144
PREREQUISITES:
None
PROBLEM:
You have two arrays A and B of length N.
The following operation can be performed:
- Pick an index i (1 \leq i \leq N), then:
- Delete B_N from B and append it to A.
- Delete A_i from A and insert it in B, just before B_i.
Using at most 2\cdot 10^5 operations, turn A into a palindrome or claim that this is impossible.
EXPLANATION:
First, let’s find out whether we have enough integers to form a palindrome at all.
We want A_i = A_{N+1-i} for each i, meaning integers have to come in pairs (except the middle element when N is odd).
Let \text{freq}[x] denote the number of times x occurs across both arrays.
Then, the largest number of equal pairs we can form is
If this quantity is \lt \left\lfloor\frac{N}{2}\right\rfloor, then forming a palindrome is clearly impossible.
Otherwise, it turns out to always be possible!
Let’s first fix what the final palindrome is going to be, then we just need to perform some operations to bring elements to their respective positions.
That is, pick \left\lfloor\frac{N}{2}\right\rfloor pairs of equal characters, which will become our palindrome (if N is odd, the middle character can be anything so just pick an unchosen element).
Now, we have N ‘marked’ elements and N unmarked elements.
The marked elements further can be given an order from 1 to N, deciding which element ends up at which position.
We’ll attempt to place elements into their respective places in order from 1, 2, 3, \ldots, N.
First, observe that performing an operation with i = 1 ‘rotates’ the entire array one step.
So, using at most 2N operations, we can bring any of the elements to position 1 of array A.
Suppose we do this. There are two cases:
- First, the element at B_1 might be unmarked.
If this is the case, we can simply recursively solve for elements 2, 3, \ldots N and never perform an operation with i = 1 again. - Second, the element at B_1 might be marked; then to get it out we’ll need to use an operation at i = 1 again which would disturb A_1.
This is undesirable, so let’s instead work towards making sure that whenever we bring the first element to A_1, the element at B_1 is unmarked.
Let x be the element we want to bring to A_1.
Note that what we want, is essentially that the element immediately after x (in counterclockwise cyclic order) should be unmarked.
One way to achieve that is as follows:
- First, perform operations at i = 1 till x ends up at A_N.
- Next, perform operations with i = 1 till the element immediately below x is unmarked.
Note that this takes at most N steps, since there are only N marked elements and each step has a different element below x. - If this is reached when x is at A_j, perform one operation at j.
Now, x is at B_j, and B_{j+1} is an unmarked element (if j = N, A_N will be unmarked instead).
That is, the element immediately following x is unmarked, as we wanted!
In total, we use at most:
- 2N moves to bring x to A_N
- N moves to find an unmarked element below x, and one move to fix their order.
- Another 2N moves to bring x to position A_1.
For an upper bound of 5N moves.
Since we do this for each i = 1, 2, 3, \ldots, N, the total number of moves is bounded by 5\cdot N\cdot (N+1)/2, which is 100500 for N = 200.
In practice, the number of moves will be less because most iterations aren’t going to require 5N moves (and it even depends on the elements you choose for the palindrome and where you choose to put them in the end).
Each rotation can be simulated directly in \mathcal{O}(N) time, for a solution in \mathcal{O}(N^3) overall.
TIME COMPLEXITY
\mathcal{O}(N^3) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
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);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
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);
}
};
input_checker inp;
void Solve()
{
int n = inp.readInt(1, 200);
inp.readEoln();
vector<vector<int>> a(2, vector<int>(n));
a[0] = inp.readInts(n, 1, 600); inp.readEoln();
a[1] = inp.readInts(n, 1, 600); inp.readEoln();
inp.readEof();
// int n; cin >> n;
// vector<vector<int>> a(2, vector<int>(n));
// for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
int x = 501;
vector <vector<pair<int, int>>> adj(x);
for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++){
adj[a[i][j]].push_back({i, j});
}
int ok1 = 0;
for (int i = 1; i < x; i++){
ok1 += ((int)adj[i].size()) / 2;
}
if (ok1 < (n / 2)){
cout << -1 << "\n";
return;
}
vector<pair<int, int>> w(n);
int p1 = 0, p2 = n - 1;
for (int i = 1; i < x; i++){
while (adj[i].size() >= 2 && p1 < p2){
w[p1] = adj[i].back(); adj[i].pop_back();
w[p2] = adj[i].back(); adj[i].pop_back();
p1++;
p2--;
}
}
for (int i = 1; i < x; i++){
if (adj[i].size() && p1 == p2){
p1++;
w[p2] = adj[i].back();
}
}
vector<vector<int>> ok(2, vector<int>(n, 0));
for (int i = 0; i < n; i++){
ok[w[i].first][w[i].second] = i + 1;
}
vector <int> ops;
auto doop = [&](int i){
assert(1 <= i && i <= n);
int ai = ok[0][i - 1];
for (int j = i - 1; j < n - 1; j++){
ok[0][j] = ok[0][j + 1];
}
ok[0][n - 1] = ok[1][n - 1];
for (int j = n - 1; j >= i; j--){
ok[1][j] = ok[1][j - 1];
}
ok[1][i - 1] = ai;
ops.push_back(i);
if (ops.size() > (int)1e5) exit(0);
};
auto find = [&](int x){
for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++){
if (ok[i][j] == x){
return make_pair(i, j);
}
}
assert(false);
return make_pair(-1LL, -1LL);
};
for (int i = 1; i <= n; i++){
bool done = false;
while (ok[0][i - 1] != i || ok[1][i - 1] != 0){
auto pos = find(i);
if (pos.first == 0 && ok[1][pos.second] == 0 && !done){
done = true;
doop(pos.second + 1);
continue;
}
doop(i);
}
}
cout << (int)ops.size() << "\n";
for (auto x : ops) cout << x << " ";
cout << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}