## 11206 - Coloring the map, but not anyhow

Moderator: Board moderators

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

### 11206 - Coloring the map, but not anyhow

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.

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 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
0``````
would kill the runtime of my program, although it's easily fixed.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:
I tried to solve the problem with brute force and got certainly TLE.
could anyone tell me how to optimize it or any other algorithm for this problem?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Contact:
Can anybody give some special ( tricky ) input for this problem?

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
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 ...

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### 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.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### Got ac

I just got ac. let me answer my own question.
yes, you have to consider 4 colors even if 3 colors suffice.
In some rare cases using 4 colors can get you a greater
value.