PROBLEM LINK:
Author: Hasan Jaddouh
Testers: Kamil Debowski
Editorialist: Hasan Jaddouh
Difficulty:
Medium-hard
Prerequisites:
Gaussian-elimination, two pointers, two stacks trick
Problem Statement:
You are given a sequence of N elements, each element has a cost and a value, you want to buy a consecutive sub-sequence such that their total cost does not exceed K and and to maximize the XOR that you can get from subset of values of elements that you bought
Explanation:
We will start of discussing special cases some useful techniques then we will mix them together to provide the full solution for this problem.
Finding a subset of numbers that have maximum XOR
Say that we have a sequence of numbers of we want to pick a subset of them having maximum possible XOR.
Let L(S) be a set of all numbers that can be result of XOR of any subset of S including empty one, for example L({1, 5}) = {0, 1, 4, 5}
what want we want to find is maximum number of L(S) where S is the set of given numbers.
Lemma: Let S be a set of numbers and let S’ be a set of numbers that is resulted from picking two different numbers A and B from set S and replacing them with A and A xor B, we have L(S) = L(S’).
for example if S={4, 6, 7} one possibility of S’ is {4, 4 xor 6, 7}
proof: Let X be an element from L(S), let’s write X as the xor of elements of S, (i.e. X=X1 xor X2 … Xk; where Xi is element of S)
now we have 2 cases:
1- B is not an element of sequence Xi, then X is obviously element of L(S’) because all Xi are present in S’
2- B is an element of sequence Xi, then we can write X as xor of subset of S’ by removing B from sequence Xi and adding both A and A xor B to sequence Xi
so the above lemma tells us that we can apply this operations as many times as we want and we still have an equivalent sequence.
Lemma2: Let S be a set of numbers and S’ be a set of numbers resulted by removing 0 from S if it exists, then L(S) = L(S’)
proof: 0 is neutral in operation XOR
with those two lemmas we want to change our sequence into a sequence such that no two elements have same index of Most Significant Bit (MSB), we start by an empty set S and add the elements of given sequence one by one into this set Let’s say currently we want to add the number C but before we add it we make sure that no element V in the set have index of its MSB same as the number of want to add, if there’s one such element in the set then we xor C by V (i.e. C become equal to C xor V) then we check again until C becomes 0 in this case we don’t add it at all because of second lemma, or there’s no longer a number of the set S with same index of MSB as C then we add C into the set
now we have reduced our sequence into a sequence such that no two elements have same index of MSB, note that this sequence have at most 30 elements because all numbers are less than 109
after that we can greedily find maximum xor subset in this way:
We start with answer ANS=0 then we iterate over all indices i from 29 to 0, now if there’s an element X in our sequence with MSB index equal to i and i-th bit in ANS is 0, then we xor element X to the answer (i.e. ANS = ANS xor X), in the end of this process the answer is ANS
note with this solution it’s easy to support adding new elements to the sequence
You can see more details how to support adding new element to sequence and getting the max xor subset from setter’s code
struct Gauss{
int arr[31];
int len;
Gauss(){
len=0;
}
void add(int x){
for(int i=0;i<len;i++){
if( (arr[i]^x)< x) // it's true when index of MSB of arr[i] is 1 in x
x=arr[i]^x;
}
if(x!=0){
arr[len++]=x;
for(int i=len-1;i>0;i--){ // keep the list sorted in decreasing order, helpful to find the max
if(arr[i]>arr[i-1]){
swap(arr[i],arr[i-1]);
}
}
}
}
int getMax(){
int ret=0;
for(int i=0;i<len;i++){
if((ret^arr[i]) > ret){ // it's true when index of MSB of arr[i] is 0 in ret
ret= ret^arr[i];
}
}
return ret;
}
};
Supporting Deleting latest-added element
we can easily support adding new elements and deleting the element which is added most recently by using stack such that each element of the stack is the sequence of elements (remember each sequence is at most 30 elements)
whenever we want to add new elements we copy the sequence in top of stack and add to it the new element then we push it to the top of stack
whenever we want to delete the last added element we just pop the top element from the stack
trick: making a queue using two stacks
We can make a queue using two stacks in the following way:
one stack is header forward and the other is backward, so let’s name them forward and backward stacks
Whenever we want to add new element to queue we add it to top of forward stack
Whenever we want to pop earliest added element from queue we just pop the top element from backward stack, if backward stack is empty then we move all elements from forward stack to backward stack one by one, so their order will be reversed
here’s a code example:
struct queue{
stack<int> forward,backward;
void push(int x){
forward.push(x);
}
int pop(){
if(backward.empty()){
while(!forward.empty()){
backward.push(forward.top());
forward.pop();
}
}
if(backward.empty()){
cout<<"error: queue is empty";
return 0;
}
int ans=backward.top();
backward.pop();
return ans;
}
};
supporting deleting earliest-added element from the sequence
We can implement similar trick by using two stacks of sequences to make a queue of sequences, thus we can delete earliest-added element, whenever we want to find maximum answer we need to merge the top of the two stacks, since each of the top sequences has at most 30 numbers then we can simply add numbers of one sequence to another one by one
full solution
now we are ready to describe the full solution to this problem, we use two pointers to point on the current segment every time we increase the left pointer by one we try to increase right pointer until we can’t afford the next element then we get the maximum, increasing right pointer by one means we add new element to our queue, increasing left pointer by one means we are poping earliest-added element from queue
time complexity is O(log(109)) every time we increase right pointer by one and whenever we want to find maximum xor subset we need to merge tops of two stacks and this would be O(log2(109)), so overall complexity is O(N log2(109))