Our 2019 Code Jam to I/O for Women round was the first round using a redesigned UI — we know there were issues with loading the contest at the start of the round, but we hope you enjoyed solving the problems and had a smooth experience once the round began. Please don't hesitate to let us know if you encountered any issues by emailing codejamio@google.com.
Grid Escape and Parcel Posts were the two easier problems of the four, but both took some thought and had non-obvious edge cases. The formidable infinite field of Sheepwalking could be tamed with some algebra and memoization. War of the Words was our first interactive problem in Code Jam to I/O for Women, and it was quite fiendish even on top of the challenge of getting used to this problem type ‐ even the first test set was tough to pass!
We had over a thousand participants attempt at least one problem. In the first hour of the contest, we saw many solutions to our first two problems, but Sheepwalking and especially War of the Words proved to be tougher to crack. Only a handful of contestants earned any points on War of the Words, and nobody solved the second test set, but we saw some submissions get close! Over 60 contestants solved the first three problems, and 10 of those also solved test set 1 of War of the Words. Most contestants who got into top 150 either fully solved the first three problems or fully solved the first two with a small enough time penalty.
Thanks to everyone who participated — and congratulations to the top 150! We'll be in touch in the upcoming days, pending finalization of the results. We hope to see all of you again next year!
Cast
Grid Escape: Written by Ian Tullis. Prepared by Jonathan Irvin Gunawan.
Parcel Posts: Written by Ian Tullis. Prepared by Pablo Heiber.
Sheepwalking: Written by Ian Tullis. Prepared by Jonathan Irvin Gunawan.
War of the Words: Written by Ian Tullis. Prepared by Pi-Hsun Shih.
Solutions and other problem preparation and review by Shane Carr, Luis Hector Chavez, Md Mahbubul Hasan, Trung Thanh Nguyen, Lizzie Sapiro, Pi-Hsun Shih, Micah Stairs, Mary Streetzel, Dave Walker, Jeroen van Wolffelaar, and Adilet Zhaxybay.
Analysis authors:
You are designing a new "escape" adventure that uses a rectangular grid of rooms (unit cells) with R rows and C columns. Each room has four doors oriented in the four orthogonal directions of the grid: north, south, east, and west. The doors on the border of the grid lead outside, and all of the other doors lead to other rooms.
The adventure will be played by exactly R × C players, with each player starting in a different one of the R × C rooms. Once everyone is in position and the game starts, all of the doors close, and there is a mechanical trick: one of the four doors in each room can be opened from inside the room, and the other three doors cannot be opened. This remains consistent throughout the adventure; in a given room, it is always the same door that can be opened. Notice that it is possible that a door that connects two rooms might be able to be opened from one side but not the other.
Each player moves independently of all other players. Players can only go through doors that they opened themselves, and they must close doors behind them. Each player will keep going through doors until they go through a door that leads outside (and therefore they escape), or they have made R × C moves without escaping (at which point they are considered to have failed, and they do not escape).
You want to choose which door in each room can be opened, such that exactly
K of the players will be able to escape. Can you find a way to do
this, or determine that it is IMPOSSIBLE?
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line containing three integers R, C, and K, as described above.
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1) and y
is IMPOSSIBLE if there is no solution, or POSSIBLE
if there is. If there is a solution, output R more lines of C
characters each, representing the grid of rooms. The j-th character on the
i-th of these lines represents the room in the i-th row and j-th column of
the grid; each character must be either uppercase N,
S, E, or W, according to whether the
door that opens from that room is the one that leads north, south, east, or
west.
If multiple answers are possible, you may output any one of them.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set. (10 seconds per test run.)
Memory limit: 1GB.
1 ≤ R.
1 ≤ C.
0 ≤ K ≤ R × C.
1 ≤ (R × C) ≤ 8.
1 ≤ (R × C) ≤ 100.
|
Input |
Output |
2 2 3 2 1 1 0 |
Case #1: POSSIBLE SES SNW Case #2: IMPOSSIBLE |
In our solution for Sample Case #1, the two players who start in the westernmost two rooms will go south until they escape, whereas the four players who start in the other four rooms will travel between those rooms in an endless clockwise circle and cannot escape.
In Sample Case #2, there is only one room, so the player can definitely escape regardless of which particular door can be opened.
You just bought a parcel of land that is K kilometers long; it is so narrow that, for the purposes of this problem, we will consider it to be a polyline that runs from west to east, varying in elevation. You know the elevations of the land (in meters) at K + 1 regularly spaced measurement marks M0, M1, ..., MK. These marks are 0, 1, ..., K km, respectively, from the western end.
In this region, a wooden post denotes the boundary between two adjacent parcels of land. Wooden posts can only be placed at measurement marks, and there can be at most one post at each mark. Right now, there are two posts: one at the 0 km mark, and one at the K km mark. A measurement mark with a post is considered to be part of both of the parcels it demarcates, so your parcel of land includes all measurement marks between 0 and K km, inclusive.
A parcel is considered desirable if it contains three measurement marks such that the west-most and east-most of those three marks are both strictly higher than the remaining one of the three marks, or both strictly lower than the remaining one of the three marks. People like some variation in their landscapes! Notice that these three marks are not necessarily consecutive, and the west-most and east-most of the three marks are not necessarily the west-most and east-most marks of the parcel.
Consider an example with K = 5 and M0, M1, ..., MK = 5, 6, 6, 1, 2, 4. The measurement marks with elevations 5, 2, and 4 satisfy the condition, as do the measurement marks with elevations 6, 1, and 2. However, the measurement marks with elevations 6, 6, and 1 do not satisfy the condition, nor do the measurement marks with elevations 1, 2, and 4. Any three measurement marks that satisfy the condition make the whole parcel desirable; for example, a parcel containing the measurement marks 4 7 6 7 is desirable because of the first three values.
Your parcel is desirable, but you think it may be possible to extract even more value from it! You want to add additional posts to this parcel to divide it up into multiple parcels, all of which must be desirable, since you do not want to waste any land. What is the largest number of posts you can add?
The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line containing an integer K: the length, in kilometers, of your parcel of land. Then, there is one more line with K + 1 integers M0, M1, ..., Mk; where Mi is the elevation (in meters) at the measurement mark that is i km from the western end of your land.
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1) and y
is the largest possible number of posts you can add, as described above.
Time limit: 20 seconds per test set. (10 seconds per test run.)
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 ≤ Mi ≤ 1000, for all i.
(Mi - Mj) ×
(Mk - Mj) > 0,
for some i < j < k. (Your starting parcel is desirable.)
4 ≤ K ≤ 10.
4 ≤ K ≤ 1000.
|
Input |
Output |
4 4 4 8 7 3 5 4 4 8 7 7 5 7 1 2 2 1 2 1 2 1 6 2 1 3 10 9 12 20 |
Case #1: 1 Case #2: 0 Case #3: 2 Case #4: 1 |
In Sample Case #1, you can add one post at 2 km to get a total of two desirable parcels. The parcel from 0 to 2 km is desirable because 4 < 8 and 8 > 7. The parcel from 2 to 4 km is desirable because 7 > 3 and 3 < 5.
In Sample Case #2, there is no way to add another post. If you added one at 1 km or 3 km, one of the parcels would include only two measurement marks and could not be desirable. If you added one at 2 km, the parcel between 0 and 2 km would be desirable, but the parcel between 2 and 4 km would not.
In Sample Case #3, posts can be added at 3 km and 5 km.
In Sample Case #4, a post can be added at 2 km. Notice that the parcel from 2 km to 6 km is desirable because 10 > 9 and 9 < 12. However, there is no way to add a second post.
Bleatrix Trotter is a sheep who lives in a two-dimensional field that is an infinite grid of unit cells. Her home is in a unit cell that we denote as (0, 0) — that is, all coordinates are given relative to Bleatrix's home cell. However, because she has been sleepwalking, she is currently in the unit cell at the coordinates (X, Y) — that is, in a cell X columns east of, and Y rows north of, her home cell. The two sheepdogs who have been assigned to protect Bleatrix have just noticed that she is missing, and now they want to herd her back to her home cell.
Before each of Bleatrix's moves, the two sheepdogs can move to any grid cells that they want, except that they cannot both move to the same cell, and neither one can move to Bleatrix's current cell. Once the sheepdogs are in place, Bleatrix, who is sleepwalking, will make a random unit move in a direction that would not take her into a cell with a sheepdog. That is, she takes the set of four possible unit moves (north, south, west, east), discards any that would move her into a cell with a sheepdog, and then chooses uniformly at random from the remaining moves. Then the sheepdogs can position themselves again, and so on (notice that, unlike Bleatrix, the sheepdogs do not have to make unit moves).
Once Bleatrix arrives at her home at (0, 0), she stops sleepwalking, wakes up, and grazes peacefully, and does not make any more moves thereafter.
If the sheepdogs coordinate their movements to minimize the expected number of Bleatrix's moves to reach her home, what is that expected number?
The first line of the input gives the number of test cases, T. T test cases follow. Each case consists of one line with two integers X and Y, representing the coordinates of Bleatrix's starting cell, as described above.
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1) and y
is the expected number of Bleatrix's moves, as described above.
y will be considered correct if it is within an absolute or
relative error of 10-6 of the correct answer. See the Competing
section of the
FAQ
for an explanation of what that means, and what formats of real numbers we
accept.
Time limit: 20 seconds per test set. (10 seconds per test run.)
Memory limit: 1GB.
(X, Y) ≠ (0, 0).
1 ≤ T ≤ 48.
-3 ≤ X ≤ 3.
-3 ≤ Y ≤ 3.
1 ≤ T ≤ 100.
-500 ≤ X ≤ 500.
-500 ≤ Y ≤ 500.
|
Input |
Output |
1 -1 1 |
Case #1: 4.000000 |
Notice that the values of X and/or Y may be negative. An X value of -1, for example, means that the cell is one unit west of Bleatrix's home cell. (Similarly, a negative value of Y means the cell is south of Bleatrix's home cell.)
In the sample case, Bleatrix starts off one cell to the north of, and one cell to the west of, her home. Before she makes her first move, the two sheepdogs could position themselves in cells (-2, 1) and (-1, 2). Then, whichever direction she might choose, she would end up only one step away from her home… but the sheepdogs could not guarantee that she would go there on her next move! The remaining details are left for you to discover.
Finally, you are face to face with the leader of the alien robots! You have managed to distract it with its favorite word game, while your fellow Resistance members try to shut down the robots' power supply.
The game uses the robot language, which is made up of 105 words:
the set of all five-letter strings made up of uppercase English letters
between A and J, inclusive. For example,
AAAAA, FGHIJ, and BEIGE are among
the valid words.
You know that these words have a rank order, with no ties, such that a higher-ranked word beats any lower-ranked word, with the one exception that the lowest-ranked word beats the highest-ranked word. Unfortunately, you do not know the rank order of the words in the robot language!
The game has the following rules:
Thanks to some great work by the Resistance's spies, you know the strategy that the robot will use for every turn of the game. It only cares about scoring 100 points, so on every turn, it will choose a word uniformly at random from all possible words that will score a point on that turn, and independently of all of its previous word choices. The robot knows the rank order of the language, so it has no trouble choosing words!
If you do not score at least N points, the robot will become bored and stop playing with you, so your plan (and the universe) will be doomed!
This problem is interactive, which means that the concepts of input and output are different than in standard Code Jam problems. You will interact with a separate process that both provides you with information and evaluates your responses. All information comes into your program via standard input; anything that you need to communicate should be sent via standard output. Remember that many programming languages buffer the output by default, so make sure your output actually goes out (for instance, by flushing the buffer) before blocking to wait for a response. See the FAQ for an explanation of what it means to flush the buffer. Anything your program sends through standard error is ignored, but it might consume some memory and be counted against your memory limit, so do not overflow it.
In addition, sample solutions to a previous Code Jam interactive problem (in various languages) are provided in the Analysis section of this past problem.
Initially, your program should read a single line containing two integers T and N: the number of test cases, and the number of points you must score in each case. (Notice that the N parameter is the same for every test case in a test set.) Then, you need to process T test cases.
At the start of a test case, the judge chooses a rank order for the words in the robot language, uniformly at random from all such orders, and independently of any previous choices of rank order. (However, the judge uses a deterministic seed, so if your program is deterministic, its interaction with the judge will be the same even across submissions for this problem.)
At the start of a test case, you must output one line with a five-letter
string of uppercase English letters in the inclusive range A
through J: a valid word W0 in the robot language.
Then you will have 100 exchanges with the judge; the j-th of these
(counting starting from 1) proceeds as follows:
After you send your last word for a test case, your program should terminate if it was the last test case; otherwise, it should output a word to begin the next test case.
If your program outputs something wrong (e.g., gives an invalid word), the
judge will send -1 to your input stream and it will not send any
other output after that. If your program continues to wait for the judge after
receiving -1, your program will time out, resulting in a Time
Limit Exceeded error. Notice that it is your responsibility to have your
program exit in time to receive a Wrong Answer judgment instead of a
Time Limit Exceeded error. As usual, if the total time or memory is
exceeded, or your program gets a runtime error, you will receive the
appropriate judgment.
You should not send additional information to the judge after processing all test cases. In other words, if your program keeps printing to standard output after the last test case, you will get a Wrong Answer judgment.
1 ≤ T ≤ 50.
Time limit: 40 seconds per test set. (10 seconds per test run.)
Memory limit: 1GB.
Wi is five characters long and consists only of characters
in the set of uppercase letters ABCDEFGHIJ, for all odd i. (The
robot plays valid words.)
N = 25.
N = 50.
Notice that interactive problems do not have sample input and output like other Code Jam problems. Your code will not be run against samples, and the following interaction is just an example.
t, n = readline_int_list() // reads 50, 25 into t, n
// Before the case starts, the judge silently chooses a rank order for the
// 100000 words. Suppose that the word FADED is the lowest-ranked word,
// AHEAD is the highest-ranked word, and CAGED and HIGCJ are ranked
// such that FADED < CAGED < HIGCJ < AHEAD. As the contestant,
// though, we do not know this!
printline AHEAD to stdout // you name AHEAD as word 0. What luck!
flush stdout
robot_word = readline_str() // reads FADED into robot_word
printline CAGED to stdout // you name CAGED as word 2
flush stdout
robot_word = readline_str() // reads HIGCJ into robot_word
printline GAFFED to stdout // you name an invalid word as word 4
flush stdout
robot_word = readline_str() // reads -1 (judge has decided our solution is
// incorrect)
exit // exits to avoid an ambiguous TLE error
You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.
Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.
In the first test set, there can be at most 8 rooms in the grid. Each room
can have its working exit in any one of the four directions, so we can use
brute force to check all 48 possible ways to choose the 8
working exits, and see how many players escape from each possible layout.
Either we will find a solution, or we will show that the case is
IMPOSSIBLE.
In the second test set, we can no longer get away with an exhaustive approach! However, since we have some freedom in designing the grid, it's worth looking for a constructive solution.
If R = C = 1, then K = 0 is impossible, and any solution works for K = 1. Otherwise, imagine drawing a "snaking" path through all of the rooms of the grid, choosing our working doors to allow us to follow this path. We start in the northwesternmost cell of the grid, and move eastward through rooms until we reach the northeasternmost cell. (If C = 1, we will already be there and so we will not need to move.) Then we make one move south, and if we have not exited the grid, we move westward through rooms until we reach a cell on the western border. Then we make one more move south (if possible), and then move eastward, and so on, until one of our moves to the south exits the grid.
(By the way, a more obscure term for this type of winding path is boustrophedon, which derives from a way to direct oxen when plowing a field. Algorithms have been useful for a very long time!)
Notice that all of the players can escape along our path, no matter where they start. Now consider choosing some room along the path and "reversing" its working door — that is, choosing the door that opens onto the previous room on the path. Then every player who starts in that room or a room earlier than it along the path cannot escape — they will be trapped in an infinite loop! Every other player will still be able to escape just as before.
Since we can choose any room along the path, we can allow any desired number of players to escape... well, almost any number. If we try to use the above strategy to allow all but one of the players to escape, it breaks down because the very first room (where that player is) has no "previous room on the path".
In fact, we can never allow all but one of the players to escape. Consider the room with the one player who we want to prevent from escaping. One of their doors has to work, and it cannot open onto the outside world, so it must open onto another room. But that means that our player will share the fate of the player in that other room — either they will both be able to escape, or neither will.
So, if K = R × C - 1, the case is
IMPOSSIBLE, and for any other case, the above construction gets
us our answer. If K = R × C, we do not modify any
of the path’s doors; otherwise, to allow exactly K of the players to
escape, we "reverse" the door in the (K+1)-th-from-last room of the
path.
Many other approaches are possible. For example, we can design around the
target number of players who cannot escape. As long as that number is at
least two, we can create a "nucleus" of the trap in the upper left corner of
the grid: either an E room to the west of a W room,
or an S room to the north of an N room, depending
on our given dimensions. Then we can turn cells sharing rows with the
nucleus into Ws, cells sharing columns with the nucleus into
Ns, and other cells (scanning top-to-bottom, then left-to-right)
into Ws until our set of trapped rooms is large enough. The
remaining rooms can safely be filled with S. Alternatively,
we can use flood fill
to extend the sink.
Test set 1 has a small upper bound of only 10 for K, which leaves at most 9 places where a post can be placed. That means we can just try every one of the 29 = 512 combinations. For each one, check whether all of the produced parcels are valid, and if they all are, update a result if the number of posts in this option is larger than it. To check whether a parcel is valid, notice the condition is equivalent to checking if the list of elevations is not sorted non-decreasingly nor non-increasingly. We can do that by either sorting it in both ways and compare whether either is equal to the original, or check there exist two consecutive marks with one strictly lower than the other, and also two consecutive marks with one stricly higher than the other.
We can improve upon the exponential time required for the solution in the previous paragraph with the following insight: if a parcel between marks i and j is valid, so is any extension of it to a parcel between marks i-d and j+e for non-negative d and e. So, let i be the westernmost mark such that the parcel between marks 0 and i is valid and the parcel between i and K is valid. If there is not such an i, then the result is just 0 (no posts can be added). We can then prove that there is a way to place a maximum number of posts that places a post at mark i and not at any mark west of i. If that's true, a greedy algorithm follows: find such i, place a post there, and recursively try to place more posts within the [i, K] parcel. This algorithm takes O(K2) time if implemented as described, which is fast enough to solve this test set, but a linear time alternative is presented in the next paragraph.
To solve the problem in linear time, we scan the list of elevations from west to east, recording when we see consecutive marks in strictly increasing and strictly decreasing order. As soon as we have seen both, we found a potential i (we don't check if [i, K] is valid just yet, to save time). We add 1 to the result, reset whether we have seen markings in each order to false, and resume scanning (this is equivalent to the recursive step in the previous presentation). After the scan is complete, it's possible that the eastmost parcel is not valid (since we didn't check it), but we can check it by inspecting the value of the same two boolean variables showing whether we saw markings in each order since our last reset. If the westmost parcel is not valid, the last place we found for a post was not valid, so we subtract 1 from our running result. Notice that each time we find a place where we can place a new post, it means that all previously placed posts were valid. This takes a single linear pass and a constant number of updates and checks of 3 variables at each step (two boolean variables about having seen markings in each order, and the result), so the algorithm runs in linear time.
To prove the main proposition, notice first that the parcel between marks 0 and j for j < i is never valid by definition of i, so any valid placement of posts does not place a post at mark j < i. For the second part, since just i is a valid placement, there exists a non-empty valid placement. Let L = i1, i2, ..., im be the list of mark positions where posts should be added in a valid placement of a maximum number m of posts, in increasing order. Then, i ≤ i1 because of the first part, so we can define L' = i, i2, ..., im. Now we can show L' is also such a list, and one that has i as its westernmost post. L' has m posts by definition. The validity of L' follows because the parcel between marks 0 and i is valid by definition of i, and the parcel between i and i2 is an extension of the one between i1 and i2 (because i ≤ i1 from the previous part). All other parcels in L' are also parcels in L, and are therefore also valid, so L' is valid.
What is the most efficient way to herd Bleatrix from cell (X, Y) back to the "origin" cell (0, 0)? We will simplify our discussion by assuming that X and Y are both nonnegative; because Bleatrix's two-dimensional field is symmetric across both axes, our solutions can safely work with the absolute values of X and Y.
If Bleatrix is ever at a cell (x, y) such that x ≠ 0, and y ≠ 0 — that is, she is not along one of the two "axes" of cells — then two of her possible moves will take her toward the origin cell (reducing either her horizontal or vertical distance from it), and the other two will take her away from the origin. In this case, we should use the two sheepdogs to block the two "away" moves. Any move away from the goal in some direction would need to be reversed later on, costing us two moves. Moreover, we do not want to spend both sheepdogs to block opposite directions of movement (e.g., placing them to Bleatrix's left and right to force her to move either up or down), because then she would make a purely random horizontal or vertical walk, with no tendency toward the goal.
The only remaining case — apart from being at the origin and thus being done — is that Bleatrix is at a cell of the form (x, 0) or (0, y). That is, she is along one of the two main "axes" of unit cells; without loss of generality, we will suppose she is at a cell of the form (0, y).
We know from the argument above that we do not want to use both sheepdogs to force her to randomly walk along the y-axis, so we should use one sheepdog to block her movement along the y-axis away from the origin. But should we deploy the other sheepdog to block one of her moves perpendicular to the axis? If we do not, she will move toward the goal with probability ⅓ and perpendicular to it with probability ⅔; if we do, she will move toward or perpendicular to the goal with equal probability. Since moving toward the goal is better (again, any lateral move needs to be undone eventually), we should use the additional sheepdog. For convenience, we will always deploy it in a way that keeps both of her coordinates nonnegative — that is, below her if she is along the x-axis, and to the left of her if she is on the y-axis.
A more rigorous proof of the optimality of our strategy follows at the end of this analysis.
Now that we have a strategy, a natural approach is to simulate it and take the average of, say, a million runs. Test set 1 only includes nine distinct cases; the others are symmetric, differing only in signs and/or in which values are X and Y. How hard can it be to get those nine answers?
As it turns out: pretty hard! The problem is that the length of our random walk has very high variance, so it is hard to get a confident estimate of the true expected length. A straightforward simulation solution will either take too long or not meet the strict tolerance requirements of the problem. However, we can run simulations offline and inspect the results, and we might notice that the answers are always close to a value of the form A / 9, where A is some integer. This pattern will not hold up for X and Y values outside of the [-3, 3] range, but it can serve us well here — an offline simulation can get us close enough to the true answers that we can confidently guess the value of A for each case, and then submit a solution that packages up those answers.
It is also possible to solve Test set 1 by hand, using the same method that also leads to a solution for Test set 2...
Notice that the problem is "memoryless"; if Bleatrix moves to cell (x, y), the expected number of additional moves to reach the origin from there is the same as if she had begun at (x, y). So, to calculate the expected number of moves needed from a given starting point, we can use a series of recurrences. Let T(x, y) be the expected number of moves when starting from cell (x, y); trivially, T(0, 0) = 0. Let us consider our cases from above:
We can simplify the second recurrence by replacing T(1, y) with its representation from the first recurrence: ½ T(0, y) + ½ T(1, y-1) + 1. Then, after some algebra, the second recurrence simplifies to T(0, y) = ⅔ T(0, y-1) + ⅓ T(1, y-1) + 2. Now we are expressing T(0, y) only in terms of recurrences for smaller values of y. So, all told, for any starting cell, we have T(x, y)=
At this point, we can use recursion plus memoization — or some other form of dynamic programming — to quickly compute any answer we want. We will never need to evaluate T() for any particular cell more than once, so we have tamed the infiniteness and randomness inherent in the problem.
If we use, e.g., C++ doubles, might our solution fail due to
accumulated floating-point errors? This phenomenon is often worth worrying
about, but in this problem, it is not even close to posing a threat. The total
number of calculations needed is not very large — only a few per
recurrence. Even if our solution for e.g. the case 500 500
involves calculating the answer for every possible distinct test case
along the way, we will have at most a few million chances to introduce a
tiny amount of error. A standard double precision floating point number has
15 decimal digits of precision, but we only need the first 6 to be correct,
so even if our errors pathologically did not cancel each other out at all,
we would be fine.
Check out the answers for the cases 100 0, 100 1,
..., all the way up to 100 30. They are all (to nine decimal
places) the same: 201.500000000. The answer for 100 100 is
212.727275769. Why are these values so close? That is, if we compare starting
200 moves away from the goal at (100, 100) versus starting only 100 moves
away from the goal at (100, 0), why does the latter not help us very much?
Observe that, in our strategy, once Bleatrix has made enough left moves to reach the y-axis, her horizontal moves will alternate between right and left; once she has made enough down moves to reach the x-axis, her vertical moves will alternate between up and down. But regardless of where we are in the strategy, she has an equal probability of moving horizontally or vertically. Given that Bleatrix starts at (X, Y), we can be sure that she will reach the goal only after she has made at least X horizontal moves and at least Y vertical moves.
How many moves will it take until the first time at which both of those conditions are satisfied? Without loss of generality, let us assume that X ≥ Y. If X is much larger than Y, then by the time we get our X-th horizontal move, we will almost certainly have gotten Y vertical moves, so we can ignore Y. Then the expected number of moves needed to get X horizontal moves is 2X, since the probability of a horizontal move is ½. However, if X is not much larger than Y, or equal to Y, we cannot ignore Y, and it may take more than 2X moves in expectation for both conditions to be satisfied.
The above explains why the (100, 100) answer is larger than the (100, 0) answer. It also explains why it is not too much larger, since a large discrepancy would imply that it is very likely to get 100 moves in one direction long before getting 100 moves in the other direction.
However, why is the (100, 0) answer 201.5 rather than 2X = 200? Consider the first time at which we have at least X horizontal moves and at least Y vertical moves; call the number of moves M. We have just hit one of the axes for the first time, and we will be on the other axis (and thus done) if M matches the parity of X + Y, or one cell away otherwise. We know that T(0, 1) = T(1, 0) = 3; for large X + Y, we would expect parity effects to even out, so this final herding process should add ½(3) = 1.5 more moves to the expected total.
Also note that even though our chosen precision level obscures it, the (100, 0) answer is in fact slightly smaller than the (100, 1) answer, and so on.
T(0, 0) = 0, and for any other (x0, y0), T(x0, y0) is the minimum of 1/k × the sum of the T values of any k neighbors of (x0, y0), where k ≥ 2. Observe that k can always be 2 — it is never suboptimal to place 2 dogs adjacent to the current cell, since they block the neighbors with the larger values of T, and decrease our average T over all remaining neighbors. Therefore, to compute T(x0, y0), we will pick any smallest two among T(x0 - 1, y0), T(x0 + 1, y0), T(x0, y0 - 1), and T(x0, y0 + 1), and take their average.
Lemma 1: T(x0 - 1, y0) ≤ T(x0 + 1, y0) for all x0 > 0, y0 ≥ 0.
Lemma 2: T(x0 - 1, y0) ≤ T(x0, y0 + 1) for all x0 > 0, y0 ≥ 0.
By Lemmas 1 and 2, T(x0 - 1, y0) (and, by symmetry, T(x0, y0 - 1)) are better than the other two neighbors, so we place the sheepdogs to block the other two neighbors.
Proof of Lemma 1: Let S be an optimal strategy starting from (x0 + 1, y0). From (x0 - 1, y0), we could use a strategy S' that, as long as we don't get to the column of cells x = x0, always places the dogs in a way that "mirrors" their placements in S with respect to the column x = x0. Call this stage 1. When we first touch that column, we switch to using strategy S; call this stage 2.
During stage 1, if strategy S is in cell (x0 + a, b) after k moves, then S' is in cell (x0 - a, b). During stage 2, after k moves, they are always in the same cell. Since the path from (x0 + 1, y0) to (0, 0) must cross column x = x0, using this strategy means that for any random choices, either our modified strategy reaches (0, 0) before crossing column x = x0, and therefore before strategy S... or the two strategies reach (0, 0) during stage 2, that is, both at the same time.
Sketch of proof of Lemma 2: This is similar to our proof of Lemma 1, but we mirror across the diagonal y = x0 + y0 - x. From (x0, y0 + 1), the path must cross that diagonal, so we can define S' with similar stages, and a similar argument demonstrates the inequality.
It might seem impossible to promise that we will achieve any particular score in a game in which we do not know which options are better than others, and we don't even know when we are scoring points! But we have our ways...
At first, we might be tempted to send a totally random word every turn. Unfortunately, that's not enough to pass the first test set! When we pick a random word W, the robot will respond with a word R chosen uniformly at random from all words ranked higher than W. Since our W will have a 50th percentile rank on average, the robot's R will have a 75th percentile rank on average, so we might expect to score around 25 points in each case (less if we tie). But we have to get at least 25 points in each of 50 test cases. Good luck winning 50 coin flips in a row!
One approach against an unknown strong opponent, familiar to practitioners of aikido, is to use the opponent's own strength against them:
HIGCJ. The
robot responds with some word R1.Suppose that our initial choice of W ranks somewhere around the middle of the pack. We certainly lose by playing W against R1, since we know that R1 beats W. But then when we borrow R1 to play against R2, we know that both R1 and R2 were chosen uniformly and independently at random from among words that beat W, so we should a slightly less than 50% chance of winning (because R1 and R2 might be the same, and we do not score points for ties). Then we lose again by playing against R3, but when we borrow R3 to play against R4, we are playing a word that beat a word that beat W against a word that beat W, so we should have around a 75% chance of winning. As this strategy unfolds, we should lose every other round, but win the remaining rounds with probability 50%, 75%, 87.5%, and so on. This seems like it should easily be enough to get us to 25 points.
However, there is a flaw in this argument: as our "borrowed" words get stronger and stronger, at some point, one of them may be the highest-ranking word, in which case the next "borrowed" robot word will be the lowest-ranking word. Then our "borrowed" words, which are supposed to get us our wins, are actually weak and will cause us to lose those rounds. But now we start to win on the rounds on which we play W, since the robot is playing weakish words in response to our weak "borrowed" words, and W probably beats them. So we still get our wins, but now from the W rounds, until the cycle passes by W again. Notice that this implies that the rank of our initial choice of W was not important.
It turns out that this strategy scores close to 50 points on average, but with enough variance that it will not pass test set 2. (We do not need to worry about it failing test set 1, though. In general, running simulations can help us get estimates of the variance of random solutions like this.)
The most notable characteristic of the game is the fact that the otherwise lowest-ranking word L beats the highest-ranking word H. Can we exploit this irregularity? Suppose that we had a way of knowing the identities of L and H. Then we could score a point on every turn by repeating the following cycle:
So, if we can confidently find L and H in fewer than 50 turns, we can certainly pass.
One strategy is as follows. Start with an arbitrary word, and then spend a number of turns copying the robot's most recent response. Since the robot always has to play something higher-ranking in response, and our play will always be of the same rank as the robot's last word, this algorithm will gradually visit higher-ranked words. Eventually, there must be an exchange in which we play H and the robot is forced to play L. Then we climb the ranks again from there. So, this strategy will repeatedly "cycle" us through the rankings. Although we will not necessarily visit the same particular subset of ranks each time, each cycle will contain H followed by L.
How many of our turns (not counting the robot's turns) will it take us, on average, to reach the H to L transition? It will take 0 turns if we are lucky enough to start there, 1 turn if we start 1 rank away, an expected 1 + ((0 + 1) / 2) = 1.5 turns if we start 2 ranks away, an expected 1 + ((0 + 1 + 1.5) / 3) = 1.8333... turns if we start 3 ranks away, and so on. These are the harmonic numbers. If we start with a random one of our 105 words, the mean number of turns to reach the highest-ranking word is about 11.09. So if we spend 50 turns, we can go through at least three cycles, with high probability.
Then, our program can look through the results to identify these H to L transitions; we should see multiple instances of those two words back to back. There may be a few other instances of consecutive ranks that appear in multiple cycles — for example, maybe the robot always happens to choose the second-highest-ranking word on its way to the highest-ranking word. But the H to L must be present in every cycle, and even if we are unlucky and other consecutive patterns also appear in all of our cycles, we can still reason that the one that occurs closely after all the others is the real transition, since other consecutive patterns are only likely to occur closely before the transition.
Another approach is based on the fact that there are only two words that leave the robot with a single choice: if we play the second-highest-ranking word, the robot must play the highest-ranking word, and if we play the highest-ranking word, the robot must play the lowest-ranking word. So, when the robot sends us a word W, we can send two instances of W and note the robot's two responses. If they are different, we pick the first one and send two instances of that, and so on. If they are the same, we can send W a few more times to see whether we always get the same response R. Then we can send R a few times to see whether we always get the same response S (in which case R is the second-highest-ranking word and S is the highest-ranking word) or varying responses (in which case R is the highest-ranking word and S is the lowest-ranking word).
You can experiment locally and run your own simulations until you are confident that you have a solution that will pass the test sets with high probability. Since both test sets are Visible, and the judge is deterministic, it is possible to tweak your solution and try again if you get unlucky with a reasonable approach. Any overall success probability over, say, 50% should suffice, but the approaches described above should do much better than that.