can anybody share their faster approaches.
my solution of this problem is in near 2 secs. but there is a person in the ranklist who got this in .004 secs. i wonder how can it be done so fast.
11206 - Coloring the map, but not anyhow
Moderator: Board moderators
-
little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
I don't know; I've been wondering too. There might be some kind of greedy that works. It makes sense to give a vertex with a high degree an extreme color value (highest or lowest) and it's surrounding vertices color values as close as possible to the other extreme. But I can't see an algorithm that exploits that fact and would guarantee an optimal result in all possible cases.
It should be noted that the current input contains no disconnected maps, which makes the problem slightly easier: you don't have to split the separate connected components. An extreme case likewould kill the runtime of my program, although it's easily fixed.
It should be noted that the current input contains no disconnected maps, which makes the problem slightly easier: you don't have to split the separate connected components. An extreme case like
Code: Select all
20 10 1 3 9 27
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
0The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
I've wondering too, and now I got to a solution in 0.004 sec.
My previous approach was: First assign c1 ~ c4 to the regions and after coloring, assiging the actual values (C1 ~ C4) to c1 ~ c4 (24 ways).
Now I'm using branch and bound. Amazing! Its quite fast than the previous approach which runed in 0.922 sec.
----
Rio
My previous approach was: First assign c1 ~ c4 to the regions and after coloring, assiging the actual values (C1 ~ C4) to c1 ~ c4 (24 ways).
Now I'm using branch and bound. Amazing! Its quite fast than the previous approach which runed in 0.922 sec.
----
Rio
-
Mushfiqur Rahman
- Learning poster
- Posts: 56
- Joined: Tue Jun 13, 2006 5:18 pm
- Location: (CSE, SUST) Sylhet, Bangladesh
- Contact:
I/O's
Could anyone post some inputs and outputs for this problem ?
By the way my program gives
6760
as output for the input above.
Thanks ...
By the way my program gives
6760
as output for the input above.
Thanks ...
Cases where you want to use 4 colors, where 3 suffices?
Are there cases where you want to use 4 colors,
while it requires only 3 colors to color the graph?
Obviously, with 1 or 2 colors, we don't need to consider
using more colors. However, for 3 colors, I can't find
an example where it would require you to use 4 colors
to get the maximum of the function.
while it requires only 3 colors to color the graph?
Obviously, with 1 or 2 colors, we don't need to consider
using more colors. However, for 3 colors, I can't find
an example where it would require you to use 4 colors
to get the maximum of the function.