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


Need help with BEERUS

I attempted BEERUS 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

asked 14 Jun '18, 14:01

ay2306's gravatar image

accept rate: 11%

edited 14 Jun '18, 14:10

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


answered 14 Jun '18, 14:16

admin's gravatar image

0★admin ♦♦
accept rate: 35%

Wow.. didn't knew admin also replies answers about solutions xD

(14 Jun '18, 14:33) l_returns5★

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

(14 Jun '18, 14:34) vijju123 ♦♦4★

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

(14 Jun '18, 14:50) admin ♦♦0★

@admin _/\_

(14 Jun '18, 14:51) vijju123 ♦♦4★

That's really nice :)

(14 Jun '18, 14:53) l_returns5★

@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?

(14 Jun '18, 16:24) ay23064★
showing 5 of 6 show all
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 14 Jun '18, 14:01

question was seen: 120 times

last updated: 14 Jun '18, 16:24