|
Match Editorial |
Wednesday, December 1, 2004
Match summary
Before writing the match summary, I often go from room to room listening to what the competitors thought of the round. The Division 2 coders seemed to have reached a consensus. This was one of the most difficult SRMs in recent history. Both the medium and hard problems had only 2 successful submissions. Mysteriously, each of these 4 submissions belonged to different coders. BeanSweany, owner of the fastest hard submission, took home the Division 2 crown. The Division 1 results were far less dismal. Eryx finished the entire set in under 22 minutes. Ploh, only slightly behind Eryx after the coding phase, took the lead with a successful challenge. We congratulate him on his first SRM win.
The Problems
EqualSubstrings
Used as: Division Two - Level One:
Value 250 Submission Rate 145 / 181 (80.11%) Success Rate 78 / 145 (53.79%) High Score kclancy for 242.34 points (5 mins 5 secs) Average Score 179.53 (for 78 correct submissions)
When the coding phase began, I expected someone to ask what should be returned if the string could not be adequately split. To my surprise, the question was never posed. This is probably a testament to the skill of the competitors, since such a split is always possible. To solve this problem, simply try all possible prefixes, and keep the largest one that works. Java code follows:
int count(char c, String s) {
int ret = 0;
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == c) ret++;
return ret;
}
public String[] getSubstrings(String str) {
for (int i = str.length() ;; i--) {
String x = str.substring(0,i), y = str.substring(i);
if (count('a',x) == count('b',y)) return new String[]{x,y};
}
}
PointLifeGame
Used as: Division Two - Level Two:
Value 650 Submission Rate 13 / 181 (7.18%) Success Rate 2 / 13 (15.38%) High Score fractaled for 379.42 points (28 mins 44 secs) Average Score 321.21 (for 2 correct submissions)
This problem proved extremely difficult for Division 2 coders. In my opinion, there are 3 very distinct issues that need to be handled:
- The number of points can become unwieldly if not dealt with properly.
- Points have to be compared, in order to find the best one.
- The resulting point must be output in a particular format.
String make(double d) {
int di = (int)(d*10000); //get an extra 4 digits
String whole = di/10000+"", frac = di%10000+"";
while(whole.length() < 4) whole = "0"+whole; //add zeros if needed
while(frac.length() < 4) frac = "0"+frac;
return whole+"."+frac;
}
As for issue 2, some sort of comparison function should be written that compares points as
described in the problem. This function can be given to an ordered set container, which will also
serve the purpose of removing duplicates. To deal with issue 1, observe that the best k points after
round n are a subset of the points generated by the best k+1 points before round n (why?). This means we
will never need more than 11 points since the maximum number of rounds is 10. Thus, after each
round, the total set of points can be pruned such that only the best few remain.
NumberChanger
Used as: Division Two - Level Three:
Used as: Division One - Level Two:
Value 1100 Submission Rate 9 / 181 (4.97%) Success Rate 2 / 9 (22.22%) High Score BeanSweany for 659.37 points (27 mins 26 secs) Average Score 532.50 (for 2 correct submissions)
Value 500 Submission Rate 143 / 194 (73.71%) Success Rate 73 / 143 (51.05%) High Score athenachu71 for 485.33 points (4 mins 58 secs) Average Score 352.98 (for 73 correct submissions)
There are numerous ways to solve this problem. One of the faster methods computes a minimum cost bipartite matching. Such an algorithm is overkill here since the constraints are quite restrictive. Many of the C++ submissions I read used next_permutation to step through all possible orderings of the numbers. For each permutation, the number of swaps and the number of increments/decrements must be computed. My Java solution utilizes breadth first search. Using the start string as my initial node, I explore outward one swap at a time. After exhausting all possible permutations, the best score is returned. This technique has the added benefit of counting the number of swaps for you. If you want to optimize this method, use integers (instead of strings) to store the intermediate values.
TerribleEncryption
Used as: Division One - Level One:
Value 250 Submission Rate 194 / 194 (100.00%) Success Rate 184 / 194 (94.85%) High Score nicka81 for 248.38 points (2 mins 17 secs) Average Score 224.56 (for 184 correct submissions)
The easiest way to solve this problem is to loop through data, and try all possible k-values until one works. When I originally wrote the problem, the constraints made this type of brute force solution impossible. A faster method utilizes Euclid's algorithm for computing the greatest common divisor (GCD). Given positive integers a and b, Euclid's algorithm will find integer coefficients x and y such that xa + yb = g, where g is the GCD of a and b. Letting a = data[i] and b = keys[i], the algorithm will give us x and y such that
x*data[i] + y*keys[i] = 1
The 1 is guaranteed by the constraints. Since we are working mod keys[i], the y*keys[i]
term can be ignored. Thus x is practically the k value we are looking for. k is actually the
smallest positive integer congruent to x mod keys[i].
PresentationComp
Used as: Division One - Level Three:
Value 900 Submission Rate 57 / 194 (29.38%) Success Rate 22 / 57 (38.60%) High Score Eryx for 752.53 points (13 mins 7 secs) Average Score 482.74 (for 22 correct submissions)
This problem has many more nuances than you might expect. For those who are familiar with group
theory, the set described here closely resembles the 48-element non-abelian group Z6
semidirect Z8. Another interesting feature is that the constants 5, 6, and 8 that occur
in the problem were not chosen randomly, but picked with care. The following proof will not work if
those numbers do not agree.
The method I advocate relies on 2 facts:
- The returned string will never contain more than 12 characters.
- Given two strings A and B, equivalence can be determined quickly.
The key concept is that any string of x's and y's can be converted into a canonical form where y's occur before x's. To notice this, observe that the rule xy -> yyyyyx shows how to move a y across an x. Continuously applying this rule to the leftmost occurrence of xy, we eventually arrive at a string that has y's before x's. Once in this form, we remove x's 8 at a time, and y's 6 at a time until we can no longer do so. The resulting string is what I call the canonical form. Let c(A) denote the canonical form of expression A. Clearly c(A) will never have more than 12 characters since it can have at most 5 y's and 7 x's.
The problem states that 2 strings A and B are "equivalent" if there is a string C such that A can be reduced to C and B can be reduced to C. Let A~B denote A and B are equivalent. What we will now prove is that A~B if and only if c(A)=c(B).
Proof. First observe that if c(A)=c(B) then A can be reduced to c(A) and B can be reduced to c(A) (converting a string to canonical form constitutes a reduction). Thus A~B. Conversely, we will assume that A~B. This implies there is a string D such that A can be reduced to D and B can be reduced to D. We will show that c(A)=c(D)=c(B). To do this, we will prove that if string G reduces to string H in one step, then c(G)=c(H). This will establish the above triple equality via induction on the number of reduction steps.
There are 3 possible ways to turn G into H:
- We apply the rule that deletes x's. Thus G has the form pxxxxxxxxq and H is pq, where p and q are strings. If we compare the workings of c(G) and c(H) we see that y's making their way leftward from the right side of the string must cross 8 more x's in G than in H. This begs the question, does crossing 8 x's alter the y? Observe that each time a y crosses an x we get 5 copies of the y. Thus, when a y crosses 8 x's, we get 58 y's. Since 5 is congruent to -1 mod 6, we see that 58 is congruent to 1 mod 6, so in the grand scheme of things, y is unscathed during its journey over the sea of 8 x's. Thus c(G)=c(H).
- We apply the rule that deletes y's. Thus G has the form pyyyyyyq and H is pq, where p and q are strings. Again comparing how c(G) and c(H) are computed, we can see that once these 6 y's make their way to the left side of the string, their numbers will still be a multiple of 6. More precisely, these 6 y's will contribute 6*5k y's to the y-count (before the final y removal), where k is the number of x's crossed in p. Since 6*5k is congruent to 0 mod 6, these y's can be safely deleted. Thus c(G)=c(H).
- We apply the rule that replaces xy with yyyyyx. Thus G has the form pxyq and H is pyyyyyxq, where p and q are strings. This turns out to be the easiest case since c(G) will make this exact replacement once the occurrence of xy in question becomes leftmost. Thus c(G)=c(H).
