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

×

CENTREE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Alei Reyes
Primary Tester: Hussain Kara Fallah
Secondary Tester: Kacper Walentynowicz
Editorialist: Hussain Kara Fallah

DIFFICULTY:

Easy

PREREQUISITES:

Graph Theory

PROBLEM:

Construct a tree of N nodes such that the maximum distance between one of its centers and one of its centroids is exactly B.

A vertex u is a centroid if after removing u from the tree, the size of any of the resulting connected components is at most n/2.

Let f(x) be the greatest distance from u to any other vertex of the tree. A vertex u is a center if f(u) ≤ f(v) for any other vertex v.

EXPLANATION:

First of all let's create a tree consisting of a single node numbered 1 and assuming that it will be our centroid.

Now we should construct a chain consisting of B edges ending in a node representing our future center and this node is numbered B+1. Currently our tree is composed of a chain containing B+1 nodes. Currently node B+1 is not the center of our tree. So to make it our center we should extend this chain from this node by B extra nodes. Resulting a chain consisting of 2*B+1 node where the ith node and the (i+1)th node are connected by an edge for each 0 < i < 2*B+1

Now we assured that node B+1 is our center. And clearly node 1 is not our centroid. So we must make use of the remaining nodes and attach each one of them directly to node 1 (Each of them connected to 1 by a directed edge so we keep our center unchanged). Of course we must have enough nodes to ensure that. Removing node 1 would leave us with a subtree consisting of 2*B nodes, and subtrees made of single nodes (we attached).

As a conclusion we can say that for any N,B such that :

2*B ≤ N/2 -> 4*B ≤ N

A solution exists and can be constructed by this way. For cases where 4*B > N, constructing such a tree is impossible.

Of course we must handle this special case :

Case n = 2:

if B = 1 the tree made of 2 nodes connected by an edge is the solution, for other values of B the answer is NO

This image briefly describes the configuration of our tree: centree

AUTHOR'S AND TESTER'S SOLUTIONS:

AUTHOR's solution: Here
TESTER's solution: Here

This question is marked "community wiki".

asked 19 Jun '17, 07:10

deadwing97's gravatar image

3★deadwing97
1181134
accept rate: 0%

edited 20 Jun '17, 23:05

admin's gravatar image

0★admin ♦♦
19.8k350498541

Author and Tester solution links are invalid, please update

(19 Jun '17, 15:13) hikarico5★

I was damned on the n=2, b=0 case in which the answer must be "NO" and all other things were correct. Sad :(

link

answered 19 Jun '17, 16:42

agrocks23's gravatar image

2★agrocks23
31617
accept rate: 4%

Answer is hidden as author is suspended. Click here to view.

answered 19 Jun '17, 15:50

johnshow's gravatar image

0★johnshow
(suspended)
accept rate: 0%

Can someone please help me with definition of center of the tree?? I am unable to figure out exactly is the center. I assumed its the node from which distance to any other node is least. But that didnt fit.

Can someone give explain to me the center of tree, and in light of the definition, explain-

Currently node B+1 is not the center of our tree. So to make it our center we should extend this chain from this node by B extra nodes. Resulting a chain consisting of 2*B+1 node where the ith node and the (i+1)th node are connected by an edge for each 0 < i < 2*B+1
link

answered 19 Jun '17, 16:32

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

You can understand center of tree as:-

For each node find the largest distance from that node to any other node. So for each node you will get a number (largest distance from it).Now the node with the least of these numbers is the center.

In light to the above definition, it just states that for node B+1 to remain center, we have to extend the chain further from it as else maybe node B may become center and B+1 does not.

(19 Jun '17, 16:47) agrocks232★

Thanks bro!! Got it now :)

(19 Jun '17, 17:29) vijju123 ♦♦5★

I don't quite understand the n == 2 edge case. Why is the answer NO when b == 0? With an edge (1, 2), aren't each of the two nodes both centroids and centres?

link

answered 19 Jun '17, 17:16

bilalakil's gravatar image

3★bilalakil
32
accept rate: 0%

Yes, but B is defined as the maximum distance between a center and a centroid. Thus here it's 1 not zero.

(19 Jun '17, 17:20) deadwing973★

Ahh! The maximum distance! Of course...

Thank you for the direction :)

(19 Jun '17, 17:41) bilalakil3★

Why is the length of the largest chain considered to be 2B + 1 , and not 2(B+1)+1, as there will be an extra node which would be attached to the centroid.I mean, When the chain has to be extended from the centre at that time shouldn't we be adding B+1 nodes instead of B, as there will be an extra node which will be attached to the Centroid.

link

answered 21 Jun '17, 19:36

sidharth14163's gravatar image

2★sidharth14163
111
accept rate: 0%

After forming a chain of length 2B+1 then clearly node B+1 is the center of our tree. Attaching some nodes to our tree would make the diameter equal to 2B+2 so we have 2 centers. But we are taking the maximum distance between a center and a centroid (which is node 1 definitely)

(21 Jun '17, 20:26) deadwing973★

Can someone explain me the definition of centeroid and center in simple words, i'm not getting it...!!!

link

answered 23 Jun '17, 14:40

cool29874's gravatar image

3★cool29874
11
accept rate: 0%

Here is the link to my editorial with little detailed explanation of centroid and center, i too faced quite a problem in understanding these definations. Hope it helps.

link

answered 02 Jul '17, 23:36

d4dev's gravatar image

3★d4dev
114
accept rate: 0%

edited 02 Jul '17, 23:37

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:

×15,851
×1,236
×968
×711
×202
×74
×22

question asked: 19 Jun '17, 07:10

question was seen: 1,684 times

last updated: 02 Jul '17, 23:37