Round 3 is the critical Code Jam round that determines who will attend the World Finals, and it represents a big step up even from the traditionally very difficult Round 2. The later Round 3 problems are usually as hard as our typical Finals problems! With twice as many contestants under the new rules this year, the competition for the World Finals slots was even more ferocious.
Field Trip presented what appeared to be a complicated landscape of choices, but some careful thought would reveal a deceptively simple solution. It was much harder to find any sort of constructive or formulaic solution for Name-Preserving Network, though, so contestants had to exercise some creativity to solve this interactive problem. The last two problems, Raise the Roof and Fence Construction, combined geometry — everyone's favorite programming contest topic! — with algorithmic insights.
Although many contestants made short work of the first problem, the other three proved to be formidable. It wasn't until about halfway through the round that every problem had at least one full solve; Fence Construction was the last to fall, with Radewoosh's submission. After it became clear that everything was solvable, we saw the usual race to rack up as many points as possible, with lots of churning on the leaderboard. Errichto.rekt was the first to reach 100 on the optimistic scoreboard; when the final results were revealed, there were no perfect scores, but Errichto.rekt was still in first with an impressive 81 points. ifsmirnov was second with a slightly slower 81, and Golovanov399 was third with 77. The (provisional) cutoff turned out to be 56 points; our defending champion Gennady.Korotkevich was among those advancing to the Finals.
We will finalize results (and contact our finalists) soon. In the meantime, everyone who was eligible for this round is also eligible for Distributed Code Jam, coming up on Sunday. Historically, there has been less overlap between the Code Jam and Distributed Code Jam finalists than one might expect. Will this pattern hold up?
Cast
Field Trip: Written by Pablo Heiber. Prepared by Shane Carr.
Name-Preserving Network: Written by David Arthur. Prepared by Pablo Heiber.
Raise the Roof: Written by Pablo Heiber. Prepared by John Dethridge and Igor Naverniouk.
Fence Construction: Written by Onufry Wojtaszczyk. Prepared by Kevin Tran.
Solutions and other problem preparation and review by John Dethridge, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Timon Knigge, Igor Naverniouk, Trung Thanh Nguyen, Pi-Hsun Shih, Kevin Tran, and Ian Tullis.
Analysis authors:N people from an elementary school — one teacher and N-1 kids — are on a field trip. They are exploring a grassy field that is an infinite two-dimensional grid of unit cells. Each person is currently occupying one of the cells; there may be multiple people in the same cell.
When it is time to go home, the teacher and kids must all gather in one cell; it does not matter which one, since their bus can pick them up anywhere. The kids have been taught an algorithm that makes it easier to gather:
If the teacher makes choices that minimize the number of turns, what is that number of turns?
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with an integer N: the number of people on the field trip. Then, there are N more lines. The i-th of these represents the i-th person, and has two integers Ri and Ci: the row and column numbers (on the grid) of the cell that the i-th person initially occupies.
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 smallest possible number of turns required, as described above.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
2 ≤ N ≤ 10.
0 ≤ Ri ≤ 8, for all i.
0 ≤ Ci ≤ 8, for all i.
2 ≤ N ≤ 104.
0 ≤ Ri ≤ 109, for all i.
0 ≤ Ci ≤ 109, for all i.
5 3 3 2 0 2 0 0 3 2 2 2 2 2 2 9 1 1 0 0 0 1 0 2 1 0 1 2 2 0 2 1 2 2 2 8 0 0 8 4 1 0 1 3 2 2 0 2
Case #1: 2 Case #2: 0 Case #3: 1 Case #4: 4 Case #5: 2
In Sample Case #1, the teacher is at (3, 2) — that is, row 3 and column 2. Kid 2 is at (0, 2), and Kid 3 is at (0, 0). One optimal strategy for the teacher is as follows:
In Sample Case #2, the teacher and the two kids start off in the same cell, so no turns are required.
In Sample Case #3, the teacher can remain in place, and all of the kids will move to the teacher's cell by the end of the first turn.
In Sample Case #4, the teacher should move diagonally four times to reach (4, 4).
In Sample Case #5, the teacher should begin by moving to (1, 1); then kids 2, 3, and 4 will all move to (1, 2). Note that even though all the kids are now in the same cell, the teacher is not, and must start another turn. On the second turn, the teacher can move to (1, 2) to join the kids, and the kids will not move.
A research consortium is building a new datacenter. In the datacenter, a set of computers is set up to work together and communicate via a network. The network works only with direct bidirectional links between computers. A pair of computers c1 and c2 that are not connected by a direct link can still communicate with each other, as long as there is at least one path of links l1, l2, ..., lk such that links li and li+1 share an endpoint, c1 is an endpoint of l1, and c2 is an endpoint of lk. Any two computers can have at most one direct link between them.
The consortium has asked you to submit a design that illustrates how many computers will be in the network and how they will be connected to each other. Each network design you submit must comply with a specific set of restrictions:
To elaborate on the last point: each of the N computers in a network design is initially assigned a unique integer between 1 and N that identifies it. However, it is possible that after some downtime, the system will boot up and the indentifiers will be permuted — that is, each computer will still have a unique integer between 1 and N, but not necessarily the original one. The network must be able to recover the original identifying integers without having access to any information other than the existing direct links.
To evaluate your network designs, the research consortium has set up an automated program. The program will receive one of your network designs, validate conditions 1-3 above, and then send back a copy of the network design with the following changes:
You need to be able to determine exactly how the IDs were changed. Formally, the automated program will create a secret random permutation f of the integers 1 through N, and it will assign those numbers to computers in a "blank copy" of the network with all of the previous links removed. Then, for each link between computers i and j in your network design, it will add a link between f(i) and f(j) to the copy. You then must recreate exactly the f that the automated program created. If there exists a different f' that yields the same result and you return f', the consortium will not accept your network design, as in such a case, you cannot ensure that the recovered IDs are the original ones.
For every N between 10 and 100, inclusive, there exists at least one network of N computers that complies with all restrictions above and has the property that applying two different permutations f and f' to it produces two different sets of links.
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 first read a single line containing two integers L and U indicating the inclusive range of values for the number of computers in your network design.
Then, you need to create a network design with N computers and print 2N+1 lines representing that design. The first line must contain a single integer N. The remaining 2N lines must contain two integers A and B each, each representing a different link between computers A and B, where A != B. Notice that if you list link A B, you may not list A B nor B A again.
Upon reading your network design, the judge will first check the first three
conditions listed in the statement above. If any of those is not met, the
judge will send you a single line containing a single -1, and
then finish all communication and wait for your program to finish. If your
program does finish correctly and without violating other limits, it
will receive a Wrong Answer verdict.
If all of the conditions are met, the judge will send you 2N+1 lines. The first line will contain a single integer N (the same N you sent). Then, the next 2N lines will contain two integers each, describing the links of the copy of the network design, in the same format as you used. The copy is generated as described above, with the permutation f chosen uniformly at random from all possible permutations, independently of your network design.
To finish a test case, you need to send the judge a single line with N integers X1, X2, ..., XN, representing that the computer to which you assigned number i was assigned number Xi in the judge's copy, for all i.
If the list is not the list the judge generated, you will receive a Wrong Answer verdict. If it was in the last test case, the judge will send no additional communication. Otherwise, the judge will send a single line containing a single -1, and then no additional communication. In both cases, the judge will wait for your program to end, and assign the Wrong Answer verdict only if it ended normally and without violating any resource limits.
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 printing the list of Xs for the last test case, you will receive a Wrong Answer judgment.
Notice that you are allowed to submit the same network design for different test cases, as long as that design complies with all restrictions for both cases. Additionally, the seed from random generation in the judge is fixed, so sending the same set of original network designs in the same order will get back the same set of copies.
1 ≤ T ≤ 30.
Time limit: 10 seconds per test set.
Memory limit: 1GB.
L = 10.
U = 50.
10 ≤ L ≤ 50.
L = U.
Note that this sample interaction uses a smaller value of L than the real data, for ease of illustration. Also note that there is no network of exactly 6 computers with the property that applying two different permutations f and f' to it produces two different sets of links, so it would be a bad idea to design a network of exactly 6 computers, even if the problem's limits allowed it!
t = readline_int() // reads 2 into t
limits = readline_int_list() // reads 6 50 into limits
printline 6 to stdout // using 6 computers. Contestant designs an
// octahedral network
printline 2 4 to stdout
printline 1 2 to stdout // you do not need to list edges in any
// particular order
printline 3 1 to stdout // you do not need to give the endpoints of a
// link in order
printline 1 4 to stdout
printline 1 5 to stdout
printline 2 3 to stdout
printline 2 6 to stdout
printline 3 5 to stdout
printline 3 6 to stdout
printline 4 5 to stdout
printline 4 6 to stdout
printline 5 6 to stdout
flush stdout // judge verifies that the network meets
// conditions 1-3 above, and secretly picks
// 2 6 3 1 5 4 as the new permutation
n = readline_int() // reads 6 into n
repeat 12 times:
add readline_int_list() to edges // reads 1 2, 1 4, 1 5, 1 6, 2 3, 2 5,
// 2 6, 3 4, 3 5, 3 6, 4 5, 4 6, in
// that order
printline 2 5 6 1 3 4 // note that this is consistent with what the
// judge sent, but is not the permutation the
// judge used
flush stdout // judge decides that this is wrong
limits = readline_int_list() // expects to read the next case but gets -1,
// indicating a wrong answer
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.
Anthropologists have learned something surprising about a certain ancient Greek society of geometers: they loved partying as much as they loved mathematics! In fact, they kept hosting larger and larger parties over the years, so they needed to raise the roof of their ballroom to keep the noise level tolerable.
We know that the roof of their ballroom was always supported by the tips of exactly three columns; these columns were infinitely thin line segments that originated on the floor and rose up perpendicular to the floor. Whenever the society wanted to raise the roof, they would begin by removing the existing roof. Then, they would build a new column in a location where there was not already a column. Finally, they would rest a new roof on the tips of the new column and the two most recently built of the previously existing columns. For mystical reasons, no three column bases were ever collinear, and no four column tips were ever coplanar.
Each roof was a convex polygon that was part of the plane defined by the three tips that supported it. For each column c built before the supporting ones, the roof did not intersect c at any point and was large enough to cover the space above c. The roof did not touch the floor. The different roofs did not necessarily all have the same shape.
On an archeological dig, you found all N columns that the society ever built, but no roof. You want to determine a possible order in which the columns could have been built that is consistent with the rules above. A possible order is an ordering of the N columns such that, for each prefix of length at least 4 of the ordering, there is a roof (convex polygon) that contains the tips of the last three columns in the prefix, and for each other column in the prefix with a tip at (x, y, h) the roof contains a point (x, y, z) with z > h.
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 N: the number of columns. Then, N more lines follow; the i-th of these lines contains three integers Xi, Yi, and Hi, representing the X and Y coordinates and height above the ground of the tip of the i-th column.
For each test case, output one line containing
Case #x: y1 y2 ... yN, where x is the test case
number (starting from 1), and each yi is a different integer
between 1 through N. These represent a possible ordering of the
columns, with yi being the index in the input of the i-th built column.
It is guaranteed that at least one valid answer always exists. If there are multiple possible answers, you may output any of them.
1 ≤ T ≤ 100.
-106 ≤ Xi ≤ 106, for all i.
-106 ≤ Yi ≤ 106, for all i.
1 ≤ Hi ≤ 106, for all i.
(Xi, Yi),
(Xj, Yj), and
(Xk, Yk) are not collinear, for all
distinct i, j, k.
(Xi, Yi, Hi),
(Xj, Yj, Hj),
(Xk, Yk, Hk), and
(Xl, Yl, Hl) are not
coplanar, for all distinct i, j, k, l.
Time limit: 12 seconds per test set.
Memory limit: 1GB.
4 ≤ N ≤ 10.
4 ≤ N ≤ 1000.
3 5 -1 0 3 1 2 4 1 -2 4 3 1 3 3 -1 2 4 1 1 1 2 2 3 2 3 4 10 11 120 4 1 1 1 2 2 3 2 3 4 10 11 12
Case #1: 5 4 3 1 2 Case #2: 3 2 1 4 Case #3: 1 2 4 3
The following pictures illustrate Sample Case #1.
You are an employee of the Fence Construction Company and have been tasked with the construction of F fences. Each fence runs in a straight line from one point to another. Formally, each fence is a segment connecting two different points in two-dimensional space. Fences do not intersect each other, except possibly at their endpoints. The fences are all connected, that is, for any pair of fences f and g there exists a path f = f1, f2, ..., fk = g such that fi shares an endpoint with fi+1.
At the time you begin your work, no fences have been built. Construction is done using a special fence-shooting 3D printer. There is only one such device, so fences are built one at a time. The printer is small enough that you can consider it a single point on the plane.
To build a fence f, you must first position the printer at a point p in the plane such that the printer can see all of f without being obstructed by previously constructed fences. Formally, p has to be such that:
To position the printer, you can move it from its current position in a contiguous and not necessarily straight line through the plane, as long as the line does not intersect any previously built fences (not even at an endpoint). You can choose any position for the printer to be at before the first fence is built and after the last fence is built.
Having to follow this procedure means that you cannot necessarily build the fences in any order. For example, you might choose an order that blocks off the printer and prevents you from moving it to where it needs to be.
The director of the organization has drafted a relative ordering involving K of the fences (but none of these have been built yet) without giving much thought to it. To avoid angering them, you need to use this ordering, inserting the remaining F-K fences anywhere you like to complete the ordering.
Given these restrictions, find an order in which to build the fences. It is guaranteed that at least one valid order exists.
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line containing two integers F and K: the total number of fences and the number of fences in the director's incomplete ordering. Then, F more lines follow; the i-th of these lines (counting starting from 1) contains four integers Ai, Bi, Ci and Di, indicating that the i-th fence is a line segment from (Ai, Bi) to (Ci, Di). The first K fences given in the input are the K fences in the director's ordering.
For each test case, output one line beginning Case #x: y, where
x is the test case number (starting from 1), and y is a
space-separated ordering of the integers between 1 and F, inclusive,
giving a valid order in which to build the fences.
1 ≤ T ≤ 100.
4 ≤ F ≤ 300.
-105 ≤ Ai ≤ 105, for all i.
-105 ≤ Bi ≤ 105, for all i.
-105 ≤ Ci ≤ 105, for all i.
-105 ≤ Di ≤ 105, for all i.
(Ai, Bi) ≠ (Ci,
Di), for all i.
If p is a non-endpoint point on a fence, then p is not a point of any other
fence.
The given fences are connected, as defined in the statement.
There is at least one ordering of the fences that satisfies all the
construction restrictions in the statement.
Time limit: 10 seconds per test set.
Memory limit: 1GB.
1 ≤ K ≤ 2.
1 ≤ K < F.
3 6 2 0 0 7 7 15 -2 10 0 0 0 0 10 0 0 10 0 0 10 10 10 10 0 10 10 6 1 0 0 0 10 0 0 10 0 0 10 10 10 10 0 10 10 0 0 7 7 15 -2 10 0 11 4 -10 0 10 0 -10 0 0 10 10 0 0 10 0 2 0 5 0 2 10 0 10 0 0 5 15 3 18 3 15 3 15 9 18 3 15 9 15 3 16 5 0 10 15 3
Case #1: 1 2 3 4 5 6 Case #2: 5 6 1 2 3 4 Case #3: 11 10 7 8 9 1 2 3 6 5 4
Note that the last sample case would not appear in test set 1.
In Sample Case #1, it is possible to build the fences in the order they are given: 1, 2, 3, 4, 5, 6. Note that fence 1 must come earlier in the order than fence 2, per the director's list.
In Sample Case #2, it is not possible to build the fences in the given order! One possible order is: 5, 6, 1, 2, 3, 4. Note that when the director's list includes only one fence, the relative order condition is always trivially satisfied.
In Sample Case #3, it is possible to build the fences in the order: 11, 10, 7, 8, 9, 1, 2, 3, 6, 5, 4. Note that fences 1, 2, 3 and 4 must be built in that relative order.
The following pictures illustrate one valid way of building the fences for Sample Case #1.
Since the number of kids and the grid dimensions are small in Test set 1, it is sufficient to develop a correct greedy heuristic for where to move the teacher and then run the simulation to completion.
The first observation is that the problem can be solved independently in each dimension (x and y). At each time step, kid i always moves exactly 1 step closer to person i-1 in both x and y until both people occupy the same position in that dimension. Diagonal movement happens when the two people have different positions in both dimensions; orthogonal movement happens when the two people have the same position in one dimension but different positions in the other dimension; and no movement happens when the people share the same position in both dimensions.
The second observation is that when we take the one-dimensional perspective, the time is limited by only the most distant kids from the teacher in each dimension and direction. Let K be the number of the most distant kid in a certain dimension and direction; if multiple kids share that same position, pick the one with the lowest number. By assumption, all kids with a number lower than K are either closer to or on the opposite side of the teacher than kid K, including kid K-1. Therefore, kid K will move one step in the direction of the teacher. The effect inducts to kids with numbers higher than K; now that kid K has moved closer to the teacher, the first kid with number greater than K that has a distance to the teacher equal to kid K's original distance becomes the most distant kid and is guaranteed to step toward the teacher.
Hence, the correct heuristic is to minimize the distance between the teacher and the most distant kid, treating each dimension independently. To do this, calculate the most distant kid in each dimension, and move the teacher toward each of those kids in their respective dimension. If two kids are equally distant but in opposite directions, do not move the teacher.
An equivalent statement of the heuristic is that the teacher always moves toward the average of the minimum and maximum coordinates in each dimension, not moving if the teacher is already at that center point. If the maximum difference in a certain dimension is odd, the teacher can oscillate between the two central spaces in that dimension; this does not affect the correctness of the heuristic.
A few incorrect greedy heuristics include:
Running the simulation to completion clearly does not work with the higher bounds.
By the greedy heuristic described above, at each time step, since the most distant student in each direction and dimension moves one step closer to the teacher, in each dimension, the minimum coordinate increases by 1 and the maximum coordinate decreases by 1. The problem in each dimension is solved once the minimum and maximum coordinates equal each other. Therefore, we can calculate the total time by taking the difference between the minimum and maximum coordinates in each direction and dividing by 2 (rounding up), choosing the larger of the value in the x dimension and the value in the y dimension. This requires looking at each kid once and therefore takes O(N) time.
At first glance, test set 1 may seem to be approachable even by hand, since only one design is required, and we have considerable flexibility in the number of computers to use. But it turns out to be difficult to satisfy all of the following at once:
For example, we might try creating a ring of computers in which each one is linked to its two neighbors and neighbors' neighbors. This satisfies the 4-link and connected conditions. But this design is highly symmetric in a way that makes the computers less distinguishable. We can try introducing some irregularities (by swapping some edges around; more on this later) to disrupt the symmetry, but then it becomes even harder to eyeball the design — and how can we "find" our computer again after the judge has permuted their identities?
We need a way to give each computer a unique label. Labels need to be such that:
If we have a labeling scheme that has all these properties, the solution writes itself: find a network of appropriate size, compute the labels on it and the labels on the shuffled network given by the judge, and match the computers by label.
There are many possible labeling schemes, and experimentation can go a long way to find them. We describe two below, one for the theoretically inclined, and one more manual. There also exist ways to explicitly construct networks that guarantee a particular labeling scheme. Both the constructions and labeling schemes are somewhat complicated and require casework, and only those constructions with labeling schemes that are quick to compute will work for this problem. Constructions are of course significantly easier for Test set 1, as we only need to build one network and we and we can use whichever network size (between 10 and 50) we want.
Let us start with the theoretical one, since it's shorter to write. We can model the network as an undirected graph in which each node has degree 4. If we take the adjacency matrix of the graph and compute its p-th power, we obtain a matrix in which cell (i,j) gives the number of paths of length p between nodes i and j. In the context of this problem, we do not particularly care about these paths per se, but we do care that the count of paths for a pair of nodes (i,j) depends on the entire topology of the network. So, if we are lucky enough, the set of values (i,1), (i,2), ... will be unique for each i. As it turns out, most graphs of a given size yield unique levels for p = 7, and quite possibly for other values as well. We generated graphs for every size between 10 and 50 and only needed to try a second time twice, and never a third time.
For a more manual approach, we can start by noticing that all computers look similar if we focus on them in isolation; they all use four outgoing links. The same is true of each of a computer's four neighbors. But what if we look at how the neighbors are connected to each other? Specifically, let us label a computer X via a multiset of four values Yi, one for each computer linked to X, where Yi is the number of other computers that are neighbors of both X and Yi. For example, suppose that computer 1 is directly linked to computers 2, 3, 4, and 5, and that there are additional direct links 2-3, 2-4, and 4-5 (and all other links from 2, 3, 4, and 5 are to other computers). Then our multiset for computer 1 would be {1, 1, 2, 2}.
This labeling will not get us far enough in distinguishing computers, since there are not many possible labels of the form described above. But we can take this approach deeper! Let us label each computer as described above, and call those the level 1 labels. Then, we give each computer a level 2 label that is defined as the multiset of the level 1 labels of its neighbors — that is, each level 2 label is a multiset of four multisets. We can even go on to add a level 3 label that is the multiset of the neighbors' level 2 labels, and so on. It turns out that level 4 labels give us enough power to tell computers apart, at least within the 10 to 50 computer range. Moreover, since labeling a computer only requires looking at a computer's four neighbors and a finite number of possible connections between them, one round of the labeling process takes O(computers) time, as does the full process of getting the level 4 labels. This is more efficient than other possible approaches that, e.g., label a computer by the smallest or largest cycle it is part of.
Armed with either labeling method, we just need a way to create network designs to try them on. Generating edges at random has a really low probability of making all degrees exactly 4, so we need something better. One simple possibility is to shuffle a list of exactly 4 times each id, and link the first two ids, the third and fourth, and so on. If this creates a self-loop or a repeated link, repeat until it doesn't. The probability of self-loops or repeated edges is small enough for this to finish quickly for every size.
Another way to generate graphs that is less chaotic is to start with the ring design mentioned above, and then repeatedly mutate it as follows:
This mutation method guarantees that each computer always has four links, and that the network remains connected. (Since we had C-A-B-D before and we have C-B-A-D after, any two computers that were directly or indirectly connected before are still connected.)
Most networks generated in this way (after, e.g., 1000 mutations) turn out to have unique labels on the computers. When we get one that does not (either because the network has some inherent symmetry, or because our labeling method isn't powerful enough for the network), we can just throw it away and try again. Our strategy should take at most a few seconds to discover usable network designs for all possible test cases, and then the rest is just implementation of interactions with the judge.
Finally, notice that, if necessary, graphs for all necessary sizes could be pre-computed offline and hardcoded into the solution. As long as the labeling method is efficient, it is OK for the process of finding the graphs to be a bit slow, as long as it finishes within the contest time! Nevertheless, all ideas presented above are fast enough to require no pre-computation.
In Test set 1, the number of columns is small enough to allow a brute force solution. The problem guarantees that there is at least one correct order, so we can try all possible orders (there are at most 10! = 3628800) until we find a correct one. To check a given order, we check every prefix of length at least 3, build the roof implied by the last 3 columns of the prefix, and then check that all other columns are below it. Since the statement guarantees no 3 points are collinear, any subset of 3 points determines a single plane. There are several ways to check if a roof is valid; here is one that involves only integer arithmetic:
Let p1, p2, ..., pk be the k points in the prefix. Let q be the plane that contains pk-2, pk-1 and pk. For each i between 1 and k - 3, inclusive, we need to check whether pi is above q. Notice that we can subtract pk from all points and the answer to the question doesn't change. Thus, we further assume pk = (0, 0, 0). Let v be a normal to the plane q. Project pi onto v via dot product and check whether v and the projection are on the same side of q. If they are, then pi is above q, otherwise, it is not.
Since checking a prefix takes O(N) time, and there are O(N) prefixes to check for each of the N! orders, this yields an O(N! × N2) algorithm that may or may not be fast enough depending on your language and implementation. We can speed it up in several ways:
For Test set 2, any solution that is exponential or factorial in N is doomed from the start, so we need a different strategy. One possibility is to approach the problem in reverse: start with all columns, find a roof that works, remove a column, and repeat.
To formalize this a bit, we start by fixing the last two points q and p from the set of column tips. to be the last two columns, in that order. We discuss how to do this later. Then, we define s as the set of all column tips except p and q, and repeat the following until s is empty:
The final output is the reverse of the order the points were taken from s, with p and q at the end.
To do the first step above (find r), we could just try every possible point in s and use the process described above to check the condition. This would yield an O(N2) algorithm for the step. To improve upon that, picture the plane containing the last roof, but now being supported by the remaining 2 fixed columns. For the very first iteration, the "last roof" needs to exist for this algorithm to be valid, and how to define it depends on how we choose p and q. For the choice of p and q we explain below, the existence of a possible "last roof" is straightforward. We can rotate the plane around the axis defined by the segment connecting the tips of those two columns, and we want to find one of the columns that it touches first. (There can be up to two such columns, since we can rotate the plane in either direction.) In other words, we should choose a column tip r that minimizes the angle of rotation. That is equivalent to choosing the r that maximizes the angle between a normal to the plane that contains p, q and r and the normal to the "last roof". This yields a linear time algorithm for this step.
To choose the initial p and q, we can try every possibility, which adds an N2 factor to the overall time complexity of the algorithm, or do something better. The last column with tip p can always be chosen as one of the tallest columns. Imagine a plane parallel to z = 0 that passes through p. The plane clearly passes above or touches all other columns, but it's not "pierced" by any column, so we can move it around to create a suitable roof. Then, we can choose q as a column such that the segment pq has minimal angle with the plane. This is similar to what we did above, except we are trying rotating the plane around a single point p until it touches another column q. This can be done by using the same method of comparing angles against a plane we described in the previous paragraph. This involves a one-time linear cost to find q, but then we only do the iteration for a single pair. Notice that, for this choice of p and q, there is a clear choice for the "last roof", which is the imaginary plane that we rotated to find q.
The optimal implementation of the ideas above yields a quadratic algorithm, which is the intended solution. Depending on which of the optimizations you skip, you can end up with a complexity between O(N2) and O(N5), which, together with the constant factors of your implementation and choice of language, determines whether your solution passes both sets, just Test set 1, or neither set.
For both solutions discussed below, we model the situation as a planar graph G with endpoints as nodes and fences as edges. Getting a representation of this graph as an adjacency list takes quasilinear time on the input (because we need to identify endpoints, which may add a logarithmic factor or an expected constant factor depending on whether we use trees, hashing or sorting to do it).
Let us assume for a brief moment that there is no prescribed partial ordering (for instance, when K = 1). There are many greedy algorithms that would retrieve a correct ordering of the fences. You can try working the fences from the outside in or from the inside out, cleverly using convex-hull-type algorithms. Each way has its own pros and cons, but many of them also have the property that the reverse of the ordering they produce is also a valid ordering. This is enough to deal with K up to 2: retrieve a greedy order. If the partial order is obeyed, return that; otherwise, return the reverse. One of the two is guaranteed to work. Another way that works for some greedy alternatives is that they may allow us to fix a single fence as the first one to be built and then work from there. If you fix fence 1 to be the first one built, the partial order is guaranteed to be respected.
We will describe a different option than the one discussed above, because it is simpler to describe, prove and implement. Build any spanning tree T of G that contains fence 1. Build the fences in T first in any order that starts with fence 1. This guarantees that we respect the partial order. Since we are building fences that close no cycle, there are no restrictions to moving the printer so far: any point not on a fence is reachable.
For each the remaining fences f, consider the cycle that is formed when f is added to T. That cycle represents a simple polygon. If we simply build these remaining fences in increasing order of area of that polygon (breaking ties arbitrarily) we obtain a valid order. The reason is that we can always keep the printer on the "outside" of all closed cycles. Since the next cycle to be closed at any time has area no less than any already closed cycles, it cannot be contained in any of them, which means the fence that is closing it is also on the "outside", and so the printer can get arbitrarily close to the fence's position and find a point from where the fence can be built.
Notice that this algorithm can be implemented in quadratic time. Building a spanning tree takes linear time. For each fence outside of the spanning tree, we take linear time to get the area of the polygon, which leads to quadratic overall. Then, we only need to sort the remaining fences, which can be done in faster-than-quadratic time.
For Test set 2, a bit of theoretical knowledge is required. Build the dual graph of G and call it H. Moreover, let G(S) and H(S) be the graph corresponding to a given set of fences S and its dual, respectively. As usual, when we name faces or nodes of H, we include the face that is on the outside (i.e., the only one with infinite area).
When we finish our work, the printer will be left in one of the faces of G, that is, one of the nodes of H, and the last fence we built will be one of the edges that are adjacent to that face. If we step through the build order backwards, right before building the last fence f, the printer is on a face of G(F - {f}), where F is the set of all the fences. For any set S and any fence f, there is a strong relationship between G(S) and G(S - {f}), and correspondingly, H(S) and H(S - {f}). G(S - {f}) is the result of removing f, and possibly its endpoints if they become isolated, from G(S). Correspondingly, H(S - {f}) is either equal to H(S) or the result of merging two nodes of H(S) into one: f may have a single adjacent face in G(S) or two, which leads to nothing changing or two nodes merging in H(S), respectively.
Focusing back on G(F - {f}), we know that the next-to-last fence g to be built has to be one of the fences that is adjacent to a face adjacent to f. The one right before that is adjacent to a face adjacent to either f or g, and so on. That means any ordering of the fences is a possible search on the graph X of fences as nodes where two fences are adjacent in X if they are adjacent to the same face of G. A search on a graph is an ordering of the nodes such that any prefix of the ordering is connected. Breadth-first-searches and depth-first-searches are examples of searches, but not the only ones.
Now that we have identified valid orders with searches on a graph, we can greedily build one that respects the partial order. From this point on, we will build the reverse of the output. Let us fix the first fence of our order f. From here, we can keep track of the reached fences. Any reached fence that is not in the partial order can be added immediately to our order, as it only adds more reachable fences and it cannot violate the partial order. Fences that are in the partial order, however, need to be added respecting that, which we can also do greedily. If at some point all the reachable fences are in the partial order but neither is the next one, we have failed and we need to choose a different f.
The explanations above lead to a quadratic algorithm: building G and then H takes quasilinear time. Building X from H takes quadratic time (since it may have a quadratic number of edges). The greedy algorithm takes constant time for each fence it adds to the order, and we may need to try a linear number of starting fences f, so that time is quadratic overall.
The algorithm can actually be improved to quasilinear overall: there is no need to build X explicitly. We can use X implicitly from H and only inspect adjacencies to fences that haven't been reached. That removes the quadratic cost of explicitly building X. As for trying every f, we can prove that fixing f to be the first fence in the partial order (that is, fence K, since we are building a reverse order) is always optimal. For a valid search of X that respects the partial order, reversing the prefix that ends on fence K is also a valid search that respects the partial order, and has fence K first.