ACM ICPC, final results

Golden medalists:

1. St. Petersburg University of IT
2. University of Warsaw
3. Moscow University of Physics and Technology
4. Shanghai Jiao Tong University

Full results are at: http://www.icpclive.com/
The problems can be found here.

The winning team expected to solve 10 problems

Problem A - it's a lure, don't go there, says Jakub Pawlewicz, ICPC World Finalist (1998). It's puzzling that nobody submitted any solution to problem J, one of the easiest to me. Problem K is not hard either, but the number of special cases that need to be considered may be intimidating. Jakub expects the winning team to solve as many as 10 problems this year.

ACM ICPC, Problem K "Stacking Plates"

In this problem, we deal with stacks of plates that behave like disks in the Towers of Hanoi puzzle. A plate can be put on top of another plate, whose diameter is not smaller. Unlike in the famous puzzle, there is no limit on the number of stacks of plates.

In a single move, we can take some plates from a stack and put them aside (split), or put one stack on top of another stack (join). It is not possible to move directly some plates from top of one stack to some other stack &emdash; one has to make two moves: split and join.

Given \(m\) stacks of plates, we are looking for a minimum number of moves needed to merge them into a single stack.

This task is quite easy. Looking at the statistics, it is the fifth most solved task. Why the fifth? Maybe because K is not at the beginning of the alphabet ...

It can be solved in a greedy manner. Think about the largest plate. It is at the bottom of some stack. Let us say, that \(k\) bottom stacks from this stack are larger or equal than all the other plates. So, these \(k\) plates can be put at the very bottom of the final stack. The problem reduces to a smaller one. This way, we can find the minimal set of stacks into which we have to split the original stacks. Finally, we should join all the stacks into a single stack.

In a way, it is just merging \(m\) sorted sequences into one sorted sequence, by moving minimum number of segments of elements.

Teams will suffer solving ICPC Problem C

There are few approachable problems, but others are really hard, says Bartek Klin, two-time ICPC World Finalist (1997, 1999). Problem B is definitely doable, though heavy on math. Calculation of a volume bounded by a polynomial seems like a handicap for those who graduated from calculus class recently. Problem C is roughly a traveling salesman problem. Although it is pretty standard, teams will suffer with this one. Everybody codes KMP blindfolded, but NP-hard problems are always salt in the eye and pain in the neck. Problem A looks like a minimum spanning tree with a rather extreme twist. A weird one. I am thinking about this one as a dynamically changing spanning tree. Intriguing. Problem E - a vertex cover, but the graph is pretty large (75 vertices), smells like a trap. Teams, beware!

ICPC Problems B,D, K and J not too taxing, the fight will ensue elsewhere

Problems B, D and K are rather easy to solve and implement, comments Krzysztof Onak, Postdoctoral Fellow at Carnegie Mellon and ICPC World Champion (2003). Most of the problems are pretty standard, for instance the problem J is a variant of the shortest path problem. Decent teams will solve these problems sooner or later. The easier problems were the primary focus of many teams so far. The real fight will ensue where all the easy problems are done. We yet have to see which teams will manage to cut through the easier problems quickly enough to save enough time and strength for the strenuous finish.

ICPC Problem K - teams may bog down

Problem K seems particulary cumbersome. Many special cases, teams may get tangled in them and bog down, says Andrzej Gąsienica-Samek, CTO of Atinea.pl and ICPC World Champion (2003).

ACM ICPC, Problem D "Fibonacci Words"

Fibonacci words are strings, that are defined in a recursive way, similarly to Fibonacci numbers. \(F(0) = 0\), \(F(1) = 1\), \(F(n) = F(n-1)\cdot F(n-2)\), where \(\cdot\) denotes string concatenation. Here are a few first Fibonacci words:
0
1
10
101
10110
10110101

Given a sequence of bits \(p\) and an integer \(n)\, the task is to compute the number of occurrences of \(p\) in \(F(n)\).

Fibonacci words have been intensively studied in computer-science. Now wonder, the problem of finding patterns in Fibonacci words already has been considered. A similar, or even more difficult, problem has appeared in Polish OI, http://main.edu.pl/en/archive/oi/16/slw.