11307  Alternative Arborescence
Moderator: Board moderators

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 Contact:
Re: 11307  Alternative Arborescence
7 colors gave me ac,5 color wa. But i think a tree should have no loops and chromatic number should be 2. but this problem statement says there can be loops.
Don't assume 0 as root. The node which have no indegree is the root.
Don't assume 0 as root. The node which have no indegree is the root.
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 11307  Alternative Arborescence
I'm confused about the statement of this problem.As I can see here in this thread,everyone solved this problem with more color than 2.But Problem says..
There will be no simple loop and will be connected and we also know a tree must have n1 edges.More than n1 edge implies that this graph is not a tree.Like
following graph with 3 node and 3 edge is not a tree.
1 2
1 3
2 3
So,as shafaet said,this problem should be solvable with 2 color and shouldn't have any loop.May be I haven't understood problem properly.Can anyone help me
with this?
you will be given a tree (connected graph with no simple loops)
There will be no simple loop and will be connected and we also know a tree must have n1 edges.More than n1 edge implies that this graph is not a tree.Like
following graph with 3 node and 3 edge is not a tree.
1 2
1 3
2 3
So,as shafaet said,this problem should be solvable with 2 color and shouldn't have any loop.May be I haven't understood problem properly.Can anyone help me
with this?

 New poster
 Posts: 1
 Joined: Wed Dec 26, 2012 10:13 am
Re: 11307  Alternative Arborescence
Well, you are right about the fact that a tree is 2colorable. But the question isn't asking you to find the minimum number of colors, rather its asking for the minimum cost. Try coming up with a small example where using 3 colors could get you a smaller cost than 2 colors. This will convince you about the question.Imti wrote:I'm confused about the statement of this problem.As I can see here in this thread,everyone solved this problem with more color than 2.But Problem says..you will be given a tree (connected graph with no simple loops)
There will be no simple loop and will be connected and we also know a tree must have n1 edges.More than n1 edge implies that this graph is not a tree.Like
following graph with 3 node and 3 edge is not a tree.
1 2
1 3
2 3
So,as shafaet said,this problem should be solvable with 2 color and shouldn't have any loop.May be I haven't understood problem properly.Can anyone help me
with this?
On the other hand I've been stuck on this question for some time, getting WA. I believe my algorithm is right (dp with 20 colors), and it works on all cases I've tried (but they were small). So what could be wrong?
Code: Select all
My bad. The dynamic structure was wrong earlier. Got AC

 New poster
 Posts: 1
 Joined: Mon Feb 25, 2013 8:16 am
Re:
But can you tell me why??baodog wrote:I believe number of colors can be bounded by C*log n or so.
In this case exactly 6 colors suffice.

 New poster
 Posts: 22
 Joined: Wed May 21, 2014 10:16 am
Re: 11307  Alternative Arborescence
here i used dp algorithm
still i am getting time limit exceeded
here is my code
http://ideone.com/xHJ0FI
i need help if any crucial point is there in algo
still i am getting time limit exceeded
here is my code
http://ideone.com/xHJ0FI
i need help if any crucial point is there in algo
Re: 11307  Alternative Arborescence
I have already solved the problem.
But i'm still wondering why it is necessary to use more than two colors to color a tree
As we know a tree is BiColorable, so wouldn't it be enough to use only two color ??
Can anyone give me an example where using three or more color is optimal than using two color... cause i couldn't come up with one
But i'm still wondering why it is necessary to use more than two colors to color a tree
As we know a tree is BiColorable, so wouldn't it be enough to use only two color ??
Can anyone give me an example where using three or more color is optimal than using two color... cause i couldn't come up with one

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11307  Alternative Arborescence
prashantharshi, 6 colors is enough.
For input:Using 2 colors the best you can do is 16, using 3 or more the best you can do is 15.
I got AC always using node 0 as the root, and couldn't find a test case where using another root got a better result.
For input:
Code: Select all
11
0: 3 2 7
1:
2:
3:
4: 0 10 8 6
5:
6:
7:
8: 9
9: 1 5
10:
0
I got AC always using node 0 as the root, and couldn't find a test case where using another root got a better result.
Check input and AC output for thousands of problems on uDebug!
Re: 11307  Alternative Arborescence
Thanks brianfry713
Now i understand, why more than 2 colors needed
Now i understand, why more than 2 colors needed