JOIN
 Match Editorial
2005 TopCoder Open
Qualification 2

August 16-17, 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 Problems

VariableAddition
Used as: Division One - Level One:
 Value 250 Submission Rate 314 / 347 (90.49%) Success Rate 293 / 314 (93.31%) High Score antimatter for 248.25 points (1 mins 54 secs) Average Score 194.67 (for 293 correct submissions)

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. Non-integers 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:
 Value 750 Submission Rate 204 / 347 (58.79%) Success Rate 135 / 204 (66.18%) High Score Snail for 698.73 points (6 mins 15 secs) Average Score 435.63 (for 135 correct submissions)

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 N-1 remaining steps. A recursive call solves the N-1 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,num-1));
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.

By brett1479
TopCoder Member