PROBLEM LINK:Author: Hasan Jaddouh Difficulty:Mediumhard Prerequisites:Gaussianelimination, 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 subsequence 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 XORSay 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=X_{1} xor X_{2} ... X_{k}; where X_{i} is element of S) now we have 2 cases: 1 B is not an element of sequence X_{i}, then X is obviously element of L(S') because all X_{i} are present in S' 2 B is an element of sequence X_{i}, then we can write X as xor of subset of S' by removing B from sequence X_{i} and adding both A and A xor B to sequence X_{i} 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 10^{9} 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 ith 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
Supporting Deleting latestadded elementwe 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 stacksWe 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:
supporting deleting earliestadded element from the sequenceWe can implement similar trick by using two stacks of sequences to make a queue of sequences, thus we can delete earliestadded 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 solutionnow 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 earliestadded element from queue time complexity is O(log(10^{9})) 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(log^{2}(10^{9})), so overall complexity is O(N log^{2}(10^{9})) Author's and Tester's Solutions:
This question is marked "community wiki".
asked 19 Feb '17, 17:13

The links to setter's and testers's solution are broken please fix them. answered 20 Feb '17, 03:28

Hi @kingofnumbers , would you mind explaining this part please:
Consider arr[I] to be 13, i.e 1101 and x to be 4 i.e 0100. The MSB of x is 1 in arr[I] in this case. But if you did a XOR, you would get 9 i.e. 1001, which is not lesser than x .i.e 4. So, am I missing something? If yes, what is it? Thanks answered 11 Mar '17, 18:06
it's the other way around: "it's true when index of MSB of arr[i] is 1 in x" it's fixed, thanks.
(14 Mar '17, 17:12)

Hey can someone please explain what is being talked about after the 2 lemmas. I have understood till there. But am not able to figure out what the author wants to say after that. Also, if you could help me understand the time complexity along with the algo explanation, it would be really helpful. answered 13 Mar '17, 10:57
