|
Match Editorial |
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.
In Division 1, Egor took home his first SRM win, followed by bmerry and Yarin.
Petr came in the 4-th, after losing his points on the easy problem. But ExploringEuropa was an easy
mission for Sputnik, a former blue, who managed to get the 9-th place.
In Division 2, the best performers were shd, .Invader and wildclaw.
The Problems
SwimmersDelight
Used as: Division Two - Level One:
Value 250 Submission Rate 300 / 396 (75.76%) Success Rate 91 / 300 (30.33%) High Score GMania for 226.99 points (9 mins 14 secs) Average Score 162.34 (for 91 correct submissions)
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:
Value 550 Submission Rate 29 / 396 (7.32%) Success Rate 7 / 29 (24.14%) High Score gy for 327.65 points (27 mins 44 secs) Average Score 275.60 (for 7 correct submissions)
Value 300 Submission Rate 142 / 302 (47.02%) Success Rate 81 / 142 (57.04%) High Score bmerry for 252.67 points (12 mins 48 secs) Average Score 153.28 (for 81 correct submissions)
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 case
For 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
- The time we found earlier is ensured by the existence of a vent. Thus, we are only looking for better alternatives.
- No matter the vent distribution, the probe always goes 2 * delay beyond the first vent detected.
- Ideally, you wish your probe to stop right at the next vent on its way back.
Getting the idea
In the following example, we consider surface = " S - - - V - V - - V - - - - " and delay = 4. The table below illustrates the real-time behavior of the probe. When a command takes effect on the probe, it is highlighted with yellow.| Probe location | S | S | S | S | S | - | - | - | V | - | V | - | - | V | - | - | - | - | - | V | - | - | V | |
| Incoming transmission | S | S | S | S | S | S | S | S | S | - | - | - | V | - | V | - | - | V | - | - | - | - | - | |
| Command issued | F | R | S |
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 code
public 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:
Value 900 Submission Rate 92 / 396 (23.23%) Success Rate 60 / 92 (65.22%) High Score gkv for 892.91 points (2 mins 32 secs) Average Score 627.55 (for 60 correct submissions)
Value 450 Submission Rate 254 / 302 (84.11%) Success Rate 227 / 254 (89.37%) High Score bmerry for 445.63 points (2 mins 49 secs) Average Score 374.18 (for 227 correct submissions)
This problem wasn't hard, and the most common approach was to compute the Z-value recursively. A Z-curve of order N is made up of 4 quadrants, each of them being a Z-curve of order N - 1. The easiest way is to translate the point of coordinates (r,c) to the upper-left quadrant, adding the total number of cells of every quadrant with lower Z-values.
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 base-2 bit strings. 
Multiply each character-digit of r with 2 and add 1 to it if its corresponding character in c is '1'. This is the Z-value, written in base 4. AntiChess
Used as: Division One - Level Three:
Value 1000 Submission Rate 28 / 302 (9.27%) Success Rate 6 / 28 (21.43%) High Score Egor for 570.14 points (29 mins 55 secs) Average Score 520.18 (for 6 correct submissions)
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:
- It is a two-person game in which the two players alternate making moves.
- There is a reciprocal assumption that each player plays optimally.
- The number of possible states is not very large.
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 bottom-up. 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 warm-up, 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:
- Check whether a square is occupied by a piece or not in constant time. For this, you need to declare a matrix, board [8][8], which retains the state of each square.
- Stop calculations if white can sacrifice all pawns present on the board.
- Apply partial memoization. This saves you from recursing to the same position more than once. Each pawn may have one of the following 8 states (rows 2 to 8, or captured). We cannot retain them all, but it is reasonable to only consider the cases when pawns are captured, or advance at most 3 rows from their initial position. You may assume the black queen to be on any of the 64 squares.
