PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Alice and Bob play a game on a permutation P, alternating turns:
- Alice chooses a subarray and deletes its maximum element.
- Bob chooses a subarray and deletes its minimum element.
The chosen subarray must have length \geq 2.
The score of the game is the value of the final element.
Alice wants to maximize the score, Bob wants to minimize it.
Before the start of the game, Alice can swap any two adjacent elements. Each time she does this, her score will decrease by 1.
What’s the best possible final score for Alice?
EXPLANATION:
First, let’s try to solve the base problem: if P is fixed, what will the score be?
Answer
The actual answer to this is in fact quite simple:
- If N is even, the score is \min(P_1, P_N).
- If N is odd, the score is \max(P_1, P_N).
Why is that the answer?
Alice wants the final element to be large, so it’s in her best interest to delete small elements; however, she deletes large elements each time, which goes against that goal.
Similarly, Bob wants the answer to be small, but deletes small elements himself.Now, on the very last move, when the array has length 2, the person whose turn it is is forced to choose the entire array - and essentially make the worst possible move for them.
So intuitively, the person who has the last move (which is determined by the parity of N) will “have it worse”.This can be exploited by the other player.
For example, suppose N is even, so Alice has the last move. Without loss of generality, let P_1 \lt P_N.
Note that if Alice ever deletes A_1 on her move, it must’ve been the maximum of the chosen subarray - meaning all the other elements are less than A_1.
In particular, after the deletion, the new first element of the subarray will be strictly smaller than P_1.So, as long as Bob avoids choosing P_1 in a subarray entirely (which is always possible since on his moves, the array will have size \geq 3), the first element of P will always remain \leq P_1.
On Alice’s final turn, two elements will remain. Of them, the first will be \leq P_1.
Alice deletes the maximum, so the remaining element will definitely be \leq P_1 - meaning the score is \leq P_1.On the other hand, Alice can attain a score of exactly P_1 by simply ensuring she deletes neither P_1 nor P_N till her very last move where deletion of P_N is forced.
This works because just as Alice was restricted above, Bob cannot delete the last element of the array without increasing it - meaning as long as Alice doesn’t delete it, it will always remain \geq P_N.The case when N is odd is similar: just that Bob makes the last move, so Alice can guarantee a score of \max(P_1, P_N) instead.
Now, we must deal with adjacent swaps.
Suppose N is even, so the answer for a fixed P is \min(P_1, P_N).
We can simply try every possible value of \min(P_1, P_N) and take the best among them.
If we want \min(P_1, P_N) = x,
- x should be present at either position 1 or position N.
- Some y \gt x should be present at the other end.
Let \text{pos}[x] denote the initial position of x in P. Then,
- To place x at position 1, we need \text{pos}[x] - 1 swaps.
- To place x at position N, we need N - \text{pos}[x] swaps.
- So, to place x at 1 and some y\gt x at N, it’s optimal to choose the rightmost occurrence of some element \gt x to move; so the minimum number of swaps we need is:
The score of doing this is, of course, x minus the above expression.
The last maximum is a suffix maximum on the \text{pos} array, so if suffix maximums are precomputed this entire value can be found in \mathcal{O}(1) time.
This allows us to check every value of x and take the best among them.
Similarly, for the case where x is moved to position N and some y\gt x is moved to position 1, the optimal choice is the leftmost element \gt x, which corresponds to a suffix minimum of the \text{pos} array. Again, all possibilities can be checked in \mathcal{O}(N); take the best among them.
If N is odd, the idea is exactly the same: just that we’re dealing with x = \max(P_1, P_N) now, so instead of suffix minimums/maximums, we need to use prefix minimums/maximums.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
void solve(istringstream cin) {
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
p[i]--;
}
if (n % 2 == 1) {
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, p[i] + 1 - min(i, n - 1 - i));
}
cout << ans << '\n';
} else {
int mn = n;
int mx = -1;
int ans = 0;
vector<int> at(n);
for (int i = 0; i < n; i++) {
at[p[i]] = i;
}
for (int i = n - 1; i >= 0; i--) {
mn = min(mn, at[i]);
mx = max(mx, at[i]);
if (i < n - 1) {
ans = max(ans, i + 1 - mn - (n - 1 - mx));
}
}
cout << ans << '\n';
}
}
////////////////////////////////////////
// #define IGNORE_CR
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;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
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, 1e5);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 5e5);
sn += n;
in.readEoln();
auto p = in.readInts(n, 1, n);
in.readEoln();
auto q = p;
sort(q.begin(), q.end());
for (int i = 0; i < n; i++) {
assert(q[i] == i + 1);
}
ostringstream sout;
sout << n << '\n';
for (int i = 0; i < n; i++) {
sout << p[i] << " \n"[i == n - 1];
}
solve(istringstream(sout.str()));
}
cerr << sn << endl;
assert(sn <= 5e5);
in.readEof();
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
pos = [0]*(n+1)
for i in range(n):
pos[p[i]] = i+1
pmax, pmin = pos[:], pos[:]
for i in range(2, n+1):
pmax[i] = max(pmax[i], pmax[i-1])
pmin[i] = min(pmin[i], pmin[i-1])
smax, smin = pos[:], pos[:]
for i in reversed(range(1, n)):
smax[i] = max(smax[i], smax[i+1])
smin[i] = min(smin[i], smin[i+1])
ans = 1
for x in range(1, n+1):
# final = x
# n is even -> something > x should be at the other end
if n%2 == 0 and x < n:
ans = max(ans, x - (pos[x] - 1) - (n - smax[x+1]))
ans = max(ans, x - (n - pos[x]) - (smin[x+1] - 1))
# n is odd -> something < x should be at the other end
if n%2 == 1 and x > 1:
ans = max(ans, x - (pos[x] - 1) - (n - pmax[x-1]))
ans = max(ans, x - (n - pos[x]) - (pmin[x-1] - 1))
print(ans)