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

×

Help in understanding the question Triple-tree decomposition TREE3 from LTIME59

I can't understand this question from LTIME59... Can someone please explain the question giving some more test cases!

asked 15 May '18, 19:41

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%


Question: You need to divide the edges of the given tree in groups of 3, in such a way, that all the 3 edges in a particular group shares a common vertex. The edges joining vertices (1, 3), (3, 7) & (9, 3) can form a group because the vertex 3 is common. However, the edges (1, 3), (3, 5) and (1, 7) can't form a group for the same reason. If it is impossible to group all the edges, print "NO"

Approach: Observe that the edges joining the leaf nodes can only share the other vertex (ie, the parent of that leaf node), because the leaf node itself has no other edge incident on it. Using this property, you can start from any leaf node and form groups as you go up the tree.

There are a lot of successful submissions for the problem. You can refer them. After all, the algorithm is simple:- keep on grouping the edges from one end. If you encounter any edge that can't be grouped, exit and print "NO".

You can refer to my solution here. I have performed a BFS and climbed up the tree gradually. However, there are easier and cleaner codes already submitted.

@admin The editorial link is not working. Please look into the matter.

link

answered 16 May '18, 00:02

sarthakmanna's gravatar image

6★sarthakmanna
1.0k115
accept rate: 38%

edited 16 May '18, 03:50

Thanks for reminder. I forgot to track this case due to exams. Will resolve this with @admin in morning.

(16 May '18, 00:06) vijju123 ♦♦5★

Thanks for explanation.

(16 May '18, 02:47) dushyant79175★
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:

×553
×36
×6

question asked: 15 May '18, 19:41

question was seen: 161 times

last updated: 16 May '18, 03:50