|
Match Editorials |
Monday, January 15, 2007
Match summary
High school competitions are enjoying a steady level of popularity and, with an attendance of 159 participants, this match was no exception. The problems were not easy but, thanks to the many examples offered, most of the people who were able to submit a solution were rewarded with points. thoconracroi took top honors with an impressive score of 1493.00 points. He was followed close behind by msg555 with 1427.68 points, bhzhan with 1426.54 points and tamerlan92 with 1423.72 points. Rounding the top five, was TICKET_112022 with a score of 1394.43 points.The problems in this match also, somehow, revived some of the less discussed aspects of TopCoder experience. While being able to solve problems correctly is and should remain the main focus, there are other elements that may affect a coder's performance. Many of these fall in the cateogry of controlling the "uncontrollables" and require an inspired assessment of the situation.
For the first problem in the set, SwappingMarbles, vivekioiio quickly sent in a solution that was so simple, so neat and so wrong ... "return 0". While he didn't get too close to solving the problem, he was at least inspired in choosing the most universal value that a TopCoder problem could return. elmariachi1414 saw in it the potential for a challenge, so he chose example 2 in the problem statement, the only one that returned a 0. A lesson that many of us can learn from this is that no matter how heated the challenge phase may become, it is important to keep our composure and throw at least a one-second look on what's on the screen. This strategy pays off in the long run. While not all the wrong solutions are "return 0", quite a few of them present a particular area of interest for the challenger, and one quick look can make a big improvement in accuracy. Another thing to keep in mind is that attempting to challenge with an example test is usually a very bad idea. It is quite easy to preapare a fairly difficult test and copy it in the clipboard.
The second problem, ProbCalc, allowed for quite a lot of different solving methods. hmao's approach was quite an ingenious one, as he used the random() function. His code managed to survive to 6 challenges and through most of the system tests. To shuri's disappointment, his unsuccessful challenge was the very test for which hmao's problem failed the system tests. In shuri's case a few odd milliseconds may have made the difference between -25 and +50 points. As for hmao, he was probably hoping for a system test rerun. This was actually the first time I heard about such a scenario. For more details, you can look on the final paragraphs of the Understanding Probabilities article, which briefly discuss the advantages of using Randomized Algorithms and the prospect of challenging them.
The hard problem, ForestGarbage, gave a bit of headache to the experienced tomekkulczynski. A few minutes before the coding phase ended, he was in the top position. But he noticed a bug that, although hard to find with a bunch of random tests, could had easily been exploited by a challenge. The most conservative decision was to resubmit, and he probably did the right thing in doing so. Resubmitting whenever you find a bug in your code is almost always the best thing to do.
The Problems
SwappingMarbles
Used as: Division One - Level One:
The straightforward way to solve this problem is to check for every possible pair of marbles that can be swapped. As we choose one of these pairs, we consider the two marbles in the pair to be the middle points of the 3-marble groups formed together with their left and right neighbors. The Java code below shows the comparisons that need to be made:
Value 250 Submission Rate 132 / 159 (83.02%) Success Rate 128 / 132 (96.97%) High Score Weiqi for 247.48 points (2 mins 52 secs) Average Score 202.71 (for 128 correct submissions)
public int swaptions(String colors1, String colors2) {
int nsol = 0;
for(int i = 1; i < colors1.length() - 1; i++)
for(int j = 1; j < colors2.length() - 1; j++)
if(colors1.charAt(i-1) == colors2.charAt(j) && colors2.charAt(j) == colors1.charAt(i+1) &&
colors2.charAt(j-1) == colors1.charAt(i) && colors1.charAt(i) == colors2.charAt(j+1)) nsol++;
return nsol;
}
ProdCalc
Used as: Division One - Level Two:
Because of the small constraints, there were quite a lot of ways to approach this problem. The quickest way around was to use a recursive algorithm such as the one below:
Value 500 Submission Rate 65 / 159 (40.88%) Success Rate 45 / 65 (69.23%) High Score tomekkulczynski for 482.52 points (5 mins 26 secs) Average Score 357.63 (for 45 correct submissions)
long test = 1;
long solve(int digit, int n, int ops, long val) {
if (digit > 9 || val >= test) return -1;
if (ops == 0) return val;
long ret = solve(digit,n,ops-1,val*digit);
return Math.max(ret,solve(digit+1,n,ops,val));
}
public long highest(int d, int op) {
for (int a = 0; a < d; a++) test *= 10;
return solve(2,d,op,1);
}
}
Thinking of something a bit different, one could notice for example that multiplying by 9 is the same as multiplying by 3 two times. Thus, it is enough to only generate the prime factors up to 9. As every number has a unique prime factor decomposition: 2 ^ m2 + 3 ^ m3 + 5 ^ m5 + 7 ^ m7, we can just assign values to these factors and work our way out from there. There is a little wrinkle, however -- we also need to know if such a number can be obtained by applying exactly op operations. For a given 4-uple (m2, m3, m5, m7) we can do the following:
maxop = m2 + m3 + m5 + m7;
minop = m5 + m7 + m2 / 3 + m3 / 2;
if(m2 % 3 == 2 && m3 % 2 == 1) minop += 2;
else if(m2 % 3 > 0 || m3 % 2 > 0 ) minop += 1;
We finally need to check whether op is between minop and maxop, inclusive.
While the method above is quite efficient, there are also less sophisticated methods available. With just about 200 possible test cases, one could simply compute all the values with a much slower algorithm, and then just select the proper result from a list. This is a good trick to keep in mind.
As for using random algorithms to treat degenerate cases, or even figure out the multipliers, it is quite possible to make them work for a problem such as this - but since there are many cleaner solutions available, they should only be used as a last resort.
ForestGarbage
Used as: Division One - Level Three:
To solve this problem, we first need to correctly represent our search space. One method that comes to mind is to assign different costs to different paths we might take. There are three options available to us: walking in a free empty cell for a cost of 0 (note that we do not need to minimize the length of our path), walking in a cell that neighbors a garbage cell (for a cost of 1) and walking right into a garbage cell. We must ensure that the cost of walking through a garbage cell is greater than all the other potential costs combined. It can happen (as tomekkulczynski later noticed) that we may even need to visit about half the total number of cells instead of choosing a path with only 2 or 3 cells, out of which one is filled with garbage. Considering this, we can safely assign to a garbage cell a cost of 10000 (we should also be careful not to put too high a number, in order to avoid overflow).
Value 1000 Submission Rate 31 / 159 (19.50%) Success Rate 25 / 31 (80.65%) High Score nima.ahmadi for 765.89 points (16 mins 49 secs) Average Score 606.34 (for 25 correct submissions)
After having all the costs represented, we can retain for every cell the minimal cost needed to reach it from the starting cell. As the constraints are not so large, one could solve this problem by computing all these costs step by step (after 1 step, after 2 steps, and so on ...) until we are sure no more changes are being made. Java code follows:
public int[] bestWay(String[] forest) {
int a[][] = new int[51][51];
int b[][] = new int[51][51];
int c[][] = new int[51][51];
int sol[] = new int[2];
int n = forest.length;
int m = forest[0].length();
int MAX = 10000 * 10000;
int fx = -1, fy = -1;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++) {
a[i][j] = MAX;
if(forest[i].charAt(j) == 'S') {
a[i][j] = 0; c[i][j] = 0;
}
if(forest[i].charAt(j) == 'F') {
fx = i; fy = j; c[i][j] = 0;
}
if(forest[i].charAt(j) == 'g') c[i][j] = 10000;
if(forest[i].charAt(j) == '.') {
c[i][j] = 0;
if(i>0 && forest[i-1].charAt(j) == 'g') c[i][j] = 1;
if(i0 && forest[i].charAt(j-1) == 'g') c[i][j] = 1;
if(j0 && c[i][j] + a[i-1][j] < b[i][j]) b[i][j] = c[i][j] + a[i-1][j];
if(i0 && c[i][j] + a[i][j-1] < b[i][j]) b[i][j] = c[i][j] + a[i][j-1];
if(j
