Saturday, April 2, 2005 Match summary In division 1, tomek squeaked out a win, despite starting 15 minutes late, and hence regained the number 1 ranking. liympanda took second place with the help of 175 challenge points and in spite of a resubmission. snewman rounded out the top 3 almost 90 points behind tomek. In division 2, first timer Vintik took top honors, with more than a 100 point lead on second place fredphil. The ProblemsMassiveNumbersUsed as: Division Two  Level One:
While this problem required a little bit of math, the formulas were given to you, so it really became a parsing problem. You need to split the input string into the base and the exponent, then apply the formula, and return the result. It's worth noting that the trick described for comparing very large numbers may also be used with very small numbers, and is applicable in many situations. BusinessTasksUsed as: Division Two  Level Two: Used as: Division One  Level One:
With n as large as ten million, you have to be a little careful about timing out if you perform a naive simulation of the process. However, you can use a bit of simple math to make it run instantaneously. If there are k things, and you want to count to n, starting from j, you will simply end up at (j+n)%k. Using this, its just a matter of removing the elements as specified, and running the simulation. ComputerExpertUsed as: Division Two  Level Three:
This was a good problem to use your language's builtin set class or template on. You can represent the known facts as a set of strings, and then you can do many of the operations as set operations. For example, to find out if one or more of a number of facts are true (the OR operation), you can simply do set intersection. For example, in Java, you can make some clever use of the Collections API to write quite short code. public String[] operate(String[] facts, String[] rules){ Set r = new TreeSet(); r.addAll(Arrays.asList(facts)); boolean changed = true; while(changed){ changed = false; for(int i = 0; i<rules.length; i++){ String[] sp = rules[i].split(" > "); if(tr(r,sp[0])){ changed = r.add(sp[1]); } } } r.removeAll(Arrays.asList(facts)); ArrayList al = new ArrayList(r); return (String[])al.toArray(new String[0]); } boolean tr(Set s, String r){ String[] sp = r.split(","); for(int i = 0; i<sp.length; i++){ String[] s2 = sp[i].split("/"); Set t = new TreeSet(Arrays.asList(s2)); t.retainAll(s); if(t.size()==0)return false; } return true; }HammingNumbers Used as: Division One  Level Two:
The most obvious way to do this problem is with an algorithm similar to Dijkstra's. Start with the number 1, then multiply it by each of the factors, and add those numbers to a set. Then, take the smallest number out of the set, multiply it by each factor, and put those numbers into the set. If you continue this way, you will eventually remove n numbers. The problem with this algorithm is that the set operations are fairly expensive and although n is capped at 100,000, you may end up adding many more numbers to your set than that. However, there is a simple optimization that will make this algorithm run in time. Maintain a integer representing the largest number in the set. Once we have added a total of n numbers to the set (including those that we have subsequently removed from the set), we shouldn't add any more numbers that are larger than the largest current number. While there are a number of further optimization we could make, this one is enough, and is probably simplest to implement. ParkingUsed as: Division One  Level Three:
This problem required quite a combination of skills. You have to do
a breadth first search, a binary search, and bipartite matching.
First, you do a breadth first search to find the distance from each
car to each parking spot. Next, you put all of those distances into a
single sorted array, and do a binary search over this array. At each
step in the binary search, you want to find if the distance under
examination is large enough that all of the cars can reach parking
spots in that much time. To figure this out, you need to do bipartite
matching where the cars represent one side of the graph, and the
parking locations represent the other. When doing the matching, you
are only allowed to match a car to a parking space if the distance
from that car to the parking space is less than the distance under
consideration in the binary search part of the algorithm. 
