Match Editorial

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

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.

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)

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.

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();
    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;
}

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.

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.