Saturday, October 1, 2005 Match summary
SRM 266 posed a new challenge to the daring competitors. What appeared to be an easy in Division 1, turned
out to actually give more trouble than the medium. The same happened in Division 2, where only 7 people
solved the medium, but 60 got the hard! As this match tested one’s ability to adapt to a change of pace,
some experienced coders tried new strategies: after solving the medium, they opened the hard.
The ProblemsSwimmersDelightUsed as: Division Two  Level One:
Actually, you don’t need to carry a laptop to cross this river. As there are only 2 stones, the cases to consider are relatively few. Let’s denote the starting shore by X, the stones by A and B and the destination shore by Y. We have the following alternatives: X > A > B > Y X > B > A > Y X > A > Y X > B > YThe code below explores each of them: public int longestJump (int x[], int y[]) { double best = 10; for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1; j++) { double dist = x[i]; // first jump dist = max(dist, Math.hypot(x[i]  x[j], y[i]  y[j])); // second jump dist = max(dist, 10  x[j]); // third jump best = min(dist, best); } return best; } Note that X > B > B > Y is the same as X > B > Y.This can be easily adapted to 3 or 4 stones, but for a more general case you should use a variation of Floyd Warshall algorithm. The distance you were asked to compute in this problem is also known as the frog distance, or minimax distance. ExploringEuropa Used as: Division Two  Level Two: Used as: Division One  Level One:
Ah, NASA problems … This one required a bit of logical thinking, and the solution was not obvious.
The first thing we need to do is to start from the goal. The simple caseFor now we just consider the first vent. The probe is continuously moving, so the only option we have is to make it come back as soon as we know there is a vent there.As you can see in this image, the probe is 2 * delay away from the vent when it finally turns back. Thus, it takes another 2 * delay units of time for it to reach the vent. There is also a lag of delay units of time at the beginning, so the total time is T = 5 * delay + the position of this first vent. A few deductions
Getting the ideaIn the following example, we consider surface = " S    V  V   V     " and delay = 4. The table below illustrates the realtime behavior of the probe. When a command takes effect on the probe, it is highlighted with yellow.
After a short analysis, we find out that all the vents that are within delay units of time distance from the first vent discovered (the closest to 'S') can be approached directly, using the single reverse command at the beginning. For the remaining cases, we have to determine whether a second turn is less time consuming. Let's consider surface to be " S     V    V   V V    " and delay = 6. The green lines denote the probe's path if we aim for the vent at location 9. For this, only a single reverse command is needed, issued in the moment we receive the transmission that the probe has reached the vent at location 5. The blue lines denote the probe's path if we aim for the vent at location 12. For this, we issue another reverse command when the vent at location 12 is first encountered (the probe is on its way back, at location 16 then). The purple lines denote the probe's path if we aim for the vent at location 13. As you can see in the image above, the length of the purple path is 3 units longer than the length of the blue path. The source codepublic int travelTime (String surface, int delay) { int pos = 0; while (surface.charAt(pos) != 'V') pos++; int time = 5 * delay + pos; int best = time; for (int i = pos + 1; i < surface.length(); i++) { if (i – pos <= delay) time; else time = time + 3; if (surface.charAt(i) == 'V' && time < best) best = time; } return best; }Now you can enjoy the trip! ZCurve Used as: Division Two  Level Three: Used as: Division One  Level Two:
This problem wasn't hard, and the most common approach was to compute the Zvalue recursively. A Zcurve of order N is made up of 4 quadrants, each of them being a Zcurve of order N  1. The easiest way is to translate the point of coordinates (r,c) to the upperleft quadrant, adding the total number of cells of every quadrant with lower Zvalues. public int zValue(int N, int x, int y) { if (N == 0) return 0; int p = 1 << (N  1); int quarter = ((x >= p ? 2 : 0) + (y >= p ? 1 : 0)); return quarter * p * p + zValue(N  1, x % p, y % p); }Another approach is to convert r and c to base2 bit strings. Multiply each characterdigit of r with 2 and add 1 to it if its corresponding character in c is '1'. This is the Zvalue, written in base 4. AntiChess Used as: Division One  Level Three:
This problem can be solved with minimax trees, a pretty common concept in Game Theory. The following elements should usually hint to this kind of approach:
A minmax tree is a tree where the nodes represent the current status of the game and the arcs represent the moves. The game tree consists of all possible moves for the current players starting at the root and all possible moves for the next player as the children of these nodes, and so forth, as far into the future of the game as desired. The leaves of the game tree represent terminal positions  there, the outcome of the game is clear. Let's take an example, in which white is {"a7", "h7"} and black is "g7"  we write it as "a7, h7, Qg7". The diagram below gives the tree associated to this position: The value of an arc is the number of pawns that will be captured if we are going down on that branch. Arcs are assigned bottomup. With red are denoted the arcs representing the queen's moving alternatives. The minimum value of these arcs is the value of the blue arc connecting the parent node. With blue are denoted the arcs representing the pawns' moving alternatives. The maximum value of these arcs is the value of the red arc connecting the parent node (or the final answer, if we reached the root). If recursivity in ZCurve was just a warmup, this problem required a deeper understanding of the concept. You may either use indirect recursion, or make it all in the same function (but having an extra parameter to know whose turn is, and then treat the two cases separately). After tackling the daunt Here are a few possible optimizations that can be made:

