Match summary

Forty-eight contestants from the United States, Canada, Mexico and Poland were registered for this round. Penguincode was the first to submit a correct solution for the 250-point problem, and the first to advance to the next round. The 250 was fairly elementary, however, and all contestants solved it, earning them all a shot at the next round. Ten coders successfully solved all three problems. msg555 earned 175 points during the challenge phase, which put him over the top with 1778.66 points in total. gurugan1 took second place with 1704.90 points, and vlad_D came in third with 1670.45 points.

The Problems

SearchDisks

Used as: Division One - Level One:

Value 250

Submission Rate 47 / 47 (100.00%)

Success Rate 47 / 47 (100.00%)

High Score Penguincode for 249.37 points (1 mins 26 secs)

Average Score 231.99 (for 47 correct submissions)

This was a really easy problem, and all contestants solved SearchDisk correctly. The most difficult part of the solution is the parsing of the string. Some of the contestants wrote their own parser, but it is possible to use the standard function split.


public class SearchDisks { 
    public int numberToTakeOut(String diskNames, String searchingDisk) { 
        String[] diskNamesArray = diskNames.split(" "); 
        int res = diskNamesArray.length; 
        for(String curDisk : diskNamesArray) { 
            --res; 
            if (curDisk.equals(searchingDisk)) { 
                return res; 
            } 
        } 
        return -1; 
    } 
}

TwoTrains

Used as: Division One - Level Two:

Value 500

Submission Rate 44 / 47 (93.62%)

Success Rate 39 / 44 (88.64%)

High Score msg555 for 495.09 points (2 mins 50 secs)

Average Score 400.13 (for 39 correct submissions)

To solve this problem it was enough to find the time when the next trains to NewVasyuki and OldVasyuki come. Here is one solution:


public class TwoTrains { 
    public int passengerNewVasyuki(int t1, int t2, int[] timeCome) { 
        int ans = 0; 
        for(int time : timeCome) { 
            int nextTrain1 = 0, nextTrain2 = 0; 
            while (nextTrain1 < time) nextTrain1 += t1; 
            while (nextTrain2 < time) nextTrain2 += t2; 
            if (nextTrain1 <= nextTrain2) ++ans; 
        } 
        return ans; 
    } 
}

CrazyCompetition

Used as: Division One - Level Three:

Value 1000

Submission Rate 33 / 47 (70.21%)

Success Rate 10 / 33 (30.30%)

High Score gurugan1 for 893.41 points (10 mins 3 secs)

Average Score 750.14 (for 10 correct submissions)

First it is necessary to convert input to int[]:

int[] readTemperature(String[] temperature) { 
    int len = 0; 
    for(String s : temperature) { 
        len += s.length(); 
    } 
    int[] tem = new int[len]; 
    len = 0; 
    for(String s : temperature) { 
        for(char c : s.toCharArray()) { 
            if (Character.isLowerCase(c)) { 
                tem[len++] = c - 'a' + 1; 
            } else if (Character.isUpperCase(c)) { 
                tem[len++] = -(c - 'A' + 1); 
            } else tem[len++] = 0; 
        } 
    } 
    return tem; 
}

To solve this problem you could iterate over all possible beginnings of the Winter and Summer phases of "Crazy Competition" and choose the best variant. This is a rather slow method, though. The easiest way to make it quick enough is to calculate partial sums.
In other words, find int[] sum (sum[i] = tem[0] + tem[1] + ... + tem[i - 1]). Now calculate (tem[l] + tem[l + 1] + ... + tem[r - 1]) and calculate (sum[r] - sum[l]):

public double differenceTemperature(int daysSummer, int daysWinter, String[] temperature) { 
    double res = -Double.MAX_VALUE; 
    int[] tem = readTemperature(temperature); 
    int n = tem.length; 
    int[] sum = new int[n + 1]; 
    sum[0] = 0; 
    for(int i = 0; i < n; ++i) { 
        sum[i + 1] = sum[i] + tem[i]; 
    } 
    for(int startSummer = 0; startSummer + daysSummer <= n; ++startSummer) { 
        double summerTemperature = (double)(sum[startSummer + daysSummer] - sum[startSummer]) / daysSummer; 
        for(int startWinter = 0; startWinter + daysWinter <= startSummer; ++startWinter) { 
            double winterTemperature = (double)(sum[startWinter + daysWinter] - sum[startWinter]) / daysWinter; 
            res = Math.max(res, summerTemperature - winterTemperature); 
        } 
        for(int startWinter = startSummer + daysSummer; startWinter + daysWinter <= n; ++startWinter) { 
            double winterTemperature = (double)(sum[startWinter + daysWinter] - sum[startWinter]) / daysWinter; 
            res = Math.max(res, summerTemperature - winterTemperature); 
        } 
    } 
    return res; 
}

By VitalyGoldstein
TopCoder Member