11206 - Coloring the map, but not anyhow

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11206 - Coloring the map, but not anyhow

Post by sunny »

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

Post by little joey »

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:

Post by sjn »

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?

thx in advance

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

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
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Post by Mushfiqur Rahman »

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

Post by chuzpa »

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?

Post by baodog »

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

Post by baodog »

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.

Post Reply

Return to “Volume 112 (11200-11299)”