Saturday, August 28, 2004 Match summary In division 1, many coders were quick to submit the first two problems, but took their time on the hard problem. System tests then saw 13 coders solve all three problems correctly, one of them being Vigothebest, who gains 275 rating points and no longer feels blue. Eryx won the division by a comfortable margin of over 140 points, having the fastest submission time on both the medium and the hard problem. Division 2 was a close race, with algorithmus_ua winning with only 2.54 points ahead of chaochao.
The ProblemsMovingAveragesUsed as: Division Two  Level One:
Calculating the nmoving averages for the times given proved to be no problem for the vast majority of coders. For each average to be calculated, loop through and add up the times that need to be considered for that average and do not forget to divide at the end. C++ vector<int> calculate(vector<string> times, int n) { vector<int> result; for (int i=0; i<(int)times.size()n+1; i++) { int seconds = 0, h, m, s; for (int j=i; j<i+n; j++) { sscanf(times[j].c_str(), "%d:%d:%d", &h, &m, &s); seconds += 3600*h + 60*m + s; } result.push_back(seconds/n); } return result; }MedalTable Used as: Division Two  Level Two: Used as: Division One  Level One:
In this problem an Olympic medals table has to be created from the results given. While this was not difficult to understand, this problem required quite some work. There were basically three steps to do: Accumulate the medals for each country, sort them by the criteria given and finally assemble the strings that are to be returned. Some coders were able to show off their language proficiency. Snapdragon for example makes nice use of vector<pair<vector<int>,string> > in his short C++ solution that can be found in the practice room. Java class SortEntry implements Comparable { int[] medal = new int[]{0, 0, 0}; String country; SortEntry(String c) { country = c; } public int compareTo(Object o) { SortEntry e = (SortEntry)o; for (int i=0; i<3; i++) if (medal[i] != e.medal[i]) return e.medal[i]  medal[i]; return country.compareTo(e.country); } } public String[] generate(String[] results) { Map m = new TreeMap(); for (int i=0; i<results.length; i++) { String[] s = results[i].split(" "); for (int j=0; j<3; j++) { SortEntry entry; if (m.containsKey(s[j])) entry = (SortEntry)m.get(s[j]); else entry = new SortEntry(s[j]); entry.medal[j]++; m.put(s[j], entry); } } SortEntry[] se = (SortEntry[]) m.values().toArray(new SortEntry[0]); Arrays.sort(se); String[] res = new String[se.length]; for (int i=0; i<se.length; i++) res[i] = se[i].country + " " + se[i].medal[0] + " " + se[i].medal[1] + " " + se[i].medal[2]; return res; }LoadBalancing Used as: Division Two  Level Three:
To achieve the fastest running time, the input chunks have to be
distributed between the two CPUs as evenly as possible. The first
thing to be noticed is that the input sizes may be divided
by 1024 to be able to work with smaller numbers. Then it is just a
standard problem (knapsack) of dynamic programming, where you loop through the
chunks and keep track of the sizes that can be achieved with the
chunks used so far. You may want to take a look at vorthys' feature
on dynamic programming for an indepth explanation. C++ int minTime(vector<int> chunkSizes) { vector<int> dp(204801, 0); dp[0] = 1; int total = 0; for (int i=0; i<(int)chunkSizes.size(); i++) { total += chunkSizes[i]/1024; for (int j=204800; j>=0; j) if (dp[j] == 1) dp[j+chunkSizes[i]/1024] = 1; } for (int i=(total+1)/2; true; i++) if (dp[i] == 1) return 1024 * i; }TopCan Used as: Division One  Level Two:
This is an optimization problem that can be solved by differential calculus.
Apparently TopCoders know their math better than the problem writer expected
since most of them were able to solve this problem rather quickly. (I) V = h * PI * r^2 (II) S = 2 * PI * r * (r + h)Solve (I) for h and substitute h in (II). (III) h = V / (PI * r^2) (IV) S(r) = 2 * PI * r^2 + 2 * V / rTake the derivative of S(r) with respect to r. (V) S'(r) = 4 * PI * r  2 * V / r^2 (VI) S''(r) = 4 * PI + 4 * V / r^3Set S'(r) = 0 to find the extremal value and assure yourself that this is indeed a minimum by stating that S''(r) > 0 for all r > 0. (VII) 0 = 4 * PI * r  2 * V / r^2 <=> 4 * PI * r = 2 * V / r^2 <=> 4 * PI * r^3 = 2 * V <=> r^3 = V / (2 * PI) (VIII) <=> r = cuberoot(V / (2 * PI))So we can calculate r with the help of (VIII), then h with (III) and finally the minimal surface area with (II). That is the solution most coders developed. Others like snewman performed a search to find the minimum surface area. Java public double minSurface(int volume) { double r = Math.pow(volume / (2 * Math.PI), 1.0/3.0); double h = volume / (Math.PI * r * r); return = 2 * Math.PI * r * (r + h); }CaseysArt Used as: Division One  Level Three:
This problem asked for the number of tilings of a rectangle by
the right tromino. It can be solved using dynamic programming
in O(length * width * 2^width). C++ double howMany(int length, int width) { vector<vector<double> > dp(width+1, vector<double>(1<<(width+1), 0)); dp[0][0] = 1; for (int row=0; row<length; row++) { for (int col=0; col<width; col++) { for (int mask=0; mask<(int)dp[col].size(); mask++) { int j0 = 1 << (col1); // previous position in current row int j1 = 1 << col; // position in current row int j2 = 1 << (col+1); // next position in current row int nxt = mask & (j21); // only bits set in next row int cur = (mask ^ nxt) >> 1; // only bits set in current row // bits 0 to i of mask hold bits 0 to i of next row // bits i+1 to width of mask hold bits i to width1 of current row if (cur & j1) // (row,col) already filled? { // move value one column forward dp[col+1][nxt  (cur^j1)<<1] += dp[col][mask]; } else // place trominos { int newcur = cur << 1; if (col+1 < width && (cur & j2) == 0) // (row,col+1) free? { if ((j1 & nxt) == 0) // (row+1,col) free? { // Xx // x int newnxt = nxt  j1; dp[col+2][newnxtnewcur] += dp[col][mask]; } // (row+1,col+1) is free // Xx // x int newnxt = nxt  j2; dp[col+2][newnxtnewcur] += dp[col][mask]; } if ((j1 & nxt) == 0) { if (col > 0 && !(j0 & nxt)) // (row+1,col1) free? { // X // xx int newnxt = nxt  j1  j0; dp[col+1][newnxtnewcur] += dp[col][mask]; } if (col+1 < width) { // (row+1,col+1) is free // X // xx int newnxt = nxt  j1  j2; dp[col+1][newnxtnewcur] += dp[col][mask]; } } } } } // values of completed row are the values at the // start of the next row for (int i=0; i<((int)dp[0].size()>>1); i++) dp[0][i<<1] = dp[width][i]; for (int i=1; i<=width; i++) for (int j=0; j<(int)dp[i].size(); j++) dp[i][j] = 0; // empty the rest } return dp[0][0]; }See Yarin's SRM solution for an implementation of a similar approach while using memoization. 
