 # SUBARRAYGAME - Editorial

Author: Jeevan Jyot Singh
Testers: Jeevan Jyot Singh, Hriday
Editorialist: Nishank Suresh

2699

# PREREQUISITES:

Observation, the Sprague-Grundy Theorem and Nim

# PROBLEM:

You have an array A of distinct integers. Define its goodness to be \sum_{i=2}^N |A_i - A_{i-1}|.

Alice and Bob alternate moves, each player on their turn deleting a non-empty subarray from A that doesn’t change its goodness. Under optimal play, who wins?

# EXPLANATION:

There is a single important observation that allows for a solution to this problem:

Suppose a player deletes a subarray [L, R]. This doesn’t change the goodness of A if and only if:

• A_{L-1} \lt A_L \lt A_{L+1} \lt \ldots \lt A_R \lt A_{R+1}, or
• A_{L-1} \gt A_L \gt A_{L+1} \gt \ldots \gt A_R \gt A_{R+1}

That is, the subarray [L-1, R+1] must be either increasing or decreasing. In particular, L \geq 2 and R \leq N-1 must also hold.

Proof

It is easy to see that deleting a subarray of the above form doesn’t change the goodness of the array — both before and after deleting, the contribution of the [L-1, R+1] section is |A_{L-1}-A_{R+1}|, and the contribution of indices before L-1 and after R+1 isn’t affected in any way.

It is also easy to see that deleting a subarray with L = 1 or R = N always reduces the goodness: some existing pairs stop contributing, and no new pairs contribute.

Now, consider a subarray [L, R] such that [L-1, R+1] is not sorted. Without loss of generality, let A_{L-1} \lt A_{R+1}.
Since the subarray is not sorted, there exists an index i such that L \leq i \leq R+1 and A_i \lt A_{i-1}. Choose the first such index i.

Now,

• After deletion, this segment contributes A_{R+1} - A_{L-1} to the goodness, since those elements are now adjacent.
• Before deletion, the goodness was at least (A_{i-1} - A_{L-1}) + (A_{i-1} - A_i) + |A_{R+1} - A_i|
• If A_{R+1} \gt A_i, this is (A_{R+1}-A_{L-1}) + 2A_{i-1} - 2A_i, which is strictly larger than A_{R+1} - A_{L-1} since A_{i-1} \gt A_i.
• If A_{R+1} \lt A_i, this is 2A_{i-1} - A_{L-1} - A_{R+1}, which equals (A_{R+1}-A_{L-1}) + 2A_{i-1}-2A_{R+1}, which is once again strictly larger than A_{R+1} - A_{L-1}.

So, deleting such a subarray can never keep the goodness equal.

Now, note that the initial array A can be split into alternating increasing and decreasing subarrays of length \geq 2 that intersect only at their borders, and performing a deletion within each of these subarrays is independent because the borders cannot be deleted.

For example, A = [1, 5, 3, 2, 4] splits into [1, 5], [5, 3, 2], [2, 4].

Consider one such segment, of length x. In one move, a player can delete some contiguous elements from it: in particular, anywhere between 1 and x-2 elements can be deleted.

This is strikingly similar to the classical game of nim: indeed, this subarray corresponds to a nim pile of size x-2.
Our piles are independent, and so we can simply apply the solution to nim here:

• Find all the alternating increasing/decreasing subarrays as mentioned above. Let their lengths be x_1, x_2, \ldots, x_k.
• Then, we have nim piles of sizes x_1-2, x_2-2, \ldots, x_k-2.
• So, Bob wins if and only if (x_1-2)\oplus (x_2-2)\oplus \ldots \oplus (x_k-2) = 0, where \oplus denotes the bitwise xor operation.

Finding the maximal increasing/decreasing subarrays can be done in \mathcal{O}(N) in several ways, for example with two-pointers.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Setter's code (C++)
#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5;

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}

string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}

// -------------------- Input Checker End --------------------

int sumN = 0, Alice = 0, Bob = 0;

void solve()
{
int n = readIntLn(1, 1e5);
sumN += n;
vector<int> a = readVectorInt(n, 1, 1e9);
assert(sz(set<int>(a.begin(), a.end())) == n);
int ans = 0;
for(int i = 0; i + 1 < n; )
{
int cnt = 0;
if(a[i] < a[i + 1])
{
while(i + 1 < n and a[i] < a[i + 1])
i++, cnt++;
}
else
{
while(i + 1 < n and a[i] > a[i + 1])
i++, cnt++;
}
ans ^= (cnt - 1);
}
if(ans == 0)
cout << "Bob\n", Bob++;
else
cout << "Alice\n", Alice++;
}

int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = readIntLn(1, 1e5);
for(int tc = 1; tc <= T; tc++)
{
solve();
}
assert(sumN <= 5e5);
cerr << "Alice: " << Alice << endl;
cerr << "Bob: " << Bob << endl;
return 0;
}

Tester's code (C++)
/**
* the_hyp0cr1t3
* 30.08.2022 23:44:59
**/
#ifdef W
#include <k_II.h>
#else
#include <bits/stdc++.h>
using namespace std;
#endif

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}

string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}

// -------------------- Input Checker End --------------------

template<typename T>
T expo(T A, int64_t B, int MOD) {
T res{1}; while(B) {
if(B & 1) res = 1LL * res * A % MOD;
B >>= 1; A = 1LL * A * A % MOD;
} return res;
}

int main() {
#if __cplusplus > 201703L
namespace R = ranges;
#endif
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int sumN = 0;
int alice = 0, bob = 0;

int tests = readIntLn(1, 100000);
while(tests--) [&] {
int n = readIntLn(1, 100000);
auto a = readVectorInt(n, 1, 1e9);
sumN += n;
assert(set<int>(a.begin(), a.end()).size() == n);

int sum = 0, prv = 0;
for(int i = 1; i < n; i++)
if(a[i - 1] < a[i] and (i + 1 == n or a[i] > a[i + 1])
or a[i - 1] > a[i] and (i + 1 == n or a[i] < a[i + 1]))
sum ^= i - exchange(prv, i) - 1;

cout << (sum? (alice++, "alICe") : (bob++, "bOB")) << '\n';
}();

assert(sumN <= 1000000);

cerr << "sum N: " << sumN << '\n';
cerr << "alice: " << alice << '\n';
cerr << "bob: " << bob << '\n';

#ifndef W
#endif
} // ~W

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
gnum, L, len = 0, 1, 0

for i in range(2, n):
if (a[i] < a[i-1]) == (a[L] < a[L-1]):
len += 1
else:
gnum ^= len
len = 0
L = i
gnum ^= len
print('bob' if gnum == 0 else 'alice')

2 Likes

Can you tell me how to identify a game theory problem which can be solved by nim