Maximum XOR of a Consecutive Block
Autumn Tournament (2013)
Submission name: xor.cpp
Problem summary
Choose exactly n consecutive integers lying inside the inclusive interval [a,b]. Find the largest possible bitwise XOR of the chosen block.
Input
Three natural numbers a b n.
Output
Print the maximum XOR value.
Constraints
a,b,n have at most 18 decimal digits; a<b; 1<n≤b−a+1.
Worked example
Official sample. The block 13,14,15,16,17,18 has XOR 31.
Input
10 20 6
Output
31
Solution analysis
- Let F(t)=0 XOR 1 XOR ... XOR t. Cancelling equal terms gives XOR(start..start+n−1)=F(start−1) XOR F(start+n−1). The prefix function repeats in four forms: F(t)=t,1,t+1,0 for t modulo 4 equal to 0,1,2,3 respectively.
- Set u=start−1, so a−1≤u≤b−n. Fix u modulo 4; only four cases exist. Both F(u) and F(u+n) are now either constants or expressions u+offset. For example u%4=0 makes F(u)=u; the other expression is selected from the residue of u+n.
- Optimize the XOR of those two expressions with a small bit DP, reading bits from least significant to most significant. Its state stores the addition carry for each expression and the comparison of the processed bits of u with the corresponding bits of the lower and upper bounds. A newly processed, more significant unequal bit overrides the previous comparison. This lets us enforce a numerical interval despite processing bits in reverse order.
- For each state, retain the largest XOR value among its partial choices: future transitions depend only on the carries and comparisons, so smaller values in the same state can never win. Fix the first two chosen bits to the selected residue. After processing 61 bits, accept only zero carries and lower≤u≤upper.
- In the sample, u=12 gives F(12)=12 and F(18)=19; 12 XOR 19=31. The four residue cases together consider every possible block start without iterating over the potentially enormous interval.
Why it works
The four residue classes partition all valid u values, and the periodic prefix-XOR identity rewrites each objective exactly. At every bit the carry transitions compute the true bits of both expressions. Comparison states describe the order of the processed lower-bit words, because their newest unequal bit is most significant. Keeping the maximum objective per state is valid since all future feasible completions depend only on that state. Accepted final states therefore represent exactly the permitted starts and the DP returns their maximum XOR.
Watch out. XOR is not ordinary addition. Use the block’s end start+n−1, and u’s upper bound b−n. The carries require least-significant-first processing, while interval comparisons must be updated by the newest unequal bit. Use 64-bit integers and enough leading zero bits to finish carries.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<iterator>
using namespace std;
using Integer=long long;
struct Expression{
bool variable;
Integer value; // Offset for u+value, or the constant itself.
};
Expression prefixExpression(int residue,Integer offset){
if(residue==0){
return {true,offset};
}
if(residue==1){
return {false,1};
}
if(residue==2){
return {true,offset+1};
}
return {false,0};
}
int comparison(int previous,int bit,int boundBit){
// State 0 means less, 1 equal, 2 greater.
return bit==boundBit?previous:(bit<boundBit?0:2);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
Integer a,b,n;
cin>>a>>b>>n;
Integer lower=a-1,upper=b-n,answer=0;
for(int residue=0;residue<4;residue++){
Expression first=prefixExpression(residue,0);
Expression second=prefixExpression((residue+n%4)%4,n);
Integer dp[2][2][3][3];
for(auto&p:dp){
for(auto&q:p){
for(auto&row:q){
fill(begin(row),end(row),-1);
}
}
}
dp[0][0][1][1]=0;
for(int position=0;position<=60;position++){
Integer next[2][2][3][3];
for(auto&p:next){
for(auto&q:p){
for(auto&row:q){
fill(begin(row),end(row),-1);
}
}
}
for(int carryA=0;carryA<2;carryA++){
for(int carryB=0;carryB<2;carryB++){
for(int low=0;low<3;low++){
for(int high=0;high<3;high++){
Integer score=dp[carryA][carryB][low][high];
if(score<0){
continue;
}
for(int bit=0;bit<2;bit++){
if(position<2&&bit!=((residue>>position)&1)){
continue;
}
int sumA=((first.value>>position)&1);
int sumB=((second.value>>position)&1);
if(first.variable){
sumA+=bit+carryA;
}
if(second.variable){
sumB+=bit+carryB;
}
int newLow=comparison(low,bit,(lower>>position)&1);
int newHigh=comparison(high,bit,(upper>>position)&1);
Integer candidate=score|(Integer((sumA^sumB)&1)<<position);
Integer&target=next[sumA>>1][sumB>>1][newLow][newHigh];
target=max(target,candidate);
}
}
}
}
}
for(int x=0;x<2;x++){
for(int y=0;y<2;y++){
for(int low=0;low<3;low++){
for(int high=0;high<3;high++){
dp[x][y][low][high]=next[x][y][low][high];
}
}
}
}
}
for(int low=1;low<3;low++){
for(int high=0;high<=1;high++){
answer=max(answer,dp[0][0][low][high]);
}
}
}
cout<<answer<<'\n';
}