2

There is a class of questions, that requires us to randomly select two elements from a given array, perform an operation on those elements, add the result to an "answer" and then drop any one of the elements and put the other element back in the array.

Most recently, I've come across this - Given an array, pick two elements a and b, add (a XOR b) to "answer". Then drop either a or b and put back the other in the array. Repeat these operations until there's only one element left in the array. What is the maximum value of "answer" that you can get (See Q here)

Sample I/O:-

arr = [3,2,1]

Output = 5;

Possible operations - 2 ^ 1 (= 3) -> Drop 2 -> 3 ^ 1 (= 2) -> Drop 3. Sum up 3+2=5 which is the final value of answer.

Now, given the question, I can write a recursion+backtracking code to handle this, but of course the time complexity is of the order of N!. I've been reading up on this, and it seems that it can be handled via Minimum/Maximum Spanning Tree. I don't understand why Maximum Spanning Tree works here at all. I put a comment on the question thread. Pasting part of comment below.

Running through a scenario - When following Prim's algorithm for MaxST, assume the first edge we choose is (A,B). Now the next edge we choose should be an edge that is attached to A or B and should have max weight. Let's say we choose (A,C). Similarly, now we need to choose an edge that is attached to A or B or C and have max weight. It could be an edge (B,D). Now in this circumstance, we have chosen (A,C) and (B,D) both to be parts of our MaxST. However, per the question, when we chose the first edge (A.B), we should have dropped either A or B from the array, meaning that once we chose (A,B) we can now either only choose (A,C) {i.e. drop B so can't choose (B,D) or any other edge connected to B in any step in the future} or choose (B,D) {i.e. drop A so can't choose (A,C) or any other edge connected to A in any step in the future}, but ideally can't choose both (A,C) and (B,D) Just to clarify, choosing any edge to be part of our MaxST means that we're taking the XOR of those two elements in the answer, i.e. if we choose an edge (A,B), it means that we're adding A^B to the answer (and hence must drop either A or B). Given the above, it doesn't make sense how MaxST works here. Could you please explain?

Improve this question

2 Answers 2

Reset to default
1

In order to see how you can use MST to solve these problems, you need to understand two things:

  1. Every valid sequence of pairs creates a spanning tree. You can prove this inductively, using:

    • before and after each selection, every remaining vertex is connected to a tree; and
    • for each tree, there is only one remaining vertex.

  2. For each spanning tree, there is a sequence of pairs that creates that tree. It's easy to construct this sequence by repeatedly choosing a leaf and its parent, and then dropping the leaf. When a parent's children are all dropped, the parent will become a leaf itself.

So for every sequence there is a spanning tree, and for every spanning tree there is a sequence. To solve the problem, find the maximum spanning tree, and then choose any sequence that creates it, following (2).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks a lot for your answer. I thought I understood it a few days ago, but just reading through it again, I'm not sure I understand the first point. Point #2 is crystal clear to me. Would you mind giving me an example please?
Say you have [1,2,3,4]. Each element is the root of a 1-element tree. Select 1-2 and drop 2. 1 and 2 are connected into a 2-element tree, only 1 remains available to select., leaving [1,3,4]. Select [3,4] and drop 3. 3 and 4 are connected into a 2 element tree, and only 4 remains available to select, leaving [1,4]. Finally select [1,4] and drop 1. The two 2-element trees are connected into a 4-element tree, with only [4] remaining to select. At all times, only the roots of trees are available for selection.
1

Don't consider the order of picking nodes in the MST. You can always rearrange the edges to meet the constraints of the question.

Consider a graph with nodes A, B, C, D, E. Let the edges in the MST be A-B, A-C, B-D, D-E. According to your scenario, either A or B should be dropped after picking A-B so that both don't get picked in later edges. However, if you rearrange the order of edges as D-E, B-D, A-B, A-C, you can see that this order can be used for picking elements from the array. Elements E, D, B, A, C get selected at each stage respectively.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.