VK Cup 2012 Practice Session Tutorial

A. Multicolored Marbles

Let's consider the array M, M[k] meaning the number of "zebroids" we can find in an alternating sequence of k elements and containing the k'th element. The answer to the problem is S[n]=M[1]+M[2]+M[3]+...+M[n]. If we look the way in which M is formed, we can see that M[1]=1, M[2]=2, M[3]=3, M[k]=1+M[k-1]+M[k-3]+M[k-5]+.... This rule constructs M as a Fibonacci array. Moreover, S[n]=M[n+2]-2, so all we have to do in this problem is to calculate a certain element of Fibonacci's sequence and substract 2. It is no need to use a log2n method, a linear one is good too.

B. Pixels

Instead of considering pixels of red, green and blue colors we can consider three heaps of objects. a is the number of objects in the first heap, b is the number of objects in the second heap and c is the number of objects in the third heap. The goal is obtain a configuration in which there are objects in only one heap. The solution is based on the observation that before obtaining the final configuration we must have another configuration in which were two heaps having the same number of objects. The last moves consist in taking several times one object from each of those two heaps and getting a new object in the "destination" heap. So, we can use a function, let's say int f(int a, int b), which determines the total number of moves needed to obtain a=b and after that moving all the objects to the third heap. We can see two properties: - if a%2 != b%2 this goal is unachievable, so f returns 2*10^9 - if a%2 == b%2 this goal is achievable and the total number of moves needed to obtain only one heap is exactly equal to max(a,b) The result is min(f(a,b), f(b,c), f(a,c)) There are no casese when the answer is -1. There are no special cases when, for instance, a=0, or a=b, etc. Thanks to Cezar Mocan for this solution.

C. Trails and Glades

This is, obviously, a problem in which we have an initial undirected multigraph and we have to add a minimal number of edges so that we obtain an Eulerian multigraph. This is a classical problem. First we determine the number of connected components and establish for each vertex the connected component to whom it belongs. This can be easily done in O(n), using a breadth-first traversal. Let's name C the number of connected components and NE the number of connected components in which there isn't any Eulerian cycle. To check if a connected component contains an Eulerian cycle just check the degrees of it's vertices, they all must be even. Let's name V the number of vertices having odd degrees. If C=1 then the answer is V/2 If C>1 then the answer is (V-2*NE)/2+C Thanks to Alexandru Velea for collaborating to this solution.