PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic programming, binary search (optional)
PROBLEM:
Alice and Bob play a game on an array.
While the length of the array is at least 2, Alice must choose an index that’s not an endpoint, and Bob will delete either the prefix ending there or the suffix starting there.
Alice wants to maximize the largest remaining value, while Bob wants to minimize it.
Find Alice’s score under optimal play.
EXPLANATION:
It’s not immediately obvious what Alice’s optimal strategy should be.
So, rather than explicitly find Alice’s strategy, let’s work with a simpler problem first.
We fix a value K and ask the question: can Alice obtain a score of at least K?
To answer this, note that once K is fixed, all values smaller than K become equivalent; and all values equal or larger to K become equivalent.
So, we can convert the array A into a binary string B, where B_i = 1 if and only if A_i \ge K.
The question now is: when is this binary string “winning” for Alice?
Meaning, can she force a sequence of moves such that in the end, at least one 1 (denoting an element \ge K) will remain?
If the length of B is \le 2, then B is winning if and only if it contains a 1.
This gives us the strings \{1, 01, 10, 11\} of lengths 1 and 2 that are winning.
As for strings of length \ge 3, suppose Alice picks index i to “split” the string.
Then, Bob has the option of either deleting the prefix or the suffix involving i; meaning he has the choice of turning the string into either B_1B_2\ldots B_{i-1} or B_{i+1}B_{i+2}\ldots B_N.
Note that if either of these smaller strings are “losing” states for Alice, Bob can choose to go to a “losing” state after which Alice’s hopes of getting a score of \ge K are dashed.
So, the only possible way for Alice to win is if both smaller states are “winning” states.
This tells us the following:
A string B of length \ge 3 can be winning if and only if it can be written as B = P + c + S, where P is a winning non-empty prefix of B, S is a winning non-empty suffix of B, and c is a single character.
(Here, + denotes string concatenation.)
That is, B is winning if and only if we can delete one internal character from it, and both resulting strings are also winning.
Another way to see this is that we can “build up” winning strings by gluing together smaller winning strings.
More precisely, if S_1 and S_2 are both winning strings, then (S_1 + 0 + S_2) and (S_1 + 1 + S_2) are also winning strings.
However, recall that our “base” winning strings were a handful of those having length \le 2.
This means any winning string can be obtained by just gluing together several “base” winning strings, with one separating character between each pair!
That is, a string S if winning if and only if it can be broken up into several substrings of length at most 2, where each of these substrings comes from \{1, 01, 10, 11\}, and between each of the substrings there’s exactly one separating character.
More formally, S is winning if and only if there exist several pairs (l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k) such that:
- l_1 = 1 and r_k = N
- r_i = l_i or r_i = l_i+1 for each i
- This means each substring has length at most 2.
- For i \gt 1, l_i = r_{i-1} + 2
- This means the index l_i-1 is not included in any of the substrings, and in fact separates the i-th and (i-1)-th substrings.
- \max(S_{l_i}, S_{r_i}) = 1
- Each chosen substring contains a 1.
With the above criterion in hand, it’s not hard to devise an \mathcal{O}(N) algorithm to decide if a string follows this pattern, using dynamic programming.
Let dp_i be true if the prefix of length i of the string follows this pattern, and false otherwise.
To check dp_i, we have two options:
- Index i can form a subarray of length 1.
In this case, index i-1 must be a separator; and everything till index i-2 can then be decided independently.
So, this is allowed only if dp_{i-2} is true.
Further, S_i = 1 must hold, since a length-1 substring is only allowed when it equals 1. - Indices i-1 and i can form a subarray of length 2.
In this case, i-2 will become a separator; so this is only possible when dp_{i-3} is true.
Further, either S_{i-1} or S_i must equal 1 for this to be a valid substring.
If either case works, dp_i is true; otherwise it’s false.
In the end, S is winning if and only if dp_N is true.
This gives us a linear-time check for a fixed value of K.
We can now simply binary search on the value of K to obtain the largest valid K, giving us our answer.
It’s in fact possible to further optimize this solution to run in \mathcal{O}(N) time with one more observation (skipping the binary search entirely.)
That is more relevant to solving the harder version however, and so will be discussed in that editorial instead.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector a(n, 0);
for (int &x : a) cin >> x;
auto check = [&] (int k) {
vector dp(n, 0);
dp[0] = (a[0] >= k);
if (n > 1) dp[1] = (max(a[0], a[1]) >= k);
for (int i = 2; i < n; ++i) {
if (a[i] >= k and dp[i-2] == 1) dp[i] = 1;
if (i >= 3 and max(a[i], a[i-1]) >= k and dp[i-3] == 1) dp[i] = 1;
}
return dp[n-1];
};
int lo = 1, hi = n;
while (lo < hi) {
int mid = (lo + hi + 1)/2;
if (check(mid)) lo = mid;
else hi = mid-1;
}
cout << lo << '\n';
}
}