approach for BEERUS

help
bit
mst
quco2018

#1

Can anyone discuss their approach for this problem
from this contest


#2

The only catch in the problem was that (node(i) OR node(j)) + (node(i) AND node(j)) = node(i) + node(j).The rest is easy to figure out.


#3

From this I see that MST is a star with center in lightweight node.
And weight MST = Sum{node_i} + (n-2)*node_0, node_0 - is lightweight node.
Sum {node_i} - easy to get.
But how to get weight of lightweight node?


#4

If you have \displaystyle\sum_{i}^{} node_i it should be straightforward to obtain the weights for each node.
node_i = \frac{1}{n} * \left( gohan* + trunks* - \displaystyle\sum_{i}^{} node_i\right). Now just loop over all nodes and obtain the maximum.


#5

Can you tell me where did you learn this property that
A|B + A&B = A + B