Qualification 2 August 1617, 2005 Match summary The easy, VariableAddition, required coders to simulate a simple calculator. The hard, CheapestFlights, was a recursive shortest path problem. Most coders received credit for the easy, but many div 2 coders were stumped by the hard. Snail and Im2Good took the top 2 spots with scores over 900. The ProblemsVariableAdditionUsed as: Division One  Level One:
Here we must add a string of values, some of which may be variables. First we use the '+' symbols to split the string into tokens. Then we process each token. Integers are parsed and accumulated. Nonintegers cause us to perform a lookup in the list of variables. Java code follows: public int add(String eq, String[] vars) { String[] toks = eq.split("[+]"); int ret = 0; for (int i = 0; i < toks.length; i++) { if (Character.isDigit(toks[i].charAt(0))) { ret += Integer.parseInt(toks[i]); } else { for (int j = 0; j < vars.length; j++) if (vars[j].split(" ")[0].equals(toks[i])) ret += Integer.parseInt(vars[j].split(" ")[1]); } } return ret; }CheapestFlights Used as: Division One  Level Three:
This is a classic recursion problem. We have a cost matrix, a current location, a final location and N, the number of steps that must be taken. If N = 0, the problem is trivial. If we are at the final location we have a cost of 0. Otherwise, we return a very large value denoting something wrong has occurred. If N > 0, we can try all possible flights. Each flight leaves us with an updated cost matrix, a new current location, and N1 remaining steps. A recursive call solves the N1 case. Adding to this the cost of the initial flight, we get the total cost. Taking the minimum of all possible total costs (1 for each flight choice) gives the result. Java code follows: public double getLowest(String[] prices, int start, int end, int num) { double[][] mat = new double[prices.length][prices.length]; for (int r = 0; r < prices.length; r++) for (int c = 0; c < prices.length; c++) mat[r][c] = prices[r].charAt(c)'0'; return getLowest(mat,start,end,num); } public double getLowest(double[][] prices, int start, int end, int num) { if (num == 0) return end == start ? 0 : 1000; double ret = 1000; for (int i = 0; i < prices.length; i++) { if (i == start) continue; double cost = prices[start][i]; for (int j = 0; j < prices.length; j++) prices[j][i] /= 2; ret = Math.min( ret, cost + getLowest(prices,i,end,num1)); for (int j = 0; j < prices.length; j++) prices[j][i] *= 2; } return ret; }As an optimization, we can store the number of flights that arrive at a location in an integer array, and then compute the cost of a particular flight as needed. This saves us from recomputing the entire cost matrix. 
