Get Time
high_school  Match Editorials
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 Problems

WinningTrick rate it discuss it
Used as: Level One:
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;
Returning negative values, and performing integer division are two potential errors that should be avoided.

CompositionTimeSignature rate it discuss it
Used as: Level Two:
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; 
    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 rate it discuss it
Used as: Level Three:
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) 
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,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);

By brett1479
TopCoder Member