# [Community Puzzle] Map Colorations

https://www.codingame.com/training/hard/map-colorations

Send your feedback or ask for help here!

Created by @DPAmar,validated by @Niako,@IAmNoob and @RoboStac.
If you have any issues, feel free to ping them.

On of the best Dynamic Programming puzzles in CodinGame!!! 5 stars!!
Props for @DPAmar

2 Likes

Once again, Wikipedia is a coderâ€™s friendâ€¦
Without the theory, this would have been unsolvable most likely.
With it, it was doable relatively easily.

Any help with this one? Canâ€™t figure out how to make a working formula from the given information. Managed to get the right answers for the first 3 when i manually add the formulas i figured out when i drew the graphs but otherwise iâ€™m completely stuck.

You donâ€™t have to use an optimal graph coloration algorithm as the graphs are small here, so a simple backtracking will do.
Try to put colors and backtrack if it doesnâ€™t work.

2 Likes

2Evolve11, Hint: â€śChromatic polynomialâ€ť

2 Likes

Hi
I see how to do the backtracking and everithing. The problem i have is what form should i give to my graph in the first place given that they give us links 1 by 1. I thought of something like [node,[list of neighbours],color of the node]. I find it a bit tricky. Do you have something else in mind to manipulate graphs more easily ??
Thanks

Iâ€™ll echo Aboutâ€™s hint about â€śchromatic polynomialâ€ť. Itâ€™s a bit complicated to understand, but gives a more efficient solution than trying to explicitly color each graph and individually count how many ways youâ€™re capable of doing so.

As for graph representation, I just used an adjacency matrix represented by 26 32-bit ints. 26, because the problem says thereâ€™s at most 25 edges in any of the graphs (and I assumed theyâ€™re connected graphs), hence at most 26 nodes. Those ints are just bit masks. For int u, bit v is set if the edge (u, v) is in the graph. Pretty cheap to copy and pretty cheap to edit. Both useful properties for my solution.

The puzzle is much more difficult than it seems at first glance.

I wrote recursive function in python (from empty graphs) and I canâ€™t pass the last USA test.
Rewrote function in C++ and I still canâ€™t pass the last USA test =D
wtf

My recursive function in Python passed all the tests and validators.

Finally I passed all validators in C++ by using binary graph representation changed from arrays how MuddySneakers hints.
However It still not passing last USA test without using special optimization flags.

I was also a bit surprised the straightforward implementation in C++ times out without compiler optimisations forced on, however there are some relatively simple algorithmic optimisations you can add to dramatically tame the exponential branching so this is certainly doable even in slower languages and without hardcoding array sizes etc. I left some performance comparisons in my published code if anyoneâ€™s interested.

Really interesting problem by the way, I had a lot of fun!

Remind me the puzzle about Pick formula. If you know it - here is nothing to do, if no then â€¦ Astrologers proclaim the week of optimization. Key for this puzzle is Wikipedia â€śChromatic polynomialâ€ť â€¦ recursively change this graph, wile it is not â€śedgeless graphâ€ť and then use simple equation.