OPERATION - Editorial

PROBLEM LINK:

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

Author: wuhudsm
Testers: iceknight1093, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

2870

PREREQUISITES:

Tries

PROBLEM:

You have an array A. Process Q independent queries of the following type:

  • Given u and x, set A_u = x. Then, compute the maximum possible value of
((A_1 \oplus \ldots \oplus A_i) \mid (A_{i+1} \oplus \ldots \oplus A_N)) - ((A_1 \oplus \ldots \oplus A_i) \&(\neg (A_{i+1} \oplus \ldots \oplus A_N)))

across all 1 \leq i \lt N.

EXPLANATION:

The given expression is a bit weird, so let’s try to simplify it a bit.
For a fixed i, let x = A_1 \oplus \ldots \oplus A_i and y = A_{i+1} \oplus \ldots \oplus A_N.

Our expression is (x\mid y) - (x \&\neg y). This simply equals y.

Proof

First, it’s clear that (x \& \neg y) is a submask of x\mid y (since it’s a submask of x), so the subtraction operation is really just bitwise xor.
Now that we have a bunch of bitwise operations, we can look at bits one by one; in other words it’s enough to look at what happens when x and y take the values 0 and 1.

Simple case analysis tells us that:

  • x = 0 and y = 0 evaluates to 0
  • x = 0 and y = 1 evaluates to 1
  • x = 1 and y = 0 evaluates to 0
  • x = 1 and y = 1 evaluates to 1

You’ll notice the result is simply y.

So, the answer for a fixed array is the maximum value of A_{i+1} \oplus \ldots \oplus A_N across all 1 \leq i \lt N, i.e, the maximum suffix xor of the array (except A_1 \oplus \ldots \oplus A_N).
That is, if B_i = A_i \oplus \ldots \oplus A_N, then the answer is \max(B_2, B_3, \ldots, B_N).

Processing updates

Now we need to process updates on A. Let’s see how setting A_u := x changes the answer.
Suppose y is the original value of A_u. Then,

  • For any i \gt u, B_i remains unchanged.
  • For every i \leq u, B_i changes to B_i \oplus x \oplus y
    • In particular, if we set k = x \oplus y, then B_i changes to B_i \oplus k.

So, the answer is the maximum of two quantities:

  • \max(B_{u+1}, B_{u+2}, \ldots, B_N)
    • This is simply a suffix maximum of the B array and can be precomputed.
  • \max(B_2\oplus k, B_3\oplus k, \ldots, B_u\oplus k)

Computing the second part is a rather standard exercise using tries (if you don’t know what these are, a tutorial is linked at the start), and can be done in \mathcal{O}(b) where b is the number of bits in the numbers we’re dealing with (here, b = 30).

However, this requires us to insert B_2, \ldots, B_u into the trie and nothing else, and u changes every query. Continually erasing and reinserting elements would obviously be too expensive.

The simplest way to overcome this is to solve the queries offline.

That is, read all the queries, then we’ll process them in increasing order of u.
Let T be a trie, initially empty. Iterate over u from 2 to N.
When at a position u,

  • Insert B_u into T
  • Then, for each query (u, x), query the trie for the maximum value when xor-ed with y\oplus A_u.

This gives us a solution in \mathcal{O}((N+Q)\cdot b), where b = 30 for this task.

TIME COMPLEXITY:

\mathcal{O}((N+Q)\cdot b) per testcase.

CODE:

Setter's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int n,q;
int a[N],XOR[N],MX[N],ans[N];
vector<pair<int,int> >query[N];

struct nod
{
	nod *ch[2];
};

struct Trie
{
	nod *root;
	
	Trie()
	{
		root=NULL;
	}
	
	void newnod(nod **p)
	{
		*p=new nod;
		(*p)->ch[0]=(*p)->ch[1]=NULL;
	}
	
	void insert(int x)
	{
		_insert(&root,x,29);
	}
	
	void _insert(nod **p,int x,int b)
	{
		if(*p==NULL) newnod(p);
		if(b==-1) return ;
		_insert(&(*p)->ch[(x&(1<<b))!=0],x,b-1);
	}
	
	int getmx(int x)
	{
		return _getmx(root,x,29,0);
	}
	
	int _getmx(nod *p,int x,int b,int cur)
	{
		if(b==-1) return cur;
		int t=(x&(1<<b))!=0;
		if(p->ch[t^1]) return _getmx(p->ch[t^1],x,b-1,cur+(1<<b));
		else           return _getmx(p->ch[t],x,b-1,cur);
	}
};

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=n;i;i--)    XOR[i]=XOR[i+1]^a[i],MX[i]=max(XOR[i],MX[i+1]);
	for(int i=1;i<=q;i++)
	{
		int p,x;
		scanf("%d%d",&p,&x);
		ans[i]=MX[p+1];
		query[p-1].push_back(make_pair(XOR[1]^a[p]^x,i));
	}
	int  t=0;
	Trie T;
	for(int i=1;i<n;i++)
	{
		t^=a[i];
		T.insert(t);
		for(int j=0;j<query[i].size();j++)
		{
			int x=query[i][j].first,id=query[i][j].second;
			ans[id]=max(ans[id],T.getmx(x));
		}
	}
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	
	return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

struct Trie {
	vector<int> v;
	vector<array<int, 2>> ch;
	int id = 0;
	Trie() : v(1, 0), ch(1, {-1, -1}) {}
	void create() {
		v.push_back(0);
		ch.push_back({-1, -1});
		++id;
	}
	void add(int x) {
		int node = 0;
		for (int bit = 30; bit >= 0; --bit) {
			int b = (x >> bit) & 1;
			++v[node];
			if (ch[node][b] == -1) {
				create();
				ch[node][b] = id;
			}
			node = ch[node][b];
		}
		++v[node];
	}
	int query (int x) { // Maximum value of a^x for a in the trie
		int node = 0, ret = 0;
		for (int bit = 30; bit >= 0; --bit) {
			int b = (x >> bit) & 1;
			if (ch[node][b^1] == -1) node = ch[node][b];
			else {
				ret += 1 << bit;
				node = ch[node][b^1];
			}
		}
		return ret;
	}
};

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	
	int n, q; cin >> n >> q;
	vector<int> a(n);
	for (int &x : a) cin >> x;
	vector<int> suf(n), sufmax(n+1);
	for (int i = n-1; i >= 0; --i) {
		suf[i] = a[i];
		if (i < n-1) suf[i] ^= suf[i+1];
		sufmax[i] = suf[i];
		if (i < n-1) sufmax[i] = max(sufmax[i], sufmax[i+1]);
	}

	vector<vector<array<int, 2>>> queries(n);
	vector<int> ans(q);
	for (int i = 0; i < q; ++i) {
		int pos, val; cin >> pos >> val;
		queries[--pos].push_back({val, i});
		ans[i] = sufmax[pos+1];
	}

	Trie T;

	for (int i = 1; i < n; ++i) {
		T.add(suf[i]);
		for (auto [val, id] : queries[i]) {
			ans[id] = max(ans[id], T.query(val ^ a[i]));
		}
	}
	for (auto x : ans) cout << x << '\n';
}
2 Likes

A very nice solution. Codechef problems are :heavy_heart_exclamation: ,they usually set some very nice adhocish algorithmic problems. Waiting for next starters :slight_smile:

1 Like

I solved the queries online. While inserting in trie a node in the trie , I kept track of the min and max index of the suffix that was the source of insertion for this node.

Then while checking of each queries, I also considered only those nodes in the trie who has their min index <= x.

Here is the accepted solution link CodeChef | Competitive Programming | Participate & Learn
A very nice problem (took me total 2-3h in thinking, implementing, debugging), couldn’t solve it in contest .
@iceknight1093 your editorials are always super lit :fire: .
They are always of very very high quality. You include proofs, detailed explanations and hints as well. Never seen so great editorials in codeforces even.

4 Likes