Monday, February 26, 2007 Match summaryForty-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 ProblemsSearchDisksUsed as: Division One - Level One:
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:
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:
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; } |
|