PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: munch_01
Preparation: iceknight1093
Tester: mridulahi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Linked lists or heaps/sets
PROBLEM:
Alice and Bob play a game on an array A.
On their turn, a player chooses a maximum-length subsequence of A such that no two adjacent characters of A are equal, and deletes it from A.
The player who makes the last move wins.
Find the winner with optimal play.
EXPLANATION:
The important thing to observe here is that every move of both players is essentially forced!
Let A be the current array, and B be an empty array (that will hold the subsequence chosen by the current player).
B can then be built as follows:
- For each i = 1, 2, 3, \ldots |A|, if A_i doesn’t equal the last character of B (or B is empty), append A_i to B.
That is, B can be built greedily from left to right.
An alternate way of seeing this is that A is broken into several segments of equal elements, then one element (index doesn’t matter) is picked from each.
Proof of optimality
Let X = (x_1, x_2, \ldots, x_k) be the optimal subsequence picked by the player. Note that each x_i is an index here.
Then,
- If x_1 \neq 1, there are a couple of cases:
- If there exists an index x_0 such that x_0 \lt x_1 and A_{x_0} \neq A_{x_1}, we can insert x_0 at the beginning of the sequence to get a longer stingy subsequence; contradicting X being of maximum length.
- If A_{x_0} = A_{x_1} for every x_0 \lt x_1, we’ve chosen one index from the first “block” of equal characters; we might as well choose index 1 since it changes neither the chosen subsequence nor the resulting string after deletion.
- If x_1 = 1, ignore the block of characters equal to A_1 at the start and apply the same argument to the remaining part.
Since moves are uniquely determined, all we need to do is count the number of moves: if this is even, Bob wins; otherwise Alice wins.
However, brute-forcing this calculation by repeatedly finding the longest valid subsequence and erasing it is too slow, being \mathcal{O}(N^2).
There are a couple of ways to do it faster.
O(N)
It’s possible to solve this problem in linear time using a data structure not often seen in competitive programming: a linked list!
Let’s build the first subsequence chosen greedily, say S_1.
This is easy to do in linear time.
Now, note that by virtue of how the greedy solution picks elements, the second subsequence can only contain elements immediately after some index in S_1.
For example, if the first subsequence chose indices (1, 4, 5, 8, 11), then the only candidates for the second subsequence are \{2, 5, 6, 9, 12\}.
So, go over them in order, and check which of them are valid choices - some of them might not be, because they’re already deleted or cause equal adjacent characters.
EIther way, you’ll end up with a new subsequence S_2.
Simply repeat this process on S_2 to obtain S_3, and so on.
This way, the total work done is proportional to the sum of lengths of all the subsequences, which is just \mathcal{O}(N).
Note that to achieve linear time, you need deletion and finding the next element to be done in \mathcal{O}(1) time, which a doubly linked list can achieve.
The tester’s code below implements this method.
Of course, it’s also possible to just use something like a set to find the next undeleted element using binary search, giving a complexity of \mathcal{O}(N\log N) - which is fast enough for us.
O(N logN)
Here’s an alternate solution that’s a bit “stronger”: for instance, it can easily find the answer for every prefix of the string (even though we don’t need it here).
We’ll attempt to build every subsequence simultaneously, instead of one at a time.
Let \text{SUB} denote the list of subsequences, initially empty.
\text{SUB}[i] is the subsequence removed on the i-th move (recall that these are unique).
For each i = 1, 2, 3, \ldots, N, let’s try to decide which subsequence to insert A_i to.
As our greedy choice shows, A_i will go to the first subsequence that will accept it.
That is, we do the following:
- For each j from 1 to N in order, if the last element of \text{SUB}[j] does not equal A_i (or \text{SUB}[j] is empty), append A_i to this list and stop.
This doesn’t seem to help much, it’s still quadratic. So, let’s reduce things a bit.
Notice that only the last element of each subsequence matters, so every element of \text{SUB} can be reduced to the pair (x, id), denoting its last element and index (in \text{SUB}).
We then want to find the pair (x, id) with smallest id and x \neq A_i, and replace it with (A_i, id).
Here’s one way to do that.
Let E_x denote the list of all j such that \text{SUB}[j] ends with element x.
Then, notice that only the minimum element in E_x really matters, since if some subsequence ending in x is chosen, it’ll be this one (as per our greedy choice).
So, let M_x = \min(E_x).
Then, given A_i, we simply want to find the minimum M_x across all x that are not A_i.
This is quite easy to do!
Maintain all the M_x in a data structure that allows for quick insertion, deletion, and finding the minimum element (like a set in C++).
Then, delete M_{A_i} from this set, find the minimum, and then insert M_{A_i} back into it.
Now, each time something is updated, we need to change the information we have appropriately.
- The E_x lists need to be maintained properly.
They can also be maintained using sets - since we need to be able to insert/delete elements and find the minimum.
It’s also possible to use a priority queue here, since it can be seen that only the minimum is deleted each time. - The set M of minimums needs to be kept updated with the current minimums.
Each index results in only a couple of insertions/deletions (since one element is replaced with another).
So, with an appropriate data structure (like a set, as mentioned), the overall complexity is \mathcal{O}(N\log N).
The editorialist’s code below implements this method.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
//#define int long long
const int maxn = 3e6;
bool del[maxn];
int nex[maxn];
int pre[maxn];
void delx (int x) {
nex[pre[x]] = nex[x];
pre[nex[x]] = pre[x];
del[x] = 1;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a[n];
for (auto &x : a) cin >> x;
vector<int> v;
vector<int> v2;
int las = -1;
for (int i = 0; i < n; i++) {
del[i] = 0;
pre[i] = -1;
nex[i] = -1;
if (i) {
pre[i] = i - 1;
nex[i - 1] = i;
}
if (a[i] != las) v.push_back(i);
las = a[i];
}
int cn = 0;
while (sz(v)) {
cn++;
for (auto u : v) {
if (nex[u] >= 0) v2.push_back(nex[u]);
delx(u);
}
v.clear();
las = -1;
for (auto u : v2) {
if (del[u]) continue;
if (a[u] == las) continue;
v.push_back(u);
las = a[u];
}
v2.clear();
}
if (cn & 1) cout << "Alice\n";
else cout << "Bob\n";
}
}
Editorialist's code (C++)
// #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<int> a(n);
for (int &x : a) cin >> x;
vector<priority_queue<int>> pq(n);
set<array<int, 2>> bests;
auto extend = [&] (int oldid, int newid, int len) {
bests.erase({len, oldid});
if (pq[newid].size()) bests.erase({pq[newid].top(), newid});
pq[oldid].pop();
pq[newid].push(len+1);
bests.insert({pq[newid].top(), newid});
if (pq[oldid].size()) bests.insert({pq[oldid].top(), oldid});
};
for (auto x : a) {
--x;
if (bests.empty() or (bests.size() == 1 and (*bests.begin())[1] == x)) {
pq[x].push(1);
if (pq[x].size() == 1) bests.insert({1, x});
}
else {
auto [l1, c1] = *bests.rbegin();
if (c1 != x) extend(c1, x, l1);
else {
auto [l2, c2] = *next(rbegin(bests));
extend(c2, x, l2);
}
}
}
int ans = 0;
for (auto x : pq) ans += x.size();
if (ans%2 == 0) cout << "Bob\n";
else cout << "Alice\n";
}
}