PROBLEM LINK:
Author: Alei Reyes
Tester: Hussain Kara Fallah
Editorialist: Devvrat Gupta
DIFFICULTY:
EASY
PREREQUISITES:
Basic Mathematics and Strong English
PROBLEM:
Following the definition of centroid and center we need to find if for given value of n and b a configuration of nodes exists. If Yes then we need to print the vertices number connecting these edges.
EXPLANATION:
Here the question isn’t tough but the language sure is so i will try to break it down for you, this will give you an opportunity to think this through your perspective.
First things first
Centroid:
Any of the node can be called centroid if on removing that node we get a connected component of nodes of at most n/2 size. If more then one centroid exists then beauty will be equal to the maximum number of nodes between center and centroid.
Center:
Here center is same as the normal center i.e. suppose if there are 2*k+1 nodes on a parallel line then center will be the kth node.
Distance
Here distance is not the cartesian distance instead its the number of nodes between the center and centeroid.
Now you know what center and centeroid means you need to find a configuration for given n and b which will follow all the constraints.
We need beauty of B so this means that maximum distance between one of the centeroid and center has to be equal to B. For that we will first take 2B+1 nodes into consideration. We will arrange them on a parallel line, after this arrangement Bth node will be our center. Now we need to create centeroid which is B nodes apart from the center. We will try to make 1st node on this parallel line to be the centeroid as it is B distance apart from the center node. Now 1st node being the centeroid implies what? It implies that on removing this node from our tree we can atmost have n/2 connected nodes(Remember Centroid definition). so this implies that the remaining 2B nodes on the right of the first node must be <=n/2 as the first node is our centeroid. So mathematically we have
2B<=N/2
4B<=N
So if N is less than 4*B then it won’t be possible to create the mentioned tree.
Special cases
Case1 When N=2 and b=0. In this case its not possible to create the configuration of 2 nodes which gives the beauty of 0.
Case2 When N=3 and b=0. In this case beauty of B>0 is not possible as we only have 3 nodes.
Hopefully I have made myself clear enough for you to write your own algorithm for the printing of the edges.
But if you still face difficulty you can refer to my code moreover i will be glad to answer your queries. Here is my Blog which consists of some more interesting questions of Spoj and Codechef that might be of your help. HAPPY CODING!
ALTERNATIVE SOLUTION:
I would like to know if someone thought of more efficient way to solve this interesting problem.
EDITORIAL’S SOLUTIONS:
My solution can be found here.