Match Editorial

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

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

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