PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Testers: Tejas Pandey, Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have a boolean array A. In one move, you can choose any subarray of A with length at least 2, add its bitwise XOR to your score, and delete this subarray from A.
Find the maximum possible score you can achieve.
EXPLANATION:
Since the array is boolean, each move increases our score by either zero or one.
Note that making a move that increases our score by zero is pointless, so we really want to count the maximum number of 1 moves that we can make.
Let’s call a subarray with xor 1 a good subarray.
Further, it’s better to use shorter subarrays if possible, since that gives us more freedom in the future. The shortest possible good subarrays we can choose are [0, 1] and [1, 0], so let’s keep choosing these as long as its possible to do so.
Suppose we can’t choose any more subarrays of this kind. Then, every element of A must be the same, i.e, A consists of all 0's or all 1's.
- In the first case, all 0's, nothing more can be done, since any remaining subarray has xor 0.
- In the second case, we still have good subarrays: anything with odd length is good, i.e, [1, 1, 1], [1, 1, 1, 1, 1], \ldots
- Suppose the length of A is now K. Then, the best we can do is \lfloor \frac{K}{3} \rfloor subarrays, each of the form [1, 1, 1]. So, add this value to the answer.
This gives us the final solution:
- While the array contains both 0's and 1's, remove one 0 and one 1 from it, and increase the answer by 1
- When the array contains only a single type of character, if it’s 1 and there are K of them, add \lfloor \frac{K}{3} \rfloor to the answer.
This can be done in \mathcal{O}(1) by knowing the counts of 0's and 1's, although simulation in \mathcal{O}(N) will still pass.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++, formula)
#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>;
// -------------------- 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);
int cnt0 = count(a.begin(), a.end(), 0);
int cnt1 = count(a.begin(), a.end(), 1);
int take = min(cnt0, cnt1);
int ans = take;
cnt0 -= take, cnt1 -= take;
ans += cnt1 / 3;
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();
}
assert(sumN <= 2e5);
readEOF();
return 0;
}
Editorialist's code (Python, simulation)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
cur = []
ans = 0
for x in a:
if len(cur) == 0 or x == cur[-1]: cur.append(x)
else:
ans += 1
cur.pop()
if len(cur) > 0 and cur[0] == 1:
ans += len(cur)//3
print(ans)
. I think that made it O(n²) instead of linear?