Monday, June 26, 2006 Match summary The fourth HS SRM (the first for group delta) proved to be the trickiest thus far. Only two coders were able to solve the hard problem. lssi, the only competitor to solve all three, took first place with hml close behind. The ProblemsWinningTrickUsed as: Level One:
The wording of this problem cleverly hides the fact that all we care about is the fastest competitor. Once we know this maximum, we can compute exactly how much wind is needed. Remember that the wind both hurts the competitors and helps us, so only half the difference in speed is necessary. Java code follows: public double minimumSpeed(int[] speed, int yourSpeed) { int M = 0; for (int a : speed) M = Math.max(M,a); return yourSpeed >= M ? 0 : (MyourSpeed)/2.0; }Returning negative values, and performing integer division are two potential errors that should be avoided. CompositionTimeSignature Used as: Level Two:
Instead of dealing with fractions, we can simplify the problem by
assigning sixteenth notes a value of 1, eighth notes a value of 2, and
so forth. In addition, we assign the signature 3/8 a value of 6 (3*2), 2/4 a value of 8 (2*4), and so forth. public String getTimeSignature(String duration) { String poss = "WHQES", rets[] = {"3/8","2/4","3/4","4/4"}; int[] vals = {16,8,4,2,1}, lens = {6,8,12,16}; boolean[] bad = new boolean[4]; int cnt = 0, tot = 0; for (char c : duration.toCharArray()) tot += vals[poss.indexOf(c)]; for (int i = 0; i < 4; i++) if (tot % lens[i] != 0) { //check divisibility bad[i] = true; cnt++; } if (cnt == 4) return "?/?"; //all signatures are bad int ret = 1, best = 1000; for (int a = 0; a < 4; a++) { if (bad[a]) continue; //skip bad signatures int score = 0, len = lens[a], acc = 0; for (char c : duration.toCharArray()) { //simulate composition acc += vals[poss.indexOf(c)]; if (acc / len > 0) //passed a measure if (acc % len != 0  acc / len > 1) score++; acc %= len; } if (score < best) { best = score; ret = a; } } return rets[ret]; }One tricky implementation issue is forgetting to check for notes that are longer than the measures (above we check acc / len > 1). ProductionOptimization Used as: Level Three:
If you can spot it, the solution using memoization is easy to code and understand. We first define the following function: int mem(int idx, int totCost, int totTime, int[] costs, int[] times)Given the unit we are up to (idx), the amount we have left to spend (totCost), and the time left (totTime), this function returns the greatest number of "final" units we can make. We must build at least 1 unit, so we immediately expend costs[idx] and times[idx]. At this point, our process splits. In parallel we can now continue building units of type idx and, at the same time, use the last built unit to construct units of type idx+1. What isn't clear is how much of the remaining cost should be split between the two parallel processes. So, we try every possible split. Java code follows: int[][][] cache = new int[50][101][101]; int mem(int idx, int totCost, int totTime, int[] costs, int[] times) { if (idx == costs.length) return 1; if (cache[idx][totCost][totTime] > 1) return cache[idx][totCost][totTime]; int ret = 0, newTime = totTime  times[idx], newCost = totCost  costs[idx]; //If there is not enough time to build a unit, we are done if (newTime < 0) return cache[idx][totCost][totTime] = 0; //Try all possible cost splits for (int c = 0; c < newCost; c++) { int k = mem(idx+1,c,newTime,costs,times)+mem(idx,newCostc,newTime,costs,times); ret = Math.max(ret,k); } return cache[idx][totCost][totTime] = ret; } public int getMost(int[] costs, int[] times, int totCost, int totTime) { //Initialize cache for (int[][] a : cache) for (int[] b : a) Arrays.fill(b,1); return mem(0,totCost,totTime,costs,times); } 
