Match summary

After 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.

The Problems

TextStatistics

Used as: Division Two - Level One:

Value 250

Submission Rate 328 / 346 (94.80%)

Success Rate 183 / 328 (55.79%)

High Score wilan for 247.83 points (2 mins 39 secs)

Average Score 207.03 (for 183 correct submissions)

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/words

See sims's solution for a clear implementation.

CreatePairs

Used as: Division Two - Level Two:

Value 500

Submission Rate 262 / 346 (75.72%)

Success Rate 94 / 262 (35.88%)

High Score fhoward for 481.38 points (5 mins 37 secs)

Average Score 309.40 (for 94 correct submissions)

Used as: Division One - Level One:

Value 250

Submission Rate 303 / 309 (98.06%)

Success Rate 221 / 303 (72.94%)

High Score Eryx for 247.75 points (2 mins 42 secs)

Average Score 201.27 (for 221 correct submissions)

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:

Elements from B remain unpaired.
It doesn't require much time to see that the optimal way to pair elements from C is to pair adjacent elements after sorting them in descending order. In this way all elements (with the possible exception of the smallest one) will be paired.
The same method can be applied to D (due to the fact that the product of two negative numbers is a positive one). If the group A is nonempty, we can get rid of the smallest unpaired element from D (which remained negative) by pairing it with zero.

Here's the above algorithm in pseudocode:

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 answer

Take a look at OuFeRRaT's solution for an implementation of a similar method.

Squares

Used as: Division Two - Level Three:

Value 1000

Submission Rate 110 / 346 (31.79%)

Success Rate 19 / 110 (17.27%)

High Score jwy258 for 907.67 points (9 mins 15 secs)

Average Score 624.10 (for 19 correct submissions)

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/4

The 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(w²h²) solution easily runs in time. The highest scorer on this problem, jwy258, used a similar approach.

RestoringPolygon

Used as: Division One - Level Two:

Value 550

Submission Rate 144 / 309 (46.60%)

Success Rate 16 / 144 (11.11%)

High Score gawry for 383.60 points (20 mins 42 secs)

Average Score 275.02 (for 16 correct submissions)

There are no more than 16 horizontal line segments, therefore we can try all the 2¹⁶ 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(2ⁿn²). A similar approach was successfully used by nik239.

LadderPermutation

Used as: Division One - Level Three:

Value 950

Submission Rate 61 / 309 (19.74%)

Success Rate 31 / 61 (50.82%)

High Score Astein for 869.02 points (8 mins 50 secs)

Average Score 597.59 (for 31 correct submissions)

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):

write integers in ascending order from 1 to n:
```
1 2 3 4 5 6 7 8 9 10 11 12 13
```
divide them in m consecutive blocks of size at most k elements (with at least one block actually having size of k). This is possible due to previously derived contraints on n:
```
[ 1 2 3 ] [ 4 ] [ 5 6 7 8 ] [ 9 10 ] [ 11 12 13 ]
```

reverse the order of integers in each block:

[ 3 2 1 ] [ 4 ] [ 8 7 6 5 ] [ 10 9 ] [ 13 12 11 ]

as you can see, blocks form decreasing subsequences, and every decreasing subsequence is contained in some block — therefore the longest one has size of k. On the other hand, all increasing subsequences are formed by picking at most one integer from each block and we can easily find one with length m. So forget about blocks and admire your (m,k)-ladder permutation:
```
3 2 1 4 8 7 6 5 10 9 13 12 11
```

Dividing integers in blocks to make the initial blocks as small as possible will result in lexicographically smallest permutation:

[ 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 perm

Astein's solution is one of them.

By monsoon
TopCoder Member