SRM 593: Meh

The one with hexagon grid

You are asked to color some hexagons in an hexagon grid using the least number of colors in such a way that no two adjacent hexagons have the same color.

I messed up during the match, first I thought that the maximum number of colors to color it was 4. It turns out it was 3, which I found out too late. Under the assumption it was 4 I wasted some precious minutes. What is really sad is that I actually looked at this page: http://en.wikipedia.org/wiki/Hexagonal_tiling#Uniform_colorings, in the first minute after opening the problem and I still didn't notice.

Once I knew the maximum result was 3, then you have to verify if it is possible to color using 0, 1, or 2 colors.

I made the assumption that this depended only on the degree, which was wrong. If there are no hexagons to color, the result is zero. If the maximum degree (maximum number of must-paint hexagons adjacent to another must-paint hexagon) is 1 or 2, then we can paint them using 2 colors (because they form a collar or a line). My mistake was in assuming that degree = 3 meant that you needed 3 colors. There is a specific case for which this isn't true:

-X-
-XX
-X-

Too bad I didn't find it, I actually tried a few hexagons with degree 3 and convinced myself that the adjacent hexagons would always share an edge. If I didn't make this blunder, I would have just done a bipartite check. If the graph is bipartite, then you can paint using 2 colors. That's the solution.

The one with teams

This one was 450 but I really couldn't break its secret. I was trying a dynamic programming, but it wasn't working at all. Then the match ended.

Challenge phase

I knew that my 250 was slow, but I was also pretty sure it was tricky (I even prepared some cases, because there were no example cases in which the maximum degree was 1, for example). But I didn't have that much luck. The codes were very complicated to read. I did find one solution that wasn't even relying on degrees but on partial degrees. So I challenged it, and was happy, because the 50 pts would fix the slow submission. So I went to see the room summary and boom: My solution was already challenged. Probably if I noticed about my solution getting challenged I wouldn't have risked making that challenge...

Comments?

I liked the 250 until I learned checking for bipartiteness was mandatory. Too messy for the slot. 450 said "difference" when it should have specified absolute value of the difference, this made me waste time coding a wrong solution.