Thursday, December 28, 2006
Match summaryAfter the dust settled in Division One, three targets took the top spots on the leaderboard: krijgertje, Petr and Eryx. Only two coders managed to solve all three problems. A tricky 550-pointer had a success rate of only 11.11% and proved to be one of the hardest Division One mediums ever. The lesson: never underestimate problems that look easy. Make a careless implementation or overlook a crucial corner case, and you could end up with 0 points.
In Division Two, the top three spots went to newcomers: jwy258 (whose quick solutions and 300 points on challenges gave him fifth place in the Highest Match Total chapter of the Algorithm Competition Record Book), radi0actv and lewha0.
Used as: Division Two - Level One:
This is an fairly easy problem for Division Two, and didn't require much effort or code to solve. Each letter in the text adds one to the sum of all the words' length. Each letter not preceded by another letter begins a word, so it adds one to the words counter:
length = 0, words = 0 for each character in text: if this character is a letter: ++length if this is the first character or the previous character wasn't a letter: ++words if words == 0: return 0 else: return length/wordsSee sims's solution for a clear implementation.
Used as: Division Two - Level Two:
Used as: Division One - Level One:
The first thing to notice in this problem is that there is no reason to pair positive and negative integers, so we can do pairings in these two groups separately. Because zeros are neither positive nor negative we will handle them as a special case, and will treat ones as a special case as well (because pairing ones is pointless).
We have four groups — A: zeros, B: ones, C: integers greater than 1 and D: negatives. We handle them as follows:
for each i in data: if i == 0: zeros++ elif i == 1: ones++ elif i > 0: positive.append(i) else: negative.append(i) if length(positive) is odd: positive.append(1) if length(negative) is odd: if zeros > 0: negative.append(0) else: negative.append(1) sort(positive) sort(negative) answer = ones for i = 1 to length(positive)/2: answer += positive[2*i-1] * positive[2*i] for i = 1 to length(negative)/2: answer += negative[2*i-1] * negative[2*i] return answerTake a look at OuFeRRaT's solution for an implementation of a similar method.
Used as: Division Two - Level Three:
The solution to this problem is rather straithforward. Every square is determined by its two adjacent vertices. We can iterate over every pair of vertices, check whether the square determined by them fits in the board and is valid (all vertices contain the same letter):
for each cell (x1, y1) on field: for each cell (x2, y2) on field: if cells (x1, y1) and (x2, y2) are distinct and contain the same letter: dy = y2 - y1 dx = x2 - x1 y3 = y2 + dx x3 = x2 - dy y4 = y3 - dy x4 = x3 - dx if points (x3, y3) and (x4, y4) are on field and they contain the same letter as (x1, y1): count++ return count/4The last division is necessary, because we counted every square four times. Since w and h, dimensions of the field, are limited by 50, this O(w2h2) solution easily runs in time. The highest scorer on this problem, jwy258, used a similar approach.
Used as: Division One - Level Two:
There are no more than 16 horizontal line segments, therefore we can try all the 216 possibilities of removing some of them. Assume that we have a set of n horizontal segments that have to be used. They are mutually disjoint and their endpoints are 2n vertices of our polygon. A polygon with 2n vertices has 2n edges, so it's clear that we have to add exactly n vertical segments.
How to find them? Fix the y and consider all vertices that have the second coordinate equal to y. If there is an odd number of them you should stop -- construction is impossible. If not, sort them by the first coordinate and pair the adjacent ones.
Now we have constructed a 2n-polygon, but we have to check two more things before we are done (failure to do so trapped many competitors). From the problem statement we know that the polygon "must have a single, non-intersecting boundary." To test if the boundary is single we can treat the polygon as a graph and apply one of many algorithms for checking graph connectivity. For the second requirement we can test all pairs of segments to see whether they intersect points different from vertices.
The total running time is O(2nn2). A similar approach was successfully used by nik239.
Used as: Division One - Level Three:
The first step to solving this problem is to determine what cases have no solution. Some m distinct integers must belong to a longest increasing subsequence, and some k integers must belong to a longest decreasing subsequence. These subsequences can share at most one integer, therefore a (m,k)-ladder permutation has to have at least k+m-1 elements.
On the other hand, this permutation cannot have more than mk elements. This fact is known as Erdos-Szekeres Theorem: a sequence of mk+1 different elements contains an increasing subsequence of m+1 elements or a decreasing subsequence of k+1 elements. The reader is encouraged to find an elementary proof of this theorem using the pigeonhole principle.
It turns out that if k+m-1 ≤ n ≤ mk the solution always exists. To construct one follow this procedure (illustrated with n = 13, m = 5, and k = 4):
[ 1 ] [ 2 ] [ 5 4 3 ] [ 9 8 7 6 ] [ 13 12 11 10 ]Most coders used variations of the following algorithm:
if k+m-1 > n or n > m*k: return no answer n -= m for i = m downto 1: count[i] = 1 + min(n, k-1) n -= min(n, k-1) n = 0 for i = 1 to m: for j = count[i] downto 1: perm.append(n+j) n += count[i] return permAstein's solution is one of them.