|
Match Editorial |
Online Round 2-A
September 27, 2006
Match summary
Only zhuzeyuan, falagar and cyfra were able to correctly solve all three problems in Round 2-A. 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 top-five.
The Problems
MatchCounts
Used as: Division One - Level One:
Value 250 Submission Rate 132 / 134 (98.51%) Success Rate 127 / 132 (96.21%) High Score Petr for 247.39 points (2 mins 55 secs) Average Score 223.62 (for 127 correct submissions)
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.
Value 500 Submission Rate 105 / 134 (78.36%) Success Rate 47 / 105 (44.76%) High Score zhuzeyuan for 463.37 points (8 mins 7 secs) Average Score 320.45 (for 47 correct submissions)
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):
- Don't use any letters 'R' at all. In this case code(s) = s. In this case, the length of code(s) is equal to the length of s.
- We use 'R' to repeat some prefix of s. Here, code(s) = code(p) + "R" + q, where p and q are prefix and suffix of s, and s is a concatenation of p and q. The length of code(s) is equal to (the length of code(p) + 1 + (length of s - length of p)).
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:
- Don't use any letters 'M' at all. In this case, the answer is equal to withoutM[0][s.length()].
- Use some letters 'M'. In this case, the letter 'M' splits code(s) in two parts (denote them s1 and s2), so code(s) = s1 + 'M' + s2. If s1, when decompressed, represents first j characters of string s, the length of s1 is equal to withoutM[0][s1.length()]. To find the answer for s2, we again can either don't use any letter 'M' or split it into 2 parts, and so on.
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 non-oriented edge. For exampe, a "2:3" tile is an edge between vertices 2 and 3, and a "1:1" tile is a loop-edge 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).
Value 1000 Submission Rate 19 / 134 (14.18%) Success Rate 5 / 19 (26.32%) High Score Petr for 713.57 points (19 mins 44 secs) Average Score 538.35 (for 5 correct submissions)
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 i-th path in the lexicographically first solution, we start it from the empty line and make it longer following the next rules:
- Stop building the path if the answer for the remaining graph is T - i - 1. In other words - stopping the path too early can increas the total number of paths needed, which will make our answer worse. Therefore, we can stop building the path only if the remaining edges can be grouped into T - i - 1 paths.
- If we continue the path, at each moment we move to the smallest vertex, which is a) connected to the previous vertex and b) doesn't change the final answer. In other words, sometimes we can continue to a wrong direction, which will force us to use more paths than needed in the optimal answer.
