JOIN
 Match Editorial
SRM 236
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 Problems

MassiveNumbers
Used as: Division Two - Level One:
 Value 250 Submission Rate 256 / 286 (89.51%) Success Rate 235 / 256 (91.80%) High Score mhykol for 247.80 points (2 mins 41 secs) Average Score 201.27 (for 235 correct submissions)

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.

Used as: Division Two - Level Two:
 Value 500 Submission Rate 183 / 286 (63.99%) Success Rate 146 / 183 (79.78%) High Score Serpent for 488.07 points (4 mins 27 secs) Average Score 326.12 (for 146 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 194 / 207 (93.72%) Success Rate 185 / 194 (95.36%) High Score tomek for 248.45 points (2 mins 14 secs) Average Score 203.01 (for 185 correct submissions)

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.

ComputerExpert
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 43 / 286 (15.03%) Success Rate 28 / 43 (65.12%) High Score Vintik for 710.62 points (19 mins 55 secs) Average Score 533.93 (for 28 correct submissions)

This was a good problem to use your language's built-in 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();
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])){
}
}
}
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:
 Value 500 Submission Rate 97 / 207 (46.86%) Success Rate 59 / 97 (60.82%) High Score tomek for 472.49 points (6 mins 56 secs) Average Score 323.23 (for 59 correct submissions)

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.

Parking
Used as: Division One - Level Three:
 Value 1000 Submission Rate 27 / 207 (13.04%) Success Rate 9 / 27 (33.33%) High Score tomek for 632.89 points (24 mins 54 secs) Average Score 522.37 (for 9 correct submissions)

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.

If you were efficient when it came to writing your matching algorithm, you could probably get away without using the binary search, but it is safer to use it, since its probably the fewest lines of the whole thing.

By lbackstrom
TopCoder Member