You are not logged in. Please login at www.codechef.com 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, 14:01

ay2306's gravatar image

3★ay2306
1929
accept rate: 13%

edited 14 Jun, 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).

link

answered 14 Jun, 14:16

admin's gravatar image

0★admin ♦♦
19.6k349497539
accept rate: 35%

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

(14 Jun, 14:33) l_returns5★
1

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

(14 Jun, 14:34) vijju123 ♦5★
1

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

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

@admin _/\_

(14 Jun, 14:51) vijju123 ♦5★

That's really nice :)

(14 Jun, 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, 16:24) ay23063★
showing 5 of 6 show all
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:

×1,632
×612
×294
×134

question asked: 14 Jun, 14:01

question was seen: 111 times

last updated: 14 Jun, 16:24