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 ProblemsEqualSubstringsUsed as: Division Two  Level One:
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:
This problem proved extremely difficult for Division 2 coders. In my opinion, there are 3 very distinct issues that need to be handled:
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:
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. TerribleEncryptionUsed as: Division One  Level One:
The easiest way to solve this problem is to loop through data, and try all possible kvalues 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] = 1The 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:
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 48element nonabelian group Z_{6}
semidirect Z_{8}. 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 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:

