Match Editorials

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 Problems

Value	250
Submission Rate	109 / 111 (98.20%)
Success Rate	82 / 109 (75.23%)
High Score	sluga for 249.08 points (1 mins 44 secs)
Average Score	230.39 (for 82 correct submissions)

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 : (M-yourSpeed)/2.0;
}

Value	500
Submission Rate	68 / 111 (61.26%)
Success Rate	19 / 68 (27.94%)
High Score	nordom for 415.71 points (13 mins 21 secs)
Average Score	299.63 (for 19 correct submissions)

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.

As the first step, we sum all of the values for the given composition, and determine whether they are evenly divisible by each signature. Any signatures that do not divide can be discarded. Looping over the remaining signatures, we simulate each composition, and count how many notes cross measures. This determines our return value. Java code follows:

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

Value	1100
Submission Rate	13 / 111 (11.71%)
Success Rate	2 / 13 (15.38%)
High Score	hml for 706.19 points (24 mins 16 secs)
Average Score	589.74 (for 2 correct submissions)

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) 

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,newCost-c,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);
}