PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: maximus11
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Sets
PROBLEM:
You’re given a binary array A.
Define
f(A) = \left( \left( \left( \left(A_1 \& A_2 \right) \mid A_3 \right) \& A_4 \right) \mid \ldots \right)
You’re given Q point updates to the array. After each one, compute f(A).
EXPLANATION:
Note that f(A) is computed in a rather iterative manner: the result of the first two elements is combined with the third, that result is combined with the fourth, and so on.
Let’s define f_i(A) to be the result of the operation on the first i elements; with f_1(A) = A_1.
Our aim is to compute f_N(A), and we have for i \gt 1:
f_i(A) = \begin{cases}
f_{i-1}(A) \ \mid\ A_i &, \text{if } i \text{ is odd} \\
f_{i-1}(A) \ \&\ A_i &, \text{if } i \text{ is even}
\end{cases}
Now, observe that when i is odd:
- If A_i = 1, the value of f_{i-1}(A) doesn’t matter at all: since the operation is bitwise OR, the result will always be 1 anyway.
- On the other hand, if A_i = 0, we’ll simply have f_i(A) = f_{i-1}(A).
A similar situation occurs when i is even: if A_i = 0 then f_i(A) = 0 always; otherwise f_i(A) = f_{i-1}(A).
Let’s use this knowledge to try and compute f_N(A) “quickly”.
For now, suppose N is odd. Then,
- If A_N = 1, f(A) = 1 immediately and nothing more needs to be checked.
Otherwise, f_N(A) = f_{N-1}(A) and we need to solve the problem for the first N-1 elements, essentially.- So, we look at f_{N-1}(A) next.
- N-1 is even, so if A_{N-1} = 0 then the answer is immediately 0.
Otherwise, we must look at f_{N-2}(A). - N-2 is odd, so again if A_{N-2} = 1 the answer is 1; otherwise we look at N-3 and so on.
In general, note that if the sequence of values from the back is 0, 1, 0, 1, 0, \ldots we need to keep looking at the previous value to make our decision.
There are then two possibilities when moving backwards:
- We reach index 1.
Here, the answer is simply A_1, since f_1(A) = A_1 as noted in its definition. - We reach some index i such that A_i “breaks” the pattern: i.e. either i is odd but A_i = 1, or i is even but A_i = 0.
In this case, note that the answer is simply A_i itself.- This is because for such an index we’ll have f_i(A) = A_i, and we’re only at this index because for all j \gt i we have f_j(A) = f_{j-1}(A) in the first place; so f_N(A) = f_i(A) = A_i.
So, if we know the last position where the pattern breaks, the answer is trivial to output.
That means our focus should now be on finding this last position.
This is quite easy to do.
Let’s call an index bad if its current value doesn’t match its expected value with respect to the pattern, i.e., either i is odd but A_i = 1, or i is even but A_i = 0.
Let S be a set containing all the bad indices.
Then, for each query (i, x):
- Update the set S of bad elements. This is easy to do since only index i can get affected at all, so just check the condition for it.
- Then, there are two possibilities:
- S is empty, i.e. no index is bad. In this case the answer is simply A_1.
- S is not empty. Then, let m \in S be the largest bad index. The answer is A_m.
To maintain S, we need a data structure that can quickly insert/delete elements, and retrieve the maximum.
This can be done using std::set in C++, TreeSet in Java, and SortedList in Python.
Note that the above discussion assumed that N was odd, but the exact same solution applies to even N as well so we’re done.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
// __builtin_clz(x): the number of zeros at the beginning of the number
// __builtin_ctz(x): the number of zeros at the end of the number
// __builtin_popcountll(x): the number of ones in the number
// __builtin_parity(x): the parity (even or odd) of the number of ones
// __builtin_ffs(int) finds the index of the first (most right) set bit
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define nl "\n"
#define pb push_back
#define eb emplace_back
#define Sort(a) sort(a.begin(),a.end())
#define vi vector<int>
#define vll vector<long long>
#define F first
#define S second
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
int main()
{
// freopen("input00.txt","r",stdin);
// freopen("output00.txt","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// auto start = std::chrono::high_resolution_clock::now();
int T;
cin>>T;
while(T--)
{
int n; cin>>n;
vector<int>v(n);
for(int i = 0;i<n;i++)
{
cin>>v[i];
}
int q; cin>>q;
vector<set<int>>v1(1),v2(1);
// if(n%2 == 0)
// {
for(int i = n-1;i>=0;i--)
{
for(int j = 0;j<1;j++)
{
if(((1<<j)&v[i]) == 0 && i%2) v1[j].insert(i); // set bit
if(((1<<j)&v[i]) && i%2 == 0) v2[j].insert(i); //v1.end()<v2.end()
}
}
int ind,x;
for(int i = 0;i<q;i++)
{
cin>>ind>>x; ind--;
for(int j = 0;j<1;j++)
{
if(((1<<j)&v[ind]) == 0 && ind%2) v1[j].erase(ind); // set bit
if(((1<<j)&v[ind]) && ind%2 == 0) v2[j].erase(ind); //v1.end()<v2.end()
}
v[ind] = x;
for(int j = 0;j<1;j++)
{
if(((1<<j)&v[ind]) == 0 && ind%2) v1[j].insert(ind); // set bit
if(((1<<j)&v[ind]) && ind%2 == 0) v2[j].insert(ind); //v1.end()<v2.end()
}
ll ans = 0;
for(int j = 0;j<1;j++)
{
if(v2[j].size())
{
if((v1[j].size() && *--v2[j].end() > *--v1[j].end()) || v1[j].size() == 0)
ans += (1<<j);
}
}
cout<<ans<<endl;
}
}
// auto end = std::chrono::high_resolution_clock::now();
// std::cout << "Execution time: "
// << std::chrono::duration<double>(end - start).count()
// << " seconds." << std::endl;
return 0;
}
Tester's code (C++)
// Har Har Mahadev
#include<bits/stdc++.h>
using namespace std;
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
}inp;
long long smn = 0;
long long smq = 0;
void solve()
{
int n = inp.readInt(1,100000);
inp.readEoln();
vector<int> a(n);
for(int i = 0;i < n;i++){
a[i] = inp.readInt(0,1);
if(i == n-1)inp.readEoln();
else inp.readSpace();
}
int q = inp.readInt(1,100000);
inp.readEoln();
smn += n;
smq += q;
set<int> so,se;
for(int i = 1;i < n;i+=2){
so.insert(i);
}
for(int i = 0;i < n;i++){
if(a[i] == 0)continue;
if(i&1){
so.erase(i);
}
else{
se.insert(i);
}
}
for(int i = 0;i < q;i++){
int p,x;
p = inp.readInt(1,n);
inp.readSpace();
x = inp.readInt(0,1);
inp.readEoln();
p--;
a[p] = x;
if(p&1){
so.insert(p);
if(a[p])so.erase(p);
}
else{
se.erase(p);
if(a[p])se.insert(p);
}
if(se.size() == 0){
cout << 0 << "\n";
continue;
}
if(so.size() == 0){
cout << 1 << "\n";
continue;
}
auto it = se.end();
it--;
auto gt = so.end();
gt--;
int e = (*it);
int o = (*gt);
if(e > o)cout << 1 << '\n';
else cout << 0 << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;
// cin >> t;
t = inp.readInt(1,100'000);
inp.readEoln();
while(t--)
solve();
inp.readEof();
assert(smn <= 100'000);
assert(smq <= 100'000);
return 0;
}
Editorialist's code (C++)
// #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<int> a(n);
for (int &x : a) cin >> x;
set<int> s;
for (int i = 0; i < n; ++i) {
if (a[i] != i%2) s.insert(i);
}
s.insert(0);
int q; cin >> q;
while (q--) {
int i, x; cin >> i >> x; --i;
if (i) s.erase(i);
a[i] = x;
if (a[i] != i%2) s.insert(i);
int lst = *s.rbegin();
cout << a[lst] << '\n';
}
}
}
