You are not logged in. Please login at www.codechef.com to post your questions!

×

MIXFLVOR - Editorial

3
2

PROBLEM LINK:

Contest
Practice

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))

Author's and Tester's Solutions:

Setter
Tester

This question is marked "community wiki".

asked 19 Feb '17, 17:13

kingofnumbers's gravatar image

6★kingofnumbers ♦
194824
accept rate: 12%

edited 14 Mar '17, 18:26


The links to setter's and testers's solution are broken please fix them.

link

answered 20 Feb '17, 03:28

only4's gravatar image

4★only4
1.5k212
accept rate: 17%

it's fixed now.

(20 Feb '17, 12:39) kingofnumbers ♦6★

Hi!

There is a another solution using dynamic connectivity (something similar to segment tree) and Gaussian emulation.

Code.

link

answered 20 Feb '17, 16:50

arpa's gravatar image

6★arpa
4927
accept rate: 0%

What's the complexity of it?

(20 Feb '17, 17:38) kingofnumbers ♦6★

Hi @kingofnumbers , would you mind explaining this part please:

 if( (arr[i]^x)< x) // it's true when index of MSB of x is 1 in  arr[i]
         x=arr[i]^x;

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

link

answered 11 Mar '17, 18:06

gonecase's gravatar image

0★gonecase
187112
accept rate: 0%

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) kingofnumbers ♦6★

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.

link

answered 13 Mar '17, 10:57

gonecase's gravatar image

0★gonecase
187112
accept rate: 0%

What exactly you didn't understand?

(14 Mar '17, 17:13) kingofnumbers ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,302
×98
×84
×65
×26

question asked: 19 Feb '17, 17:13

question was seen: 1,432 times

last updated: 14 Mar '17, 18:26