This topic is about CEOI 2012 — "Circuit" task (day 1, task2). In a few words, you are given the coordinates for all vertices of a polygon and you are to determine those vertices visible from (0,0) point. All vertices are situated in the first quadrant. The official solution starts with some good idea: for every point consider its polar angle and determine the point having the less and the greatest such angle. Now we can ignore "the upper part", but this idea will become obsolete, as we will soon see.
The official solution continues with some fuzzy observations (I think there are some mistakes in typewriting) and finally needs some structure in which deletion must happen very fast.
I must recognize the idea seemed to be very clever at the beginning, but... Why not the following solution?
- construct a function turn(a,b,c) which returns 0 if P[a],P[b],P[c] are co-linear, 1 if P[c] is on the left of P[a]P[b], -1 if P[c] is on the right of P[a]P[b]
- after determining the first and the last points (those having the less and the greatest polar angle) use a stack, S, containing points
- at the beginning S.push(first)
- for all other points, i, considered in the order in which they go from first to last, on the "lower" part of the polygon
— if S contains only one element, then S.push(i) — if turn(0,S.top(),i)==1, then S.push(i) — if turn(0,S.top(),i)==-1, then examine the position of i relative to the segment determined by the top two points from S and ignore i or S.pop(), if turn is -1 or 1 This idea is also used by an algorithm for determining the convex hull for a set of planar points and I think it is much more easy to understand and implement.

I hope you will understand my idea and have constructive opinion, instead blindly press dislike button.

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.