PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Testers: Utkarsh Gupta, Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
1975
PREREQUISITES:
Prefix sums
PROBLEM:
An array is said to be good if no subarray has a xor of 0.
Given an array A, in one move you can replace one of its elements with any non-negative integer. Find the minimum number of moves to make A good.
EXPLANATION:
Let P_i = A_1 \oplus A_2 \oplus \ldots \oplus A_i denote the prefix xor of array A, with P_0 = 0.
Note that a subarray [L, R] can have a xor of zero if and only if P_R \oplus P_{L-1} = 0, i.e, P_R = P_{L-1}.
So, an array A is good if and only if all its prefix sums are distinct.
Now look at what our given operation does to the prefix sums: changing the element A_i changes exactly all the prefix sums P_i, P_{i+1}, \ldots, P_N.
In particular, suppose we set A_i \gets x. Let y = A_i \oplus x. Then, each P_j for j \geq i becomes (P_j \oplus y).
This allows us to ‘fix’ the array from left to right, as follows:
- Let S be the set of current prefix sums. Initially, S = \{0\}.
- Iterate i from 1 to N.
- If P_i is not in S, insert it to S and continue.
- if P_i is in S, we have no choice but to perform an operation. We might as well perform this operation on position i. By choosing a large enough value of x and setting A_i \gets x, we can ensure the following:
- P_i is no longer in S
- For any j \geq i and k \lt i, it is impossible for P_j = P_k to ever happen.
- In other words, we can essentially just pretend we are starting from an entirely new array. The current set S is useless to us, so we can simply clear it.
- Note that S should now contain something denoting the ‘empty’ prefix (recall that we initially had S = \{0\} for this purpose). There are a couple of ways of achieving this:
- If the values of P_i were calculated in advance, insert P_{i-1} into S (the editorialist’s code does this).
- Otherwise, notice that the values of P_i can actually be calculated on-the-go. If this is how you to choose to implement it, simply reset the current prefix sum to 0 and insert 0 into S to simulate starting from a new array (the setter’s code does this).
TIME COMPLEXITY
\mathcal{O}(N) or \mathcal{O}(N\log N) per test case, depending on implementation.
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;
void solve()
{
int n = readIntLn(1, 1e5);
sumN += n;
vector<int> a = readVectorInt(n, 0, (1 << 30) - 1);
set<int> prefxor{0};
int ans = 0, cur = 0;
for(int &x: a)
{
cur ^= x;
if(prefxor.count(cur))
{
ans++;
prefxor.clear();
cur = 0;
prefxor.insert(0);
}
else
{
prefxor.insert(cur);
}
}
cout << ans << endl;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = readIntLn(1, 1e5);
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
readEOF();
assert(sumN <= 3e5);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
p = {0}
ans = 0
pref = 0
for x in a:
pref ^= x
if pref in p:
ans += 1
pref = x
p = {x}
else:
p.add(pref)
print(ans)