Round 1C continued this year's Round 1 pattern of one "easier" regular problem, one "medium" interactive problem, and one hard regular problem. Robot Programming Strategy laid out a tournament structure that might have seemed hopelessly complicated at first, but the details turned out to be mostly unimportant — your robot just had to be able to win against any opponent! Like Draupnir in Round 1B, Power Arrangers made you infer some missing information after making careful choices. Finally, Bacterial Tactics could be approached with a useful tool for solving problems about two-player games.
By the 25 minute mark, every problem had been fully solved by at least one contestant, and the race was on to get that first 100 score! Rafbill initially appeared to come out on top with a penalty time of 50:57, but later resubmitted and slipped to an overall third place, with a penalty time of 1:07:44. logicmachine — now that sounds like someone who knows a thing or two about robot programming strategy! — moved up to win with a penalty time of 54:07. Joisino took the silver with 58:48. There were 91 perfect scores overall.
We will be in touch sometime next week to confirm the 1C results; the cutoff for rank 1500 appears to be 42 points plus sufficient speed. Solving just the first or second problem was unfortunately not quite enough. To those of you who did not qualify for Round 2, don't lose heart — it's tough. Keep practicing, and we hope to see you again next year. To the 4500 qualifiers from the three Round 1s: get ready, since Round 2 is even tougher! Best of luck in winning a T-shirt and advancing to Round 3... and perhaps even the World Finals!
Cast
Robot Programming Strategy: Written by Tim Lambert. Prepared by Jonathan Irvin Gunawan.
Power Arrangers: Written by Ian Tullis. Prepared by Pi-Hsun Shih.
Bacterial Tactics: Written by Guillaume Aubian. Prepared by Shane Carr.
Solutions and other problem preparation and review by Patrick Au, Liang Bai, Darcy Best, John Dethridge, Jackson Gatenby, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Pablo Heiber, Andy Huang, Pi-Hsun Shih, Micah Stairs, and Kevin Tran.
Analysis authors:
After many sleepless nights, you have finally finished teaching a robotic arm to make the hand gestures required for the Rock-Paper-Scissors game. Now you just need to program it to compete in the upcoming robot tournament!
In this tournament, each robot uses a program that is a series of moves, each
of which must be one of the following: R (for "Rock"),
P (for "Paper"), or S (for "Scissors"). Paper
beats Rock and loses to Scissors; Rock beats Scissors and loses to Paper;
Scissors beats Paper and loses to Rock.
When two robots face off in a match, the first robot to play a winning move wins. To start, each robot plays the first move of its program. If the two moves are different, one of the moves beats the other and thus one of the robots wins the match. If the moves are the same, each robot plays the next move in its program, and so on.
Whenever a robot has reached the end of its program and needs its next move,
it returns to the start of its program. So, for example, the fifth move of a
robot with the program RSSP would be R. If a match
goes on for over a googol (10100) of moves, the judges flip a fair
coin to determine the winner.
Once a match is over, the winning robot resets, so it has no memory of the that match. In its next match, it starts by playing the first move of its program, and so on.
The tournament is played in K rounds and has a single-elimination "bracket" structure. There are N = 2K robots in total, numbered 0 through N - 1. In the first round, robot 0 plays a match against robot 1, robot 2 plays a match against robot 3, and so on, up to robots N - 2 and N - 1. The losers of those matches are eliminated from the tournament. In the second round, the winner of the 0-1 match faces off against the winner of the 2-3 match, and so on. Once we get to the K-th round, there is only one match, and it determines the overall winner of the tournament.
All of the other contestants are so confident that they have already publicly posted their robots' programs online. However, the robots have not yet been assigned numbers, so nobody knows in advance who their opponents will be. Knowing all of the other programs, is it possible for you to write a program that is guaranteed to win the tournament, no matter how the robot numbers are assigned?
The first line of the input gives the number of test cases, T; T test cases follow. Each test case begins with one line containing an integer A: the number of adversaries (other robots) in the tournament. Then, there are A more lines; the i-th of these contains a string Ci of uppercase letters that represent the program of the i-th opponent's robot.
For each test case, output one line containing Case #x: y. If
there is a string of between 1 and 500 characters that is guaranteed to
win the tournament, as described above, then y should be the
string of uppercase letters representing that program. Otherwise,
y should be IMPOSSIBLE, in uppercase letters.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
Each character in Ci is uppercase R,
P, or S, for all i.
A = 2K - 1 for some integer K ≥ 1.
1 ≤ A ≤ 7.
Ci is between 1 and 5 characters long, for all i.
1 ≤ A ≤ 255.
Ci is between 1 and 500 characters long, for all i.
3 1 RS 3 R P S 7 RS RS RS RS RS RS RS
Case #1: RSRSRSP Case #2: IMPOSSIBLE Case #3: P
Note: Although all the opponents in each of these sample cases have programs of the same length, this is not necessarily the case. Opponents within a test case might have programs of different lengths.
In Sample Case #1, there is only one opponent, with the program
RS. Our answer matches the opponent's moves for a while, and
the opponent loops through its program several times. As is starts its fourth
pass through its program, we beat it with P. Other valid
solutions exist, like P, RR, and R.
In Sample Case #2, there are three opponents, with the programs
R, P, and S. It is up to you to figure
out why this case is IMPOSSIBLE!
In Sample Case #3, all seven opponents use the same program. Using the
program P, for example, guarantees that you will win. Remember
that each robot begins at the start of its program at the start of each match
against a new opponent.
Go, go, Power Arrangers! Everyone loves this team of five superhero high school students who wear the letters A, B, C, D, and E. When they stand side by side to confront evil monsters, they arrange their team in one of 120 possible different left-to-right orders, giving them various different tactical superpowers. They are even more popular than the Teenage Permutant Ninja Turtles!
Some critics of the show claim that the team only has its arrangment gimmick so that the owners of the show can sell 120 separate sets of 5 action figures, each of which features the team in a different left-to-right order, glued to a base so that the set cannot be rearranged. As an avid Power Arrangers fan, you have collected 119 of these sets, but you do not remember which set you are missing. Your 119 sets are lined up horizontally along a shelf, such that there are a total of 119 × 5 = 595 action figures in left-to-right order. You do not remember how the sets are arranged, but you know that the permutation of the sets is selected uniformly at random from all possible permutations, and independently for each case.
You do not want to waste any time figuring out which set you are missing, so you plan to look at the letters on at most F figures on the shelf. For instance, you might choose to look at the letter on the eighth figure from the left, which would be the third figure from the left in the second set from the left. When looking at a figure, you only get the letter from that one figure; the letters are hard to see, and the different team members look very similar otherwise!
After checking at most F figures, you must figure out which of the sets is missing, so you can complete your collection and be ready to face any possible evil threat!
This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.
Initially, your program should read a single line containing two integers T, the number of test cases, and F, the number of figures you are allowed to inspect per test case. Then, you need to process T test cases.
Within each test case, the missing set of figures is chosen uniformly at random from all possible sets, and the order of the remaining sets is chosen uniformly at random from all possible orders as well. Every choice is made independently of all other choices and of your inputs.
In each test case, your program will process up to F + 1 exchanges with our judge. You may make up to F exchanges of the following form:
A, B, C, D, or
E, indicating the letter on that figure. If you sent invalid
data (e.g., a number out of range, or a malformed line), the judge will
instead respond with one line containing the single uppercase letter
N.
Then, after you have made as many of the F exchanges above as you want, you must make one more exchange of the following form:
CADBE).
Y if your answer was correct, and N if it was not
(or you provided a malformed line). If you receive Y, you
should begin the next test case, or stop sending input if there are no
more test cases.
After the judge sends N to your input stream (because of either
invalid data or an incorrect answer), it will not send any other output.
If your program continues to wait for the judge after receiving
N, 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 memory limit is exceeded, or your program
gets a runtime error, you will receive the appropriate judgment.
1 ≤ T ≤ 50.
Time limit: 40 seconds per test set.
Memory limit: 1GB.
The missing set, and the order of the remaining sets, are chosen uniformly
and independently at random.
F = 475.
F = 150.
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.
This interaction corresponds to Test set 1.
t, f = readline_int_list() // Reads 50 into t and 475 into f
printline 10 to stdout // Looks at the last figure in the second set
// from the left
flush stdout
n = readline_string() // Reads B into n. Ooh, team member B! They may
// not have the leadership ability of A, or the
// technical skill of C, but they entertain the
// team with clever quips!
printline 11 to stdout // Looks at the first figure in the third set
// from the left
flush stdout
n = readline_string() // Reads B into n. Notice that B is at the start
// of the third set, whereas they were at the
// end of the second set.
printline 14 to stdout // Looks at the fourth figure in the third set
// from the left
flush stdout
n = readline_string() // Reads D into n. Silent and brooding, team
// member D nonetheless fights fiercely to
// protect their friends... and the world!
printline ABCDE to stdout // We foolishly make a wild guess even though we
// could have looked at up to 472 more figures.
flush stdout
verdict = readline_string() // Reads N into verdict (judge has decided our
// solution is incorrect)
exit // Exits to avoid an ambiguous TLE error
Becca and Terry are microbiologists who have a friendly rivalry. When they need a break from their research, they like to play a game together. The game is played on a matrix of unit cells with R rows and C columns. Initially, each cell is either empty, or contains radioactive material.
On each player's turn, if there are no empty cells in the matrix, that player loses the game. Otherwise, they choose an empty cell and place a colony of bacteria there. Bacteria colonies come in two types: H (for "horizontal") and V (for "vertical").
Whenever a colony (of either type) tries to spread into a cell:
Notice that it may be possible that all of a player's available moves would cause them to lose the game, and so they are doomed. See the sample case explanations below for examples of how the game works.
Becca makes the first move, and then the two players alternate moves until one of them loses the game. If both players play optimally, who will win? And, if Becca will win, how many distinct winning opening moves does she have? (Two opening moves are distinct if and only if they either use different cells, or different kinds of colony, or both.)
The first line of the input gives the number of test cases, T.
T test cases follow. Each case begins with one line containing two
integers R and C: the number of rows and columns, respectively,
in the matrix. Then, there are R more rows of C characters
each. The j-th character on the i-th of these lines represents the j-th
column of the i-th row of the matrix. Each character is either
. (an empty cell) or # (a cell with radioactive
material).
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1), and y
is an integer: either 0 if Becca will not win, or, if Becca will
win, the number of distinct winning opening moves she can make, as described
above.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ R ≤ 4.
1 ≤ C ≤ 4.
1 ≤ R ≤ 15.
1 ≤ C ≤ 15.
5 2 2 .. .# 4 4 .#.. ..#. #... ...# 3 4 #.## .... #.## 1 1 . 1 2 ##
Case #1: 0 Case #2: 0 Case #3: 7 Case #4: 2 Case #5: 0
In Sample Case #1, Becca cannot place an H colony in the southwest empty cell or a V colony in the northeast empty cell, because those would spread onto a radioactive cell and Becca would lose. She has only two possible strategies that do not cause her to lose immediately:
If Becca chooses strategy 1, Terry can place a V colony in the southwest empty cell. If Becca chooses strategy 2, Terry can place an H colony in the northeast empty cell. Either way, Becca has no empty cells to choose from on her next turn, so she loses and Terry wins.
In Sample Case #2, any of Becca's opening moves would cause a mutation.
In Sample Case #3, five of Becca's possible opening moves would cause a mutation, but the other seven are winning. She can place an H colony in any of the cells of the second row, or she can place a V colony in any of the cells of the second column. In either case, she leaves two disconnected sets of 1 or 2 cells each. In each of those sets, only one type of colony can be played, and playing it consumes all of the empty cells in that set. So, whichever of those sets Terry chooses to consume, Becca can consume the other, leaving Terry with no moves.
In Sample Case #4, both of Becca's two distinct possible opening moves are winning.
In Sample Case #5, Becca has no possible opening moves.
With A competitors, there are A! possible initial setups for the tournament bracket, and A is itself exponential in the number of rounds of the tournament. A factorial of an exponential is terrifying enough, and we haven't even started the tournament yet!
Fortunately, we can ignore almost everything about the structure of the tournament. For any opponent, there is at least one possible initial setup in which we will play our first match against that opponent. Since we have to guarantee that we will win the tournament regardless of the initial setup, we must be able to defeat every opponent. We cannot tie an opponent, since that coin flip might not come up in our favor!
So all we have to do is find a program that beats every opponent's program. To check a program, we can just check it against each opponent, without worrying about the tournament setup.
In test set 1, there are at most 7 opponents, and their programs can be at most 5 characters long. Our program can be longer than that if need be, but how long does it need to be? We can observe that an optimal winning program should never waste a turn by tying with all remaining opponents, since then it could have instead chosen the move that would have beaten all of them; therefore, it should eliminate at least one opponent per move. So in test set 1, if there is a winning program, it is at most 7 moves long. We can comfortably check all 37 + 36 ... + 3 possible programs of length up to 7.
When simulating a match, we cannot wait around for a googol of moves; by the same argument above, an optimal winning program should take no more than 7 moves to defeat all opponents, so we only need to simulate at most 7 moves. If we are still tied with the opponent at that point, we can safely give up on that program.
If we find that no program of length at most 7 beats every opponent's
program, then we can declare that the case is IMPOSSIBLE.
In test set 2, there can be up to 255 opponents, and we cannot generate and check all programs of length up to 255. We must find a way to construct a winning program if it exists.
Let's imagine playing against all opponents at once. How do we choose our
program's first move? We must win or tie against every opponent, so we will
consider the set of their first moves. If it includes all three possible
moves, we are doomed; no matter what we pick, at least one opponent
will defeat us. If it includes only one move (e.g. every opponent starts
with R), then we can pick the move that defeats that move
(in this case, P) and instantly defeat everyone. Otherwise,
the set includes two of the possible moves, and we should pick the move that
ties one and beats the other. For example, if the opponents all lead off with
S or P, we should pick S.
Eliminating any defeated opponents and proceeding to the next move of this
combined "match", we can apply the same strategy, but considering the set of
remaining opponents' second moves (looping through their programs as needed),
and so on. We will eliminate at least one opponent with each move, so after
A moves, we will either have our winning program or know that
the case is IMPOSSIBLE. Notice that this limit holds regardless
of the lengths of the opponents' programs.
We can look at up to 475 figures in Test set 1, but there are 595 figures, so we cannot check them all individually. We can observe that when we investigate any particular set, we only need to look at any four of the figures (say, the first four), since we can infer the identity of the fifth. For example, if the first four figures in a set are D, E, A, and B, then we already know that the last figure in that set is C. This reduces our required number of guesses to 4 × 119 = 476. But that is still one more guess than we are allowed!
Observe that once we have determined the orders in all but one of our sets, there are only two sets remaining: the one we have not inspected, and the one we are missing. These two sets must have different figures for at least two indexes, and we can look at any such index to know which set we have. For example, if we know the last two possible sets are CADEB and CDEAB, we can look at the second index; if we see an A, we have the first set, and if we see a D, we have the second set. So, by the time we get to the 119th set on our shelf, we only need to look at one of its figures (but which one to look at will depend on what we learned earlier). After that, we will know which 119 sets we have, and therefore we will also know which set we lack.
Combining these insights, we can guarantee that we will use at most 4 × 118 + 1 = 473 guesses.
In Test set 2, we only have 150 guesses, which is not much more than one guess per set! How can we possibly succeed?
We need to take further advantage of the fact that we are missing only one of the possible sets / permutations. We can start by checking the first figure in each set, using 119 guesses. When we do this, we will find that four out of five of the letters occur 24 times each, and the other one occurs only 23 times. That letter must be the one on the first figure in our missing set!
Now we can restrict our search to only our 23 sets that begin with that letter, and look at the second figure in each of those; this uses 23 guesses. One of those letters will appear only 5 times compared to 6 for the others; then we can narrow our search to those 5 out of the 23 sets, and use 5 guesses to look at the third figures of those. We will find one unique third letter, and then we only need to check the fourth figure in that set to learn what the other, missing set is. This uses a total of (5! - 1) + (4! - 1) + (3! - 1) + (2! - 1) = 119 + 23 + 5 + 1 = 148 guesses, which fits within the limit of 150.
On a player's turn, the grid will be in some state, according to whether any bacteria have already been placed, and how they have spread. We can determine whether a state is losing via the following recursive definition:
Observe that if a state is not losing, it must be winning, since it has at least one move that does not cause a mutation and does not give the opponent a winning state.
To find the number of winning opening moves (if any) for Becca, we can check each move to see whether it is a winning move. Of course, to do this, we have to investigate the resulting state recursively per the above definition. However, since there are up to two moves per empty cell per state, the naive implementation that recursively counts the number of winning moves for each state may not be fast enough to handle even the 4 × 4 grids in test set 1, so we should optimize it.
Notice that whether a state is winning or losing does not depend on who the player is or on any previous moves. Since the same state may come up multiple times, we should consider memoizing our findings about each state to use in the future. It may be daunting that the number of possible states is intractably large. However, for any given case, there can be at most 16 initially empty cells, each of which can be either filled in by bacteria or not. (After a colony has been placed and has spread, it no longer matters what type it was.) So, we can put an upper bound of 216 on the number of states per case. In practice, there will be even fewer because not all states are reachable.
Moreover, we can save some time by not computing the exact number of winning moves for every state we examine. We only care about this value for an initial state; for every other state, it suffices to determine whether it is winning or losing. If we are investigating a non-initial state's moves and we find a winning move, we can declare the state to be winning, and stop. This optimization alone may be enough to solve test set 1.
When a player makes a legal move, the bacteria spread across the entire width or length of the row or column, up until the line of bacteria reaches reaches the edge of the grid or a cell that is already infected. Therefore, each move creates up to two subproblems that are independent in the sense that a move in one subproblem does not affect the state of the other.
Each subproblem can be expressed as a rectangle contained within the full grid. There are therefore at most O(R2C2) subproblems. How can we use the results of these subproblems to determine the overall winner of the game?
The goal of the game is to force the opponent into a situation in which there is no move they can make that leads them down a path to victory. The game is impartial: both players have access to the same set of moves. It is therefore apt to draw a comparison between Bacterial Tactics and the ancient game Nim, an impartial game with similar types of decisions. The mathematics of Nim are well-studied. A discovery particularly useful to us is the Sprague–Grundy Theorem, which says that any impartial game can be mapped to a state of Nim. Every state in Nim corresponds to a non-negative Grundy number, or nimber, where any nonzero nimber indicates a winnable game.
According to nimber addition, the nimber of a game state after we place a colony is equal to the XOR of the two subproblems. The nimber of a game state before we place a colony is the minimum excludant, or MEX, of the set of possible nimbers after placing colonies. We can therefore solve Bacterial Tactics recursively using the following pseudocode:
let solve(state) be a function:
let s = Ø
for each legal colony placement:
add [solve(first subproblem) XOR solve(second subproblem)] to s
return MEX(s)
Given this general framework, we can now optimize our implementation.
First, as in test set 1, we can memoize the game states, which are now defined using rectangles of various sizes within the original grid. Note that it is not possible to have bacteria from previous moves in a subproblem, because we always cut the rectangle along the row or column of cells infected by a colony placement. We may also want to pre-compute the nimbers of all sizes of an empty rectangle (no radioactive cells), which is information that can be shared across all test cases.
Second, observe that if it is legal to place a V colony in a cell, then it is also legal to place a V colony in any cell in that column, and similarly for H colonies in a row, within the boundary of the current subproblem's rectangle. We therefore need to check only the rows and columns for legal colony placements, not each individual cell.
Third, we can construct a data structure that allows us to determine
whether a colony placement is legal for any row or column in a given
rectangle in O(1) time, allowing us to evaluate any game state in
O(R+C) operations. For each row and column in the full grid,
create an array. Check the cells in the row or column in ascending order,
appending the 1-indexed position of the most recently seen radioactive cell,
or 0 if a radioactive cell has not been encountered yet. For example, for the
row .#..#, the array would be [0, 2, 2, 2, 5]. Suppose we have a
rectangle that includes the third and fourth cells of that row. The fourth
entry of the array is a 2. Since cell 2 is not in our rectangle (we have
cells 3 and 4 only), we can conclude that it is safe to place an H colony in
this row of our rectangle. This data structure can be pre-computed for each
test case in O(RC) time.
To summarize, there are O(R2C2) subproblems, and each subproblem takes O(R+C) operations. If we let N be max(R, C), this leads to O(N5) total time complexity, sufficient for test set 2. Less efficient solutions might still pass, depending on their implementations.