This was our first round of Code Jam 2018, and also the very first round on our new platform. With over 62,000 registrants, it was one of our biggest years ever!
We hope that you enjoyed the new platform, and we are continuously working to smooth down rough edges and add your favorite features from the old platform. We had one period of high server load midway through the contest, and we apologize to those of you who encountered difficulties submitting attempts before we were able to fix the issue.
On to the problems! The title of Saving The Universe Again was a callback to the first problem from our old platform, but the two problems were quite different. Fortunately, this decade's threat to the universe turned out to be fairly simple to defeat if you came up with the right rule. Trouble Sort was also quite approachable if you thought through what our (bad!) new sorting algorithm was actually doing. It's not the first bad sorting algorithm from the Code Jam team, either (see Kicksort); we should really stop poring over advanced algorithms journal articles and get back to the basics!
Go, Gopher! was our first interactive problem, and it was open to various approaches; the main challenge lay in getting used to the new problem type. Finally, we had our traditional oddball Qualification Round D problem, though in this case, it was more of an "oddcube" problem: Cubic UFO riffed on the plot of the 2017 movie Arrival, and it required some serious geometric thinking. Constant-time answers were possible, but not required.
In all, over 24,000 contestants made at least one attempt, and over 21,000 successfully solved at least one test set. Over 14,000 earned the 25 points or more needed to advance to Round 1; official advancement emails will go out early next week. If you were one of our qualifiers, we will see you in just a week for Round 1A! (After a suspiciously pancake-free Qualification Round, what might lie in store?) For those of you who did not qualify, we hope that you had fun, and please join us again next year!
Cast
Saving The Universe Again: Written and prepared by Jonathan Irvin Gunawan.
Trouble Sort: Written by Ian Tullis. Prepared by Micah Stairs.
Go, Gopher!: Written by Pablo Heiber. Prepared by Anqi (Joyce) Yang.
Cubic UFO: Written by Igor Naverniouk. Prepared by Petr Mitrichev.
Solutions and other problem preparation and review by Liang Bai, Shane Carr, John Dethridge, Md Mahbubul Hasan, Brian Hirashiki, Samuel Huang, Ray Robinson, Mihai-Emilian Scortaru, Micah Stairs, and Sasan Tavakkol.
Analysis authors:
An alien robot is threatening the universe, using a beam that will destroy all algorithms knowledge. We have to stop it!
Fortunately, we understand how the robot works. It starts off with a beam with a strength of 1, and it will run a program that is a series of instructions, which will be executed one at a time, in left to right order. Each instruction is of one of the following two types:
C (for "charge"): Double the beam's strength.S (for "shoot"): Shoot the beam, doing damage equal to the
beam's current strength.
For example, if the robot's program is SCCSSC, the robot will
do the following when the program runs:
In that case, the program would do a total of 9 damage.
The universe's top algorithmists have developed a shield that can withstand a maximum total of D damage. But the robot's current program might do more damage than that when it runs.
The President of the Universe has volunteered to fly into space to hack the
robot's program before the robot runs it. The only way the President can hack
(without the robot noticing) is by swapping two adjacent instructions. For
example, the President could hack the above program once by swapping the
third and fourth instructions to make it SCSCSC. This would
reduce the total damage to 7. Then, for example, the president could hack the
program again to make it SCSSCC, reducing the damage to 5, and
so on.
To prevent the robot from getting too suspicious, the President does not want to hack too many times. What is this smallest possible number of hacks which will ensure that the program does no more than D total damage, if it is possible to do so?
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line containing an integer D and a string P: the maximum total damage our shield can withstand, and the robot's program.
For each test case, output one line containing Case #x: y,
where x is the test case number (starting from 1) and
y is either the minimum number of hacks needed to accomplish
the goal, or IMPOSSIBLE if it is not possible.
1 ≤ T ≤ 100.
1 ≤ D ≤ 109.
2 ≤ length of P ≤ 30.
Every character in P is either C or S.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
The robot's program contains either zero or one C characters.
No additional restrictions to the Limits section.
6 1 CS 2 CS 1 SS 6 SCCSSC 2 CC 3 CSCSS
Case #1: 1 Case #2: 0 Case #3: IMPOSSIBLE Case #4: 2 Case #5: 0 Case #6: 5
Note that the last three sample cases would not appear in test set 1.
In Sample Case #1, the President can swap the two instructions to reduce the total damage to 1, which the shield can withstand.
In Sample Case #2, the President does not need to hack the program at all, since the shield can already withstand the 2 total damage it will cause.
In Sample Case #3, the program will do more damage than the shield can withstand, and hacking will do nothing to change this. The universe is doomed.
Sample Case #4 uses the program described in the problem statement. The statement demonstrates one way to reduce the total damage to 5 using two hacks. It is not possible to reduce the damage to 6 or less by using only one hack; remember that the President can only swap adjacent instructions.
In Sample Case #5, the robot will never shoot, and so it will never do any damage. No hacking is required.
In Sample Case #6, five hacks are required. Notice that even if two hacks swap the instructions at the same two positions, they still count as separate hacks.
Deep in Code Jam's secret algorithm labs, we devote countless hours to wrestling with one of the most complex problems of our time: efficiently sorting a list of integers into non-decreasing order. We have taken a careful look at the classic bubble sort algorithm, and we are pleased to announce a new variant.
The basic operation of the standard bubble sort algorithm is to examine a pair of adjacent numbers, and reverse that pair if the left number is larger than the right number. But our algorithm examines a group of three adjacent numbers, and if the leftmost number is larger than the rightmost number, it reverses that entire group. Because our algorithm is a "triplet bubble sort", we have named it Trouble Sort for short.
TroubleSort(L): // L is a 0-indexed list of integers
let done := false
while not done:
done = true
for i := 0; i < len(L)-2; i++:
if L[i] > L[i+2]:
done = false
reverse the sublist from L[i] to L[i+2], inclusive
For example, for L = 5 6 6 4 3, Trouble Sort would proceed as follows:
We were looking forward to presenting Trouble Sort at the Special Interest Group in Sorting conference in Hawaii, but one of our interns has just pointed out a problem: it is possible that Trouble Sort does not correctly sort the list! Consider the list 8 9 7, for example.
We need your help with some further research. Given a list of N integers, determine whether Trouble Sort will successfully sort the list into non-decreasing order. If it will not, find the index (counting starting from 0) of the first sorting error after the algorithm has finished: that is, the first value that is larger than the value that comes directly after it when the algorithm is done.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of two lines: one line with an integer N, the number of values in the list, and then another line with N integers Vi, the list of values.
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1) and y
is OK if Trouble Sort correctly sorts the list, or the index
(counting starting from 0) of the first sorting error, as described above.
1 ≤ T ≤ 100.
0 ≤ Vi ≤ 109, for all i.
Memory limit: 1GB.
3 ≤ N ≤ 100.
Time limit (for the entire test set): 10 seconds.
3 ≤ N ≤ 105.
Time limit (for the entire test set): 20 seconds.
Notice that test set 2 for this problem has a large amount of input, so using a non-buffered reader might lead to slower input reading. In addition, keep in mind that certain languages have a small input buffer size by default.
2 5 5 6 8 4 3 3 8 9 7
Case #1: OK Case #2: 1
Sample Case #1 is similar to the first one described in the problem
statement. Trouble Sort correctly sorts this list, so the answer is
OK.
Sample Case #2 is the second one described in the problem statement. Trouble Sort does not correctly sort this list, since it terminates with the list 7 9 8. The 9 is the first value in the list that is larger than the next value, so the index of the first sorting error is 1.
The Code Jam team has just purchased an orchard that is a two-dimensional matrix of cells of unprepared soil, with 1000 rows and 1000 columns. We plan to use this orchard to grow a variety of trees — AVL, binary, red-black, splay, and so on — so we need to prepare some of the cells by digging holes:
Note that the above also implies that none of the cells outside of that rectangle can be prepared. We want the orchard to look tidy!
For example, when A=11, although the eleven prepared cells in the left figure below form a 3x4 rectangle (that is, with 3 rows and 4 columns), the cell in the center of the rectangle is not prepared. As a result, we have not yet completed preparing our orchard, since not every cell of the 3x4 rectangle is prepared. However, after just preparing the center cell, the rectangle of size at least 11 is fully filled, and the orchard is ready.
See below for another example. In this case, A=6. Note that the middle figure prepares a cell outside the 3x2 rectangle, so although the rightmost figure prepares a rectangle of size 6, the entire set of the prepared cells does not form a rectangle (due to the extra cell on the left). As a result, the orchard is not ready.
Digging is hard work for humans, so we have borrowed the Go gopher from the Google Go team and trained it to help us out by preparing cells. We can deploy the gopher by giving it the coordinates of a target cell in the matrix that is not along any of the borders of the matrix. However, we have not yet perfected the gopher's training, so it will choose a cell uniformly at (pseudo-)random from the 3x3 block of nine cells centered on the target cell, and then prepare the cell it has chosen. (If it chooses a cell that was already prepared, it will uselessly prepare it again.)
We can only deploy the gopher up to 1000 times before it gets too tired to keep digging, so we need your help in figuring out how to deploy it strategically. When you deploy the gopher, you will be told which cell the gopher actually prepared, and you can take this information into account before deploying it again, if needed. Note that you do not have to declare the dimensions or location of a rectangle in advance.
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. To help you debug, a local testing tool script (in Python) is provided at the very end of the problem statement. In addition, sample solutions to a previous Code Jam interactive problem (in all of our supported languages) are provided in the analysis for Number Guessing.
Initially, your program should read a single line containing a single integer T indicating the number of test cases. Then, you need to process T test cases.
For each test case, your program will read a single line containing a single integer A indicating the minimum required prepared rectangular area. Then, your program will process up to 1000 exchanges with our judge.
For each exchange, your program needs to use standard output to send a single
line containing two integers I and J: the row and column number you want to
deploy the gopher to. The two integers must be between 2 and 999, and written
in base-10 without leading zeroes. If your output format is wrong (e.g., out
of bounds values), your program will fail, and the judge will send you a single
line with -1 -1 which signals that
your test has failed, and it will not send anything to your input stream after
that. Otherwise, in response to your deployment, the judge will print a single
line containing two integers I' and J' to your input stream, which your
program must read through standard input.
If the last deployment caused the set of prepared cells to be a rectangle of area at least A, you will get I' = J' = 0, signaling the end of the test case. Otherwise, I' and J' are the row and column numbers of the cell that was actually prepared by the gopher, with abs(I'-I) ≤ 1 and abs(J'-J) ≤ 1. Then, you can start another exchange.
If your program gets something wrong (e.g. wrong output format, or out-of-bounds values), as mentioned above, the judge will send I' = J' = -1, and stop sending output to your input stream afterwards. If your program continues to wait for the judge after reading in I' = J' = -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 the appropriate verdict (Wrong Answer, Runtime Error, etc.) 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 verdict.
If the test case is solved within 1000 deployments, you will receive the I' = J' = 0 message from the judge, as mentioned above, and then continue to solve the next test case. After 1000 exchanges, if the test case is not solved, the judge will send the I' = J' = -1 message, and stop sending output to your input stream after.
You should not send additional information to the judge after solving all test cases. In other words, if your program keeps printing to standard output after receiving I' = J' = 0 message from the judge for the last test case, you will receive a Wrong Answer judgment.
Please be advised that for a given test case, the cells that the gopher will pick from each 3x3 block are (pseudo-)random and independent of each other, but they are determined using the same seed each time for the same test case, so a solution that gives an incorrect result for a test case will do so consistently across all attempts for the same test case. We have also set different seeds for different test cases.
1 ≤ T ≤ 20.
Memory limit: 1 GB.
A = 20.
Time limit (for the entire test set): 20 seconds.
A = 200.
Time limit (for the entire test set): 60 seconds.
t = readline_int() // reads 2 into t a = readline_int() // reads 3 into a printline 10 10 to stdout // sends out cell 10 10 to prepare flush stdout x, y = readline_two_int() // reads 10 11, since cell 10 11 is prepared printline 10 10 to stdout // sends out cell 10 10 again to prepare flush stdout x, y = readline_two_int() // reads 10 10, since cell 10 10 is prepared printline 10 12 to stdout // sends out cell 10 12 to prepare flush stdout x, y = readline_two_int() // reads 10 11, since cell 10 11 is prepared again printline 10 10 to stdout // sends out cell 10 10 to prepare flush stdout x, y = readline_two_int() // reads 11 10, since cell 11 10 is prepared printline 11 10 to stdout // sends out cell 11 10 to prepare flush stdout x, y = readline_two_int() // reads 0 0; since cell 11 11 is prepared, a rectangle of size 4
The pseudocode above is the first half of a sample interaction for one test set.
Suppose there are only two test cases in this test set. The pseudocode first reads
the number of test cases into an integer t. Then the first test case begins.
For the first test case, suppose A is 3 (although, in the real test sets,
A is always either 20 or 200). The pseudocode first reads the value of A
into an integer a, and outputs 10 10 the location of
the cell to prepare. By (pseudo-)random choice, the cell at location 10 11 is
prepared, so the code reads 10 11 in response. Next, the code
outputs cell 10 10 again for preparation, and the gopher prepares
10 10 this time. The code subsequently sends 10 12 with
the goal of finishing preparing a rectangle of size 3, but only gets cell
10 11 prepared again. 10 10 is then sent out, and this time
11 10 is prepared. Notice that although the prepared area is of size 3,
a rectangle has not been formed, so the preparation goes on. In the end, the pseudocode
decides to try out cell 11 10, and 0 0 is sent back, which
implies that cell 11 11 has been prepared, completing a rectangle (or square, rather)
or size 4. As a result, the first test case is successfully solved.
a = readline_int() // reads 3 into a printline 10 10 to stdout // sends out cell 10 10 to prepare x, y = readline_two_int() // does not flush stdout; hangs on the judge
Now the pseudocode is ready for the second test case. It again first reads an integer
a = 3 and decides to send cell 10 10 to prepare.
However, this time, the code forgets to
flush the stdout buffer! As a result, 10 10 is buffered and not sent to the judge.
Both the judge and the code wait on each other, leading to a deadlock and eventually a
Time Limit Exceeded error.
a = readline_int() // reads 3 into a printline 1 1 to stdout // sends out cell 1 1 to prepare x, y = readline_two_int() // reads -1 -1, since 1 is outside the range [2, 999] printline 10 10 to stdout // sends a cell location anyway x, y = readline_two_int() // hangs since the judge stops sending info to stdin
The code above is another example. Suppose for the second test case, the code
remembers to flush the output buffer, but sends out cell 1 1 to prepare.
Remember that the row and column of the chosen cell must both be in the range
[2, 999], so 1 1 is illegal! As a result, the judge sends back -1 -1.
However, after reading -1 -1 into x and y, the code proceeds to
send another cell location to the judge, and wait. Since there is nothing in
the input stream (the judge has stopped sending info), the code hangs and will
eventually receive a Time Limit Exceeded error.
Note that if the code in the example above exits immediately after reading
-1 -1, it will receive a Wrong Answer instead:
a = readline_int() // reads 3 into a printline 1 1 to stdout // sends out cell 1 1 to prepare x, y = readline_two_int() // reads -1 -1, since 1 is outside the range [2, 999] exit // receives a Wrong Answer judgment
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.
A mysterious cubic alien ship has appeared in the sky over Toronto! In this problem, Toronto is a plane in three-dimensional space that is parallel to the xz plane at y = -3 km. The alien ship is a solid cube with side length 1 km, centered at (0 km, 0 km, 0 km), with its eight corners at (+/- 0.5 km, +/- 0.5 km, +/- 0.5 km). The ship is casting an ominous shadow onto the plane; formally, the shadow is the orthogonal projection of the cube onto the plane. (We consider the sun to be a point infinitely far above the Toronto plane along the y-axis.)
The military is willing to tolerate the ship as long as the aliens meet their bureaucratic demand: the shadow must cover an area of the plane that is acceptably close to A km2 (see the Output section for a precise definition). They have hired you, a geometric linguistics expert, to convey this demand to the aliens. In your communications so far, you have learned that the ship cannot change size, and the center of the ship cannot move, but the ship is able to rotate arbitrarily in place.
Please find a way that the aliens can rotate the ship so that the shadow's area is close to A. Express your rotation using three points: the centers of any three non-pairwise-opposing faces.
The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with a rational A, the desired area of the shadow, in km2, with exactly six digits after the decimal point.
It is guaranteed that there is always a way to rotate the ship in the desired manner for the values of A allowed in this problem.
For each test case, first output one line containing Case #x:,
where x is the test case number (starting from 1). Then, output
three more lines with three rational values each: the x, y, and z coordinates
of one of your three provided face-centers, as described above. You are
welcome to use decimal (e.g., 0.000123456) or scientific notation (e.g.,
1.23456e-4).
Your answer will be considered correct if and only if all of the following are true:
Please note that you might need to output more than 6 digits after the decimal point to safely pass the checks mentioned above. If there are multiple acceptable answers, you may output any one of them.
1 ≤ T ≤ 100.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1.000000 ≤ A ≤ 1.414213
1.000000 ≤ A ≤ 1.732050
2 1.000000 1.414213
Case #1: 0.5 0 0 0 0.5 0 0 0 0.5 Case #2: 0.3535533905932738 0.3535533905932738 0 -0.3535533905932738 0.3535533905932738 0 0 0 0.5
In Sample Case #1, there is no need to rotate the cube at all; with two of its faces already parallel to the plane, the cube is already casting a shadow that is a square with side length 1.
In Sample Case #2, one possible solution is to tell the aliens to give the cube a 45 degree turn around the x = y = 0 line, creating a shadow that is a rectangle with dimensions of 1 and sqrt(2).
The following rough image shows the cubes and shadows for Sample Cases #1 and #2. The sun is shown for clarity, but remember that it is actually a point infinitely far away along the y-axis.
Since there is at most one C instruction in this test set, we
can solve the two cases independently.
If there is no C instruction in P, then none of our swaps
will have any effect, so all we can do is check whether the damage of the
beam exceeds D.
If there is one C instruction in P, then we can try every
possible position for the C instruction in the program. Assuming
that there is at least one position for the C instruction that
causes the total damage not to exceed D, we can choose the scenario
that requires the fewest swaps; the number of required swaps for a scenario
is equal to the distance between the original and final positions of the
C instruction.
To solve test set 2, we will first derive a formula to compute the total
damage based on the positions of the C and S
instructions in P. Let NC and NS be the number of
C and S instructions in P, respectively.
Let Ci be the number of S instructions to the right of
the i-th C instruction, where i uses 1-based indexing.
Note that the i-th C instruction will increase the damage of the
subsequent beams by 2i-1. For example, in the input program
CSSCSSCSS, initially, all of the S instructions will
inflict a damage of 1. Consider the damage dealt by the last S
instruction. Since the robot has been charged twice, the damage output by the
last instruction will be 4. Alternatively, we see that the damage, 4 = 1
(initial damage) + 20 (damage caused by the first C)
+ 21 (damage caused by the second C). By breaking
down the damage by each S instruction in the same manner, the
total damage output, D, of the input program is given by:
D = NS + C1 × 1 + C2 × 2 + ... + CNC × 2NC - 1 .
Next, we investigate how each swap affects the amount of damage. A swap on
adjacent characters which are the same will not affect the equation. When we
swap the i-th C instruction with a S instruction to
its right, the value of Ci will decrease by 1 since now there is
one less S than before. On the other hand, swapping the i-th C
instruction with an S instruction on its left will increase the
value of Ci by 1. Note that in either case, we will only modify
the value of Ci, and the other C values will remain the same. This
suggests that we should only ever swap adjacent instructions of the form
CS.
Therefore, executing M swaps is equivalent to reducing the values of Cis such that the total amount of reduction across all Cis is M. We want the total damage (according to the above equation) to be minimized. Clearly, we should reduce the values of Ci that contribute to the largest damage output, while making sure that each of the Cis is nonnegative.
Intuitively, all of this math boils down to a very simple algorithm! As long
as there is an instance of CS in the current program, we always
swap the latest (rightmost) instance. After each swap, we can recompute the
damage and check whether it is still more than D. If it is not, then
we can terminate the program. If we ever run out of instances of
CS to swap, but the damage that the program will cause is still
more than D, then the universe is doomed.
Like bubble sort, Trouble Sort has O(N2) time complexity; the proof is explained below. With N ≤ 100 for test set 1, we can run Trouble Sort to completion and simply iterate over the result list to find the first sorting error, if any (that is, a value that is greater than the value that follows it in the list).
Running O(N2) Trouble Sort to completion is too slow for N ≤ 105.
Instead, let's break down what Trouble Sort is doing at each step. Let's consider an input list of 6 elements. Trouble Sort makes the following comparisons on each pass through the array:
Regardless of the length of the list, this table illustrates the fundamental flaw in Trouble Sort: even-index elements are compared with other even-index elements, and odd-index elements are compared with other odd-index elements, but even-index and odd-index elements are never compared with each other! This means that Trouble Sort is just bubble sort run separately on the even-index elements and the odd-index elements, interleaving them into the output list. Trouble Sort is correct only if interleaving the two sub-lists (the even-index list and the odd-index list) happens to produce another sorted list. Since there are O(N) even-index and O(N) odd-index elements, and since bubble sort is O(N2), Trouble Sort is also O(N2).
To solve test set 2, we can can run our favorite O(N log N) sorting algorithm independently on the two sub-lists described above, interleave the sorted sub-lists, and then find the first sorting error as in our solution for test set 1.
For test set 1, we need to prepare all the cells within a grid-aligned rectangle of size at least 20. Before starting to deploy the gopher, let's choose a rectangular target region of size at least 20. We will try to prepare all the cells within this target region. One option is to choose a 4 x 5 target region. We could have chosen 3 x 7, 5 x 5 etc, but it should not be too big. It does not matter where we place this target region in our initial 1000 x 1000 matrix. So let's place it such that one corner of the rectangle is at (1, 1) and the opposite corner is at (4, 5). Here (r, c) refers to the cell in the r-th row and the c-th column of the original matrix. Now the question is: can we come up with a strategy that will prepare all of the cells in this target region, and no other cells?
Let's visualize our 4 x 5 target region as follows (row and column numbers are given for convenience):
12345
1 xxxxx
2 x@@@x
3 x@@@x
4 xxxxx
We marked the internal cells with @ and the border cells with x. The
gopher should not be deployed on the border cells, because that might cause it to prepare a cell
outside of our target region. We will only deploy on the internal cells (cells marked with
@ in the above picture). We can deploy the gopher 1000 times in total and we have 6
internal cells. Let's deploy the gopher to each of the internal cells
floor(1000 / 6) = 166 times. Will this be enough to solve test set 1?
To answer this crucial question, let us compute the probability that after deploying the gopher as described above, the (1, 1) cell is still unprepared. Notice that this cell can only be prepared by deploying the gopher at (2, 2). Every time we do this, it has a 1/9 probability of preparing (1, 1). Looking at it from another angle, every time we do this, it has an 8/9 probability of not preparing (1, 1). So the probability that (1, 1) will not be prepared after 166 deployments to (2, 2) is (8/9)166 = 3.226 x 10-9, which is quite small. Realistically, we do not need to worry about this happening to any of the four corners (since the probability of this happening to at least one of the four corners is 1 - (1 - 3.226 x 10-9)4 = 1.29 x 10 -8). Other cells are adjacent to more than one internal cell, and thus they are more likely to be prepared than the corners. So this solution is sufficient to pass test set 1.
To convince you further we ran a simulation. We deployed the gopher to the center of a 3 x 3 region until all the nine cells in the region is prepared. We ran this 100000 times and following is the result:
The above figure shows how many of our 100000 simulations (y axis) required each possible number of deployments (x axis). As we can see, out of 100000 simulations the maximum number of times we needed to deploy the gopher was not more than 120. So 166 deployments would be more than enough to prepare an internal cell and all of its surroundings. Moreover, once we have prepared an internal cell and all eight of its neighbors, there is no reason to deploy the gopher there again, so we will almost certainly have more than 166 deployments to use to fill in the last stubborn cell if necessary.
Now we need to create a rectagular region of area at least 200. If we used the same strategy
described above, for, say a 10 x 20 size rectangle, we could make
floor(1000/(18 * 8)) = 6 deployments to each of the internal cells. But then the
probability of (1, 1) being not prepared would be: (8/9)6 = 0.49327, which is way
too high!
How can we improve this strategy? We can observe that most of the cells can be prepared from a number of locations. For example, the cell (2, 2) can potentially be prepared on a deployment to any of the internal cells around it, or to the cell itself. What if we divide our rectangular region into disjoint 3 x 3 regions and only deploy the gopher to the center cells of those regions? This way each of the cells can be prepared from only one cell. To sum things up, our plan is:
Is that enough? As the above simulation showed, sometimes it requires 120 deployments to prepare entire 3 x 3. So in the worst case 23 x 120 = 2760 deployments to prepare entire 3 x 69 region which is more than out limit 1000. However, such worst case will not happen always. We ran another simulation to examine our new strategy:
The above figure shows how many of our 100000 simulations (y axis) required each possible number of deployments (x axis) to prepare all the cells inside 3 x 69 target region. As we can see, the maximum we needed is no more than 850 and our limit was 1000. So we can be confident that this strategy is good enough to pass test set 2.
There are many other strategies. One may be, to deploy the gopher to the cell that has the largest number of unprepared cells in 3 x 3 region centering at that cell. This strategy yields following simulation result (100000 runs), which looks better than the one before:
This is an ad hoc geometry problem with many different solutions.
Suppose the cube is initially axis-aligned. Let us rotate it about the z-axis by angle t, from +x towards +y, and study the shadow:
Key observations:
For this setup, maximal area is attached when t = π/4, which corresponds to Vx = √(½), resulting in A = √2 ≈ 1.414214. This exceeds all Test Set 1 inputs, so the setup is sound.
Next, we find the shadow area A as a function of angle t. From basic geometry, Vx = √(½) × cos(t − π/4). Therefore A = 2Vx = √2 × cos(t − π/4), for 0 ≤ t ≤ π/4.
Given A, naively we'd invert the formula and get t as sum of π/4 and cos−1(A / √2). However, to satisfy 0 ≤ t ≤ π/4, we need the negative branch of cos−1! Therefore the inverse is:
t = π/4 − |cos−1(A / √2)|.
Once t is obtained, the final outputs are the centers of three non-parallel faces. One such face (invariant for all t) is (0, 0, ½). The other two can be obtained from rotating (½, 0), and (0, ½) by angle t, and assigning z to 0. Using the rotation formula yields (½ cos(t), ½ sin(t), 0) and (−½ sin(t), ½ cos(t), 0).
Our solution hinges on the following two crucial observations:
To simplify the computations, let's rotate the cube about the y-axis by 45 degrees. (The direction of the rotation does not matter, since the cube would end up in the same orientation either way.) After that, the cube will look like this:
It might not be immediately clear why this simplifies our life, but it will make sense soon!
According to the above observations, the cube currently has the smallest possible shadow. To maximize that shadow, we can rotate the cube about the x-axis from +z towards +y, and bring the vertex H (from our diagram above) onto the y-axis. A useful property of this rotation is that the area of the shadow consistently increases throughout this rotation. Since we start with the smallest possible shadow and continuously rotate until we get the largest possible shadow, we achieve every possible shadow area at some point during this rotation. So, we can use binary search to figure out the exact angle by which we need to rotate the cube about the x-axis to achieve the desired area.
However, two questions remain:
Notice that, since we are rotating the cube about the x-axis, the x-coordinates of the points will remain the same; only the y- and z- coordinates will change. So, instead of performing rotations in 3-D, we will project the point onto the yz-plane (the x = 0 plane) and perform the rotations in 2-D.
For example, suppose that we want to rotate point P = (Px, Py, Pz) about the x-axis from +z towards +x by angle t. First, we project the point onto the yz-plane, where it will have coordinates (0, Py, Pz). We will ignore the x component and treat the point as (Py, Pz) on a 2-D plane.
Now, rotation about the x-axis by angle t in the indicated direction is equivalent to rotating (Py, Pz) about (0, 0) by angle t in a clockwise direction. The resulting 2-D point will be
(Py', Pz') = (Py × cos(t) + Pz × sin(t), −Py × sin(t) + Pz × cos(t)),
which in 3-D becomes (Px, Py', Pz'). We can get this from the rotation formula, or the complex expression (Py + iPz) × e−it.
As H approaches the y-axis, the shadow on the y = −3 plane takes the shape of a convex hexagon. More specifically, the vertices of the hexagon are the projection of points D, C, G, F, E, and A onto the y = −3 plane. For a point P with coordinates (Px, Py, Pz), the coordinates of its projection onto the y = −3 plane are (Px, −3, Pz).
Now, to find the area of the shadow, we can treat the six projected vertices as if they were on a 2-D plane, with only their x- and z-coordinates. By construction, these already form a convex hull with vertices properly oriented (otherwise one would need to explicitly compute the convex hull, although shortcuts exist for the special case). This enables us to apply the standard formula to compute area of a convex polygon. Note that area computation can also be simplified by using symmetry with respect to the z-axis, and apply the trapezoid area formula instead of the general convex polygon.
Once we have a set of coordinates that produces the desired area, we can compute the coordinates of the face-centers of any three non-pairwise-parallel faces, and we have solved the problem. With the setup above, these are simply ½(A + C), ½(C + F), and ½(F + A).
There are many other ways to solve this problem: