PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Counting inversions
PROBLEM:
Alice and Bob play a game on an array consisting of the integers +1 and -1 only.
Alice, on her turn, chooses a subarray with non-negative sum and deletes it.
Bob, on his turn, chooses a subarray with non-positive sum and deletes it.
Whoever cannot make a move wins.
Find the number of first moves for Alice that are winning.
EXPLANATION:
Let’s understand exactly when Alice can win.
Observe that any non-empty subarray with non-negative sum must contain at least one occurrence of 1; since it’s not possible to obtain a non-negative sum using only -1's.
So, if the array doesn’t contain any occurrences of 1 at all on Alice’s turn, she immediately wins.
However, as long as the array contains a 1, Alice will definitely be able to make a move (for example by choosing a single 1), so the game continues.
Thus, Alice’s goal is to remove all occurrences of 1 from the array.
Similar reasoning holds for Bob: on his turn, if there are no occurrences of -1, he wins immediately; otherwise he can always play.
So, his objective is to remove all occurrences of -1 from the array.
Now, Alice and Bob do have to be careful - if Alice removes all occurrences of 1 from the array, but while doing so also removes all -1's from the array, then Bob will win because he moves after her and can’t move.
So, each player’s goal is more precisely to remove all occurrences of their element, while keeping at least one occurrence of their opponent’s element remaining.
Knowing this, we can prove the following criterion:
Claim: Alice wins on the array A if and only if on her turn, either A_1 = -1 or A_N = -1.
Proof
This can be proved by explicitly giving a strategy.
Suppose A_1 = 1 and A_N = 1.
Then, there are two possibilities:
- Alice chooses the entire array A on her turn (if it’s possible).
In this case, Bob will receive the empty array, and can’t make a move so he wins.- Alice doesn’t choose the entire array A on her turn.
In this case, Bob will receive an array where at least one end has the element 1.In the second case, there are two possibilities for Bob:
- One end is 1 and one end is -1.
Here, Bob can delete all the -1's from whichever end has them (this is negative sum, which is a valid move for Bob).
Alice then receives a non-empty array with both ends being 1 again.- Both ends are 1.
Now, if there exists a -1 in the array, Bob can just delete any single occurrence of -1, and again Alice is left with a non-empty array with both ends 1.
If there are no -1's, Bob cannot move and wins anyway.So, if the initial ends are both 1, Alice cannot win.
Similar logic shows that if both ends are -1 on Bob’s turn, he cannot win.
Let’s go back to Alice’s turn now.
Suppose one end is 1 and one is -1.
She can then remove all the 1's from one end and give Bob an array with both ends -1, thus putting him in a losing position.Suppose both ends are -1.
Then, if there are no 1's, Alice wins immediately; otherwise she can delete any one of them and give Bob a losing array.This proves our claim.
A similar condition holds for Bob: he wins if and only if on his turn, at least one endpoint of the array is equal to 1.
Knowing the above, let’s analyze which moves can possibly winning for Alice.
Alice should perform a move that results in a losing state for Bob - meaning both endpoints must equal -1.
Suppose Alice chooses the move [L, R]. Then, note that if 1 \lt L and R \lt N, the endpoints of the array don’t actually change.
Or, the other way around - there only about 2N moves that can change the endpoints of the array at all (those being each non-empty prefix and each non-empty suffix).
Each prefix and suffix can be checked in constant time each: check if it has non-negative sum; and if after deleting it the resulting array has both endpoints -1, it’s a valid winning move for Alice.
As for subarrays that are neither prefix nor suffix: they don’t change the endpoints, so,
- If A_1 = 1 or A_N = 1, none of these moves will ever be valid.
- If A_1 = A_N = -1, all of these moves will be valid.
So, we only need to care about the second case; and there we simply want to count the number of internal subarrays with non-negative sum, since they’re all valid!
All that remains is counting the number of pairs (L, R) such that 1 \lt L \le R \lt N and
A_L + A_{L+1} + \ldots + A_R \ge 0.
This is a fairly standard problem, and can be solved with prefix sums and a bit of data structure usage.
That is, define P_i = A_1 + A_2 + \ldots + A_i to be the i-th prefix sum of A; and then note that the sum of subarray [L, R] is P_R - P_{L-1} so we’re really just looking for pairs (L, R) with P_R \ge P_{L-1}.
This is essentially just the problem of counting inversions (or rather, non-inversions) in an array, which has several solutions.
For example, one solution is to maintain an array B such that B_x is the number of indices seen so far with P_i = x.
Initialize B to all zeros, except for B_{P_1} = 1. Then, for each i = 2, 3, \ldots, N-1:
- Let x = P_i.
- Add B_{x} + B_{x-1} + B_{x-2} + \ldots to the answer.
- Then, add 1 to B_x so that it gets counted for future indices.
To do this quickly, we need a data structure that supports point addition and range updates, which a segment tree/fenwick tree can do.
There are also solutions that require no data structures: for example it’s possible to adapt mergesort to also count the number of inversions by adding appropriate counts during each merging process.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Tester's code (C++, Fenwick)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct FenwickTree{
int n;
vector <int> f;
vector <int> b;
inline void add(int i, int x){
b[i] += x;
for (int j = i; j <= n; j += j & (-j)){
f[j] += x;
}
}
inline void modify(int i, int x){
add(i, x - b[i]);
}
inline void init(int nn, vector <int> a){
n = nn;
if (a.size() == n){
vector <int> a2;
a2.push_back(0);
for (auto x : a) a2.push_back(x);
a = a2;
}
f.resize(n + 1);
b.resize(n + 1);
for (int i = 0; i <= n; i++) f[i] = 0, b[i] = 0;
for (int i = 1; i <= n; i++){
modify(i, a[i]);
}
}
inline int query(int x){
int ans = 0;
for (int i = x; i; i -= i & (-i)){
ans += f[i];
}
return ans;
}
inline int query(int l, int r){
return query(r) - query(l - 1);
}
};
void Solve()
{
int n; cin >> n;
vector <int> a(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
int ans = 0;
{
int S = 0;
for (int i = 1; i < n; i++){
S += a[i];
if (S >= 0 && a[i + 1] == -1 && a[n] == -1) ans++;
}
}
{
int S = 0;
for (int i = n; i > 1; i--){
S += a[i];
if (S >= 0 && a[1] == -1 && a[i - 1] == -1) ans++;
}
}
if (a[1] == -1 && a[n] == -1){
vector <int> p(n + 1);
for (int i = 1; i <= n; i++){
p[i] = p[i - 1] + a[i];
}
FenwickTree fen;
vector <int> vv(2 * n + 1);
fen.init(2 * n + 1, vv);
for (int i = 2; i < n; i++){
fen.add(p[i - 1] + n + 1, 1);
ans += fen.query(1, p[i] + n + 1);
}
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (C++, divide and conquer)
// #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;
if (a[0] == 1 and a[n-1] == 1) {
cout << 0 << '\n';
continue;
}
// Need to give Bob (-1, -1)
ll ans = 0;
// Prefix
{
int sm = 0;
for (int i = 0; i+1 < n; ++i) {
sm += a[i];
if (sm >= 0 and a[n-1] == -1 and a[i+1] == -1) ++ans;
}
}
// Suffix
{
int sm = 0;
for (int i = n-1; i > 0; --i) {
sm += a[i];
if (sm >= 0 and a[0] == -1 and a[i-1] == -1) ++ans;
}
}
// Between
// Ends don't change -> either everything is valid or nothing is valid
if (a[0] == -1 and a[n-1] == -1) {
// number of subarrays with positive sum in the middle
vector<int> p = {0};
for (int i = 1; i+1 < n; ++i) {
p.push_back(p.back() + a[i]);
}
auto calc = [&] (const auto &self, int L, int R) -> void {
// count non-inversions in [L, R]
if (L >= R) return;
int M = (L+R)/2;
self(self, L, M);
self(self, M+1, R);
vector<int> vals;
for (int i = L; i <= M; ++i) vals.push_back(p[i]);
ranges::sort(vals);
for (int i = M+1; i <= R; ++i) {
ans += ranges::upper_bound(vals, p[i]) - begin(vals);
}
};
calc(calc, 0, size(p)-1);
}
cout << ans << '\n';
}
}