OJ Board

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.

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.

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

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

Can anybody give some special ( tricky ) input for this problem?

Could anyone post some inputs and outputs for this problem ?
By the way my program gives

6760

as output for the input above.
Thanks ...

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.

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.