|
Match Editorial |
Monday, November 21, 2005
Match summary
This match featured an exciting competition with versatile problems, great challenging opportunities and cool iPods.
In Div1, the top scores were quite impressive. Out of the 14 coders who solved all three problems, Petr was
a clear winner with a score of 1483.76. With this victory, he raised his rating once more, at an all-time best of 3457. The
yellow coder soul-net did also have an outstanding performance, taking the second place. Andrew_Lazarev
came in the third, followed by sjelkjd and rem .
As Petr, Eryx and ploh preferred to hide in room 6 for the ultimate target confrontation, coders
of different colors took over the other rooms. The most notable of them, lucab, who won room 1, has boosted
his rating with 552 points.
The challenge phase was bitter sweet. Many coders, some of them new to challenging, experienced the joy of unleashing
an arsenal of successful challenges. This, of course, came at the cost of those who lost their submissions. As system testing
finished the job, only a little more than half the total number of submissions in Div1 were still standing.
In Div2, there were 17 coders who solved all three problems. The first place was taken by Minny . He was
followed by slavejovanovski, colesbury, alberto and the newcomer edans.
The Problems
AimToTen
Used as: Division Two - Level One:
Value 250 Submission Rate 314 / 334 (94.01%) Success Rate 290 / 314 (92.36%) High Score Tisho for 249.62 points (1 mins 6 secs) Average Score 220.05 (for 290 correct submissions)
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:
Value 500 Submission Rate 101 / 334 (30.24%) Success Rate 54 / 101 (53.47%) High Score Minny for 370.92 points (18 mins 8 secs) Average Score 254.70 (for 54 correct submissions)
Value 250 Submission Rate 318 / 352 (90.34%) Success Rate 242 / 318 (76.10%) High Score Petr for 238.05 points (6 mins 25 secs) Average Score 183.64 (for 242 correct submissions)
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:
vectorPrisonCellsharvest(vector<int> drops) { vector<int> data(100, 0); for (int i = 0; i < drops.size(); i++) Drop(data, drops[i] + 25); int first = 0; for (; first < data.size(); first++) if (data[first] > 0) break; int last = data.size(); for (; last >= 0 ; last--) if (data[last - 1] > 0) break; vector<string> result(*max_element(data.begin(), data.end()), string(last - first, '-')); for (int i = first; i < last; i++) for (int j = 0; j < data[i]; j++) result[j][i - first] = 'O'; return result; } void Drop(vector<int>& data, int position) { if (data[position + 1] < data[w]) {Drop(data, position + 1); return;} if (data[position - 1] < data[w]) {Drop(data, position - 1); return;} data[position]++; }
Used as: Division Two - Level Three:
Value 1000 Submission Rate 78 / 334 (23.35%) Success Rate 40 / 78 (51.28%) High Score Luffy_ for 905.00 points (9 mins 24 secs) Average Score 621.71 (for 40 correct submissions)
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.
- First of all, if there are too many prisoners, it is pretty obvious that you cannot place them all such that every one of the
distances is greater than 1. If you take the prison cells as squares on a chessboard, you can be sure that the minimum
distance is at least 2 as long as you can place the prisoners in squares of the same color. If there are more prisoners than
white squares or black squares, you should simply return 1.
- By studying example 2 more carefully, another observation can be made. In this example you have to place 4 prisoners
on a 4 * 4 grid. The answer is 3, but it becomes pretty obvious that you cannot place any more prisoners, without decreasing
the minimal distance. And because 4 * 4 is the highest possible input we can deduct that for 5 prisoners or more, the
minimum distance is at most 2.
- Finally, if there are 4 or less prisoners to place, the most intuitive solution is to place them on the edge of the grid. This
can be proven by applying the properties of Manhattan distance.
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 brute-forced by checking all 2m*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:
Value 500 Submission Rate 183 / 352 (51.99%) Success Rate 52 / 183 (28.42%) High Score Im2Good for 453.84 points (9 mins 15 secs) Average Score 319.91 (for 52 correct submissions)
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.
Let's consider the following example:
startPosition = 50
endPosition = 100
orbs = {10, 20, 30, 40, 60, 70, 80, 90}
If we want to reach the orb at location 30 in 5 moves, we also need to reach the orbs at locations 40, 60, 70 and 80,
respectively (the orb at location 20, as well as the orb at location 90, are unreachable in this case).
The minimum amount of time to reach an orb equals the minimum amount of time to reach the previous orb + the time
needed to travel between these last two orbs. In the previous example, we can find the shortest time to reach the orb
at location 30 in 5 moves by looking at the shortest time needed to reach the orb at location 40 in 4 moves and the orb at
location 80 in 4 moves (in the second case the orb at location 40 is reached before the orb at location 80).
One way to represent the solution is to declare two matrices tl and tr, where tl[i][j] denotes the amount of time we need to
reach the i-th orb to the left of startPosition in j moves and tr[i][j] denotes the amount of time we need to reach the i-th orb to
the right of startPosition in j moves. In the code below I first built and sorted the two matrices, after which I determined for
each orb the time needed to reach it in a certain amount of moves. In the end, I took the minimum of the times needed to
reach the orb at endPosition.
Another way of solving this problem is memoization.
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[i-1][k-1] + uT * Math.abs(left[i] - left[i-1]));
}
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[i-1][k-1] + uT * Math.abs(right[i] - right[i-1]));
}
}
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:
Value 900 Submission Rate 79 / 352 (22.44%) Success Rate 40 / 79 (50.63%) High Score Petr for 712.14 points (15 mins 28 secs) Average Score 508.27 (for 40 correct submissions)
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.
