Online Round 2A September 27, 2006 Match summaryOnly zhuzeyuan, falagar and cyfra were able to correctly solve all three problems in Round 2A. The gold medal winner at the last IOI, zhuzeyuan came up with another huge performance, winning the round by more than a 100 point margin over falagar. Revenger made up for his flawed medium with four challenges, coming in third. cyfra and Petr rounded out the topfive. The ProblemsMatchCountsUsed as: Division One  Level One:
This problem can be brute forced by checking all different valid assignments. For each person, try assigning it to any of the tasks it can perform, and marking each task that gets assigned. Java code by radeye follows: int go(String[] a, int used, int at) { if (at >= a.length) return 1 ; int r = 0 ; for (int i = 0; i < a[at].length(); i++) { int b = a[at].charAt(i)  '0' ; if ((used & (1 << b)) == 0) r += go(a, used  (1 << b), at + 1) ; } return r; } public int howMany(String[] a) { return go(a, 0, 0) ; }Repeat Used as: Division One  Level Two: Experienced coders needed only a couple of seconds to see this problem required DP techique, but finding the proper way to split a case into smaller ones saved a lot of time here. Since all repeat operation are 'stopped' by an 'M' letter in the resulting expression, it's natural to use these letters to divide the input string into smaller substrings, which are encoded without using 'M's. When we need to encode a string without using any letter 'M', this means that any letter 'R' in the compression code will repeat everything between itself and the beginning of the string. Therefore, there are only two different ways to encode string s without any 'M' (code(s) denotes compression code for string s):
Now, let's move to the second part of the problem  encoding the input string using letters 'M'. To encode string s, we can use one of the following two options:
int minLength(string text) { int N = text.size(); vector< vector< int> > withoutM(N + 1, vector< int>(N + 1, 10000000)); for (int len = 0; len <= N; len++) for (int i = 0; i <= N  len; i++) { withoutM[i][i + len] = len; for (int j = 1; j <= len/2; j++) if (text.substr(i, j) == text.substr(i + j, j)) withoutM[i][i + len] <?= (len  2*j) + 1 + withoutM[i][i + j]; } vector< int> withM(N + 1); for (int i = N; i >= 0; i) { withM[i] = withoutM[i][N]; for (int j = i + 1; j < N; j++) withM[i] <?= withM[j] + withoutM[i][j] + 1; } return withM[0]; }DominoesLines Used as: Division One  Level Three: The domino lines from the statement can be easily transformed into a graph, where numbers 0..6 are vertices, and each single domino tile is a nonoriented edge. For exampe, a "2:3" tile is an edge between vertices 2 and 3, and a "1:1" tile is a loopedge from vertex 1 to itself. Having a graph, we are to find the smallest set of paths such that these paths go through each of the edges exactly once. First, lets compute the total number of paths in such a set (this problem is closely related to building an Eulerian path for a graph). It's clear that the total answer for the graph will be the sum of the answers for connected components of the graph. To find this number, compute the degree for each of the vertices in the component. If the component doesn't have any vertices with odd degree, then we can build an Eulerian cycle for this component, and the answer is 1. If the component has K vertices with odd degree, we need at minimum K/2 (you can easily prove that K will always be even) paths to cover each edge exactly once (each such path will start and end in a vertex with odd degree). Adding these number for all components gives us the total answer for the whole graph. To construct the ith path in the lexicographically first solution, we start it from the empty line and make it longer following the next rules:

