Need help with BEERUS

general
, , ,
1

I attempted [BEERUS][1] with this approach, please tell me if this approach is wrong and how should i attempt it.

Using the property A|B + A&B = A+B , I store the sum of input array elements into array t;

Now each element of t is t[i] = (\sum_{i=1}^{n} node_i) + n.node_i

Thus at sum = \sum_i^n t_i = n(\sum_{i=1}^{n} node_i)+ n(node_1 + node_2 + ... ) = 2n(\sum_{i=1}^{n} node_i)

Therefore (\sum_{i=1}^{n} node_i) = sum/2n

Which makes node_i = (t[i]-sum/2n)/n

Now we have to find the maximum spanning tree. Since the weight of an edge is A&B + A|B = A+B

Therefore maximum path will be to go max(node)->secondmax(node) and so on

Hence I found of maximum spanning tree to be (2\sum_i^nnode_i) - min(node) - max(node)

Thank you
[1]: https://www.codechef.com/problems/BEERUS

2

Everything is fine except the last assertion about the max spanning tree. The maximum spanning tree will be kind of a star tree in which we keep the root with the maximum value attached to all the other nodes. Hence, the weight of the max spanning tree would be the sum of all nodes (except the highest value node) + (n - 1) * (the highest value of a node).

3 Likes
3

Wow… didn’t knew admin also replies answers about solutions xD

4

Some mod once requested her to be more active on the forum :3

1 Like
5

Yes, I replied to this, because I was a tester in this contest :slight_smile:

1 Like
6

@admin _/\_

7

That’s really nice :slight_smile:

8

@admin thanks for the answer. But can you help me in stating why it is in star form? I don’t have that much experience. Can you tell me theory to look for or something like that?