SUBARRAYGAME - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

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

DIFFICULTY:

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();
    }
    readEOF();
    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
    readEOF();
#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