.png)
SnackDown 17 onsite finale was yesterday at almost midnight (in my timezone). The best 25 teams in ellimination round travelled to Mumbai to crack 10 problems in 5 hours and decide who is the best CodeChefer.
Is the first time that I’m a problem setter in a major programming contest! My problem (BCYCLES) can be stated in one line:
Given a bicubic graph, find a set of cycles such that every edge belongs to exactly two cycles.
The key idea is that if we paint the edges of the cycles with 3 colors (r:red, g:green, b:blue) in such a way that no two edges of the same color share a vertex, then we can easily generate the cycles as follow:
1. cycles of r,g alternating colors.
2. cycles of g,b alternating colors.
3. cycles of b,r alternating colors.
Now the problem is how to find such edge coloring. It turns out that every bicubic graph has a perfect matching (indeed, every k-regular bipartite graph has a perfect matching), so we can paint with red all the edges of the perfect matching. If we remove the edges of the perfect matching, we get cycles of even length (remember that the graph is bipartite), so we can paint the cycles alternating with green and blue.
Bonus problem: If we find a set of cycles in which every vertex belongs to exactly 3 cycles, then is also true that every edge belongs to exactly two cycles?
The easiest problem of the contest was probably MAXIEDGE: Given a matrix of 2xn, shuffle the characters in such a way that the number of equal adjacent cells is maximized. After noticing that the number of elements with odd frequency is even, the solution arises inmediatly. By the way, the first time that I read the problem, I understood it wrong and thought that we can only move elements of the same row (solve this version as an easy bonus problem 🙂 ).
I also liked problem HULLSUM, it was about constructing a set of 50 points in which the sum of the sizes of the convex hulls over every subset is at most 
Another problem that I solved during testing was UNIVERSE. The queries can be answered using the Dijikstra algorithm, but the hard part is to construct the graph. Given a tree, we have to build another tree consisting of some vertices in such a way that the “ancestor” relationship is preserved. This is an standard problem, the idea is that a tree is like a parenthesization, and every node can be considered as an interval.
aleigorithms 