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 in-degree is the root.
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
UVa stats: http://felix-halim.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 n-1 edges.More than n-1 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 n-1 edges.More than n-1 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 2-colorable. 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 n-1 edges.More than n-1 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![:(](./images/smilies/icon_frown.gif)
As we know a tree is Bi-Colorable, 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![:(](./images/smilies/icon_frown.gif)
But i'm still wondering why it is necessary to use more than two colors to color a tree
![:(](./images/smilies/icon_frown.gif)
As we know a tree is Bi-Colorable, 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
![:(](./images/smilies/icon_frown.gif)
-
- 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 ![:)](./images/smilies/icon_smile.gif)
Now i understand, why more than 2 colors needed![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
Now i understand, why more than 2 colors needed
![:)](./images/smilies/icon_smile.gif)