Monday, November 21, 2005 Match summary
This match featured an exciting competition with versatile problems, great challenging opportunities and cool iPods.
The ProblemsAimToTenUsed as: Division Two  Level One:
The solution to this problem is straightforward. One could compute the average of the current grades and, in case it is lower than 9.5, add a grade of 10 and repeat this whole process. Some coders used a trick to avoid the possible inconveniences caused by double operations. They took the grades in the input array one by one and computed the number of 10's needed to get an average of 9.5 with each of them. Summing these up, we get the final answer. This can be implemented in the following way: public int need(int[] marks) { int n = marks.length; int score = 0; for (int i = 0; i < n; i++) score = score + (10  marks[i]) * 2  1; return Math.max(0, score); }FallingCoconuts Used as: Division Two  Level Two: Used as: Division One  Level One:
In this problem there are no shortcuts, you basically need to simulate the whole process. You start with the first coconut, determine its correct landing position, continue with the second, the third and so on. The most convenient representation for the already fallen coconuts is a matrix, or an array of Strings. As for the current falling coconut, you check it's neighbours to see whether it falls or slides in one direction or another. You continue to do so until the coconut reaches a place where it will not slide any further. C++ code follows: vectorPrisonCells Used as: Division Two  Level Three:
Although the constraints here are small, you can still time out if you are not too careful. There are a lot of ways to solve this
problem, but you can do it very easily by just making a few observations.
The observations above translate in the following code: public int scatter (int n, int m, int nr) { if (nr * 2 > n * m + 1) return 1; if (nr > 4) return 2; return (n + n + m + m  4) / nr; } This problem can be bruteforced by checking all 2^{m*n} possible cases (each cell can be either free or occupied). If total number of occupied cells is equal to nr, we compute the minimal distance between two prisoners and return the maximal result among all cases. SnakeTurbo Used as: Division One  Level Two:
This problem can be solved using the Dynamic Programming technique. A first observation to make is that it only makes
sense to turn around when you encounter an orb. Using this, we can define a move as a travel between two orbs.
To simplify coding, we can add two more orbs, one at startPosition and one at endPosition. Then, we could use the fact that
an orb cannot be reached, unless all the other orbs between startPosition and that particular orb have been reached. Thus, if
we know the number of moves we made to reach an orb, we also know what other orbs have been reached.
public double finishTime (int start, int end, int[] orbs) { double tl[][] = new double[100][100]; double tr[][] = new double[100][100]; int left[] = new int[100]; // here we will store the orbs to the left of startPosition, sorted in descending order int right[] = new int[100]; // here we will store the orbs to the right of startPosition, sorted in ascending order int n = orbs.length; int nl = 0; // the number of orbs to the left of startPosition int nr = 0; // the number of orbs to the right of startPosition // We also add an orb at endPosition, which is put either in left[], // or right[], according to its relative position from startPosition. tr[nr] = 2000000001; nr++; // sentinel to the right tl[nl] = 1000000001; nl++; // sentinel to the left for (int i = 0; i <= n; i++) tl[i][0] = tr[i][0] = 1000000002; double uT = 0.5; tl[0][0] = uT * Math.abs(start  left[0]); tr[0][0] = uT * Math.abs(start  right[0]); for (int k = 1; k <= n + 8 ; k++) { for (int i = 0; i <= k; i++) { int j = k  i  1; tl[i][k] = tr[i][k] = 1000000002; if (i < nl && j < nr) { if (j >= 0) tl[i][k] = Math.min (tl[i][k], tr[j][k  1] + uT * Math.abs(left[i]  right[j])); if (i > 0) tl[i][k] = Math.min (tl[i][k], tl[i1][k1] + uT * Math.abs(left[i]  left[i1])); } if (i < nr && j < nl) { if (j >= 0) tr[i][k] = Math.min (tr[i][k], tl[j][k  1] + uT * Math.abs(right[i]  left[j])); if (i > 0) tr[i][k] = Math.min (tr[i][k], tr[i1][k1] + uT * Math.abs(right[i]  right[i1])); } } uT /= 2; } // We now look at the orb we placed in endPosition and check in which move we obtained the best result. } }RobotCollision Used as: Division One  Level Three:
The easiest way to solve this problem is to take into account every possible start position for the first robot and every possible start position for the
second robot. Because the room limits are large (100 * 100), we must restrict our search to the cases when the robots start close enough to
produce a collision. Fortunately, each robot can receive at most 10 commands, so we only need to check the starting coordinates that are at most
20 units in Manhattan distance away from each other:
In the figure above, the red dot in the middle denotes the starting position of the first robot, Robbie. If Speedy doesn't start in one of the yellow squares, there won't be the possibility of a collision. The algorithm below also reduces the maximum needed distance between robots to produce a collision, as they move. For example, if there are only 5 more move commands to be executed, the robots need to be not more than 10 units in Manhattan distance away from each other. public boolean frontal (char dir1, char dir2) { if (dir1 == 'U' && dir2 == 'D') return true; if (dir1 == 'D' && dir2 == 'U') return true; if (dir1 == 'L' && dir2 == 'R') return true; if (dir1 == 'R' && dir2 == 'L') return true; return false; } boolean regularity (int px, int py, int n, int m) { return (px >= 20 && px < n  20 && py >= 20 && py < m  20); } public double probability (int n, int m, String c1, String c2) { double prob = 0; boolean regular = false; int intake = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!regular  !regularity(i, j, n, m)) { for (int ii = i  20; ii <= i + 20; ii++) { for (int jj = j  20 + Math.abs(i  ii); jj <= j + 20  Math.abs(i  ii); jj++) { if (ii < n && jj < m && ii >= 0 && jj >= 0) { int px1 = i, py1 = j, px2 = ii, py2 = jj, collision = 0; if (px1 == px2 && py1 == py2) collision = 1; // they start from the same point for (int k = 0; k < c1.length(); k++) { if (Math.abs(px1  px2) + Math.abs(py1  py2) > 2 * (c1.length()  k)) break; // Move Robbie here if (px1 == px2 && py1 == py2 && frontal(c1.charAt(k), c2.charAt(k)) ) collision = 1; // frontal collision // Move Speedy here if (px1 == px2 && py1 == py2) collision = 1; // they end up in the same point } if (collision == 1) { prob = prob + 1; if (regularity(i, j, n, m)) intake++; } if (regularity(i, j, n, m)) regular = true; } } } } else prob = prob + (double) intake; } } return (double) prob / (double) (n * m * n * m); } } You can significantly optimize your solution using the following observation. For every cell, compute the probability of a collision if Robbie starts from that cell. You can easily prove that this probability is the same for all cells further than 20 units from any border. Therefore you don't need to compute this probability for every such cell, instead you can compute it only once and multiply by the number of such cells. 
