This year's Round 3 was different than any of our past rounds. None of the problems were easy, and more importantly, we had two interactive problems in the same round for the first time ever. Revenge of GoroSort was another interactive sorting problem which required some knowledge about permutations and a bit of research / trial and error. Duck, Duck, Geese was the only typical competitive programming problem that was about data structures. Mascot Maze was highly idea-oriented, where getting the right insight led to a straightforward implementation. Finally, there was a large jump in difficulty to the second interactive problem of the round, Win as Second, which was about game theory and had contestants play around in a tree.
About 10 minutes into the contest the first submissions that solved Revenge of GoroSort in full started coming in. But it wasn't until almost 2 hours that someone got a perfect score. Gennady.Korotkevich was the first one there, and claimed the first place in the round. Benq, SpyCheese, and Um_nik were the other three that managed to do it and rounded out the top 4. The unofficial cutoff to make it to the finals is 71 points and a low enough penalty.
The results will be reviewed in the coming days. Those who are in the top 25 after the round is finalized will advance to the Virtual World Finals! You can keep trying the problems or pratice for your next challenge by checking out our archive.
Thank you for participating and remember you can get a certificate showing your Code Jam achievements in your profile page.
Cast
Revenge of GoroSort: Written by Ian Tullis. Prepared by Timothy Buzzelli.
Duck, Duck, Geese: Written by Chakradhar Reddy. Prepared by Shane Carr.
Mascot Maze: Written by John Dethridge. Prepared by John Dethridge and Swapnil Mahajan.
Win as Second: Written and prepared by Petr Mitrichev.
Solutions and other problem preparation and review by Andrei Korneev, Andy Huang, Antonio Mendez, Chakradhar Reddy, Darcy Best, Deepak Gour, Ian Tullis, John Dethridge, Liang Bai, Md Mahbubul Hasan, Mohamed Yosri Ahmed, Nafis Sadique, Nhi Le, Nour Yosri, Pablo Heiber, Petr Mitrichev, Pi-Hsun Shih, Salma Mustafa, Samuel Huang, Shane Carr, Shantam Agarwal, Swapnil Mahajan, Timothy Buzzelli, and Yui Hosaka.
Analysis authors:
In this problem, when something is said to be chosen at random, it means uniformly at random from among all valid possibilities, and independently of any other choice.
Code Jam contestants once helped the mighty Goro sort an array of integers. (You do not need to read that problem to solve this one.) Once again, Goro needs your help. He has $$$\mathbf{N}$$$ boxes lined up on the table in a single row, numbered $$$1$$$ through $$$\mathbf{N}$$$ from left to right. Each box has exactly one ball inside. Balls are also numbered $$$1$$$ through $$$\mathbf{N}$$$. Goro wants ball $$$i$$$ to end up in box $$$i$$$, for all $$$i$$$. That is, he wants to leave the balls in sorted order. Unfortunately, that is not initially the case.
When Goro bumps the table with his powerful fists, balls pop up in the air and fall back in boxes. Goro can do this so accurately that exactly one ball falls into each box. A ball may fall into the same box it came out of, or into a different one.
Better yet, Goro also has the ability to assign colors to boxes before each bump. Then, he can bump the table in such a way that balls coming out of a box of color $$$c$$$ always fall into a box of color $$$c$$$. As impressive as this accuracy is, Goro does not have any more control than that. Within each color, balls end up assigned to boxes at random.
For example, suppose the balls appear in the order $$$1, 4, 3, 6, 5, 2$$$ (as seen above). He might choose — not necessarily optimally — to give the first box the color red, the second and sixth boxes the color green, and the third through fifth boxes the color blue. Then, after Goro bumps the table,
So, for example, the probability of the bump leaving the balls in the order $$$1, 2, 3, 5, 6, 4$$$ is $$$\frac{1}{12}$$$. If Goro got this or some other non-sorted result, he would have to designate a set of box colors for the next round, and so on, until he eventually arrives at the sorted $$$1, 2, 3, 4, 5, 6$$$. Goro can assign colors to boxes in any way before each bump, regardless of previous assignments.
Can you help Goro implement a better strategy that will efficiently sort the balls? It is guaranteed that the balls start in a random non-sorted order.
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 three integers, $$$\mathbf{T}$$$ $$$\mathbf{N}$$$ $$$\mathbf{K}$$$: the number of test cases, the number of boxes per test case, and the total number of bumps allowed for all test cases combined. Then, $$$\mathbf{T}$$$ test cases must be processed.
Each test case begins with the judge sending one line with $$$\mathbf{N}$$$ integers, with each integer from $$$1$$$ to $$$\mathbf{N}$$$ appearing exactly once, and with the list chosen at random from all non-sorted lists. Then you must engage in a series of interactions with the judge. Each interaction works as follows:
As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment. Also, if your program continues to wait for the judge after receiving a $$$-1$$$, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error.
Be advised that the judge uses the same source of randomness each time, so in the absence of other errors (e.g. Time Limit Exceeded, Memory Limit Exceeded), submitting the exact same code twice will yield the same outcome twice.
Time limit: 20 seconds.
Memory limit: 1 GB.
$$$\mathbf{T} = 1000$$$.
$$$\mathbf{N} = 100$$$.
$$$\mathbf{K} = 16500$$$.
$$$\mathbf{K} = 12500$$$.
$$$\mathbf{K} = 11500$$$.
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.
2 4 8
1 4 3 2
1 2 3 2
0 1 4 3 2
1 2 3 2
1
2 1 4 3
4 4 4 4
1
Note that the sample interaction does not satisfy the constraints of any of the test sets. It is only presented to clarify the input and output format.
In the game "Duck, Duck, Goose", all players but one sit on the floor and form a circle. The remaining player walks around the circle calling each player "duck" until they select one sitting player and, while touching their head, call them "goose" instead. At that point, the goose chases the selecting player and our interest in the game fades.
In the new game "Duck, Duck, Geese", the walking player instead chooses a contiguous subset of at least two (but not all) sitting players to be "geese"! Furthermore, each sitting player is wearing a hat. Each hat is one of $$$\mathbf{C}$$$ possible colors, numbered $$$1$$$ through $$$\mathbf{C}$$$.
For each color $$$i$$$, the quantity of selected geese wearing a hat of color $$$i$$$ must be either $$$0$$$ or between $$$\mathbf{A_i}$$$ and $$$\mathbf{B_i}$$$, inclusive.
Can you help count the number of choices that fulfill these requirements? Two choices are considered different if there is some player that is included in one choice but not the other.
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow. Each test case starts with a line containing two integers $$$\mathbf{N}$$$ and $$$\mathbf{C}$$$: the number of sitting players and hat colors, respectively. Then, $$$\mathbf{C}$$$ lines follow. The $$$i$$$-th of these lines contains two integers $$$\mathbf{A_i}$$$ and $$$\mathbf{B_i}$$$, as explained above. The last line of a test case contains $$$\mathbf{N}$$$ integers $$$\mathbf{P_1}, \mathbf{P_2}, \dots, \mathbf{P_N}$$$ representing that the $$$j$$$-th sitting player in clockwise order (starting from an arbitrary one) is wearing a hat of color $$$\mathbf{P_j}$$$.
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 number of sets of
at least $$$2$$$ and at most $$$\mathbf{N}-1$$$ contiguously sitting players that fulfill all the color
requirements.
Time limit: 20 seconds.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$2 \le \mathbf{C} \le \mathbf{N}$$$.
$$$0 \le \mathbf{A_i} \le \mathbf{B_i} \le \mathbf{N}$$$, for all $$$i$$$.
$$$1 \le \mathbf{P_j} \le \mathbf{C}$$$, for all $$$j$$$.
$$$3 \le \mathbf{N} \le 1000$$$.
$$$3 \le \mathbf{N} \le 10^5$$$.
3 3 2 1 1 1 1 1 1 2 5 2 1 1 1 2 1 2 1 2 2 3 3 1 2 1 2 2 2 1 1 3
Case #1: 2 Case #2: 9 Case #3: 1
In Sample Case #1, the total number of players chosen as geese must be $$$2$$$. There are only three possible ways to select $$$2$$$ players. The following color configurations are possible: $$$[1, 1]$$$, $$$[1, 2]$$$, and $$$[2, 1]$$$. The first one has two players wearing hats of color $$$1$$$, so it is not valid, but the other two are valid. Therefore the answer is $$$2$$$.
Sample Case #2 is the one illustrated in the statement, with color $$$1$$$ being yellow and color $$$2$$$ being blue. The total number of players chosen as geese in this case must be between $$$2$$$ and $$$3$$$, because selecting $$$4$$$ geese would require at least one color to be out of bounds. For cases with $$$2$$$ geese, the only requirement is that we do not select $$$2$$$ geese both wearing hats of color $$$1$$$; all $$$5$$$ such selections are valid. If choosing $$$3$$$ geese, the options are $$$[1, 2, 1]$$$, $$$[2, 1, 2]$$$, $$$[1, 2, 2]$$$, $$$[2, 2, 1]$$$, or $$$[2, 1, 2]$$$. All but the first one are valid, adding another $$$4$$$ valid options, for a total of $$$9$$$.
In Sample Case #3, notice that there can be hat colors that nobody is wearing. In this case, since there is only $$$1$$$ player wearing hat color $$$3$$$ and $$$1$$$ is not in range, the only valid way is to pick $$$0$$$ players wearing that hat color.
The Google Coding Competitions team is setting up a new theme park. As in any good theme
park, we want to have actors dressed up as mascots to interact with visitors. Because we
are in a rush to open, we decided to use the letters from CODE JAM
,
KICK START
, and HASH CODE
as mascots, for a total of $$$13$$$
different mascots (the letters ACDEHIJKMORST
).
The park's only attraction is a maze that has a set of $$$\mathbf{N}$$$ rooms numbered from $$$1$$$ to $$$\mathbf{N}$$$. Each room has a left exit and a right exit. Each exit takes the visitor to another room. Exits cannot be used in reverse; for example, if room $$$2$$$ has an exit to room $$$3$$$, you cannot go back from room $$$3$$$ to room $$$2$$$ unless room $$$3$$$ also happens to have an exit to room $$$2$$$.
We want to place exactly one of our $$$13$$$ mascots in each room. Each letter may be present in zero, one, or more rooms of the maze. To increase variety, we want to place mascots so that any three (not necessarily distinct) rooms that a visitor can visit consecutively have three different mascots.
Can you help us choose a mascot for each room such that this goal is met, or let us know that it cannot be done?
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow. Each test case consists of $$$3$$$ lines. The first line contains a single integer $$$\mathbf{N}$$$, representing the number of rooms in the maze. The second line contains $$$\mathbf{N}$$$ integers $$$\mathbf{L_1}, \mathbf{L_2}, \dots, \mathbf{L_N}$$$, representing that the left exit from room $$$i$$$ leads to room $$$\mathbf{L_i}$$$. The third and last line contains $$$\mathbf{N}$$$ integers $$$\mathbf{R_1}, \mathbf{R_2}, \dots, \mathbf{R_N}$$$, representing that the right exit from room $$$i$$$ leads to room $$$\mathbf{R_i}$$$.
For each test case, output one line containing Case #$$$x$$$: $$$y$$$
,
where $$$x$$$ is the test case number (starting from 1) and $$$y$$$ is IMPOSSIBLE
if there is no way to assign mascots while obeying the rules explained above. Otherwise, $$$y$$$
is an $$$\mathbf{N}$$$ character long string. The $$$i$$$-th character of $$$y$$$ should be an uppercase letter
from the set ACDEHIJKMORST
, representing that you wish to assign that mascot to the
$$$i$$$-th room.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$\mathbf{L_i} \neq i$$$, for all $$$i$$$.
$$$\mathbf{R_i} \neq i$$$, for all $$$i$$$.
$$$1 \le \mathbf{L_i} \lt \mathbf{R_i} \le \mathbf{N}$$$, for all $$$i$$$.
Time limit: 20 seconds.
$$$3 \le \mathbf{N} \le 100$$$.
Time limit: 45 seconds.
$$$3 \le \mathbf{N} \le 10^5$$$.
4 3 2 1 1 3 3 2 6 3 1 4 1 2 3 5 3 5 2 4 5 20 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 2 19 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 3
Case #1: IMPOSSIBLE Case #2: TSHIRT Case #3: HCJKSHCJKSHCJKSHCJKS Case #4: CODEJAMROCKSTHEMOST
Sample Case #1 is the image in the problem statement. It is possible to visit rooms 1, 2, and 1 consecutively (which visits room 1 twice), so the case is impossible.
Sample Case #2 has the following layout (blue arrows represent the left exits and red arrows represent the right exits):
One of many valid answers is to assign mascots as indicated. Notice that although we do not
need to assign two T
mascots in this case, we have done so in a way that does
not break the rules.
Sample Cases #3 and #4 are possible, but require the use of multiple copies of some mascots.
Ueli and Vreni are playing a game. The game's board is a tree with $$$\mathbf{N}$$$ vertices, all initially colored blue. They alternate turns, with Ueli going first. In each turn, a player must choose a blue vertex, together with any subset (possibly none or all) of its blue neighbors, and color all those vertices red. If at the start of a players' turn, all vertices are red, then that player loses the game and the other player wins the game.
In the example game below, Ueli colored vertex $$$3$$$ red in their first turn. Then, Vreni chose vertex $$$2$$$ for their turn and colored both it and its neighbor (vertex $$$1$$$) red. Because all vertices are now red, Ueli loses and Vreni wins.
Ueli and Vreni have noticed that it is much easier for Ueli to win this game because he has the first turn. Therefore they have adopted the following procedure: first, Ueli chooses an integer $$$\mathbf{N}$$$. Then, Vreni chooses any tree with $$$\mathbf{N}$$$ vertices. And then they start playing as described above, with Ueli taking the first turn.
Vreni is hopeful that being able to choose the tree can help her overcome the disadvantage of going second. Can you demonstrate how Vreni can win games in this setup?
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 an integer, $$$\mathbf{T}$$$, the number of test cases. Then, $$$\mathbf{T}$$$ test cases must be processed.
For each test case, your program must first read a line containing a single integer $$$\mathbf{N}$$$, the number of vertices that Ueli has chosen. Then, your program must output $$$\mathbf{N}-1$$$ lines describing the edges of the tree Vreni should choose. The nodes of the tree are numbered $$$1$$$ through $$$\mathbf{N}$$$. Each line must represent a distinct edge of the tree with $$$2$$$ integers between $$$1$$$ and $$$\mathbf{N}$$$: the two vertices the edge connects. The edges must represent a tree. The two integers within a line may be in either order, and the $$$\mathbf{N}-1$$$ lines themselves may be in any order.
After that, your program must read a line containing a single integer $$$\mathbf{M}$$$, the number of games that you need to play on this tree. These games are played independently; in other words, all vertices of the tree are blue at the start of each game.
For each of the $$$\mathbf{M}$$$ games, you need to process some number of exchanges until the game is over. Each exchange consists of a turn from each player.
For each exchange, your program must read two lines describing Ueli's turn first. The first of those lines will contain an integer $$$\mathbf{K}$$$, denoting the number of blue vertices to be colored red. The second of those lines will contain $$$\mathbf{K}$$$ distinct integers $$$\mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_K}$$$ describing the blue vertices to be colored red. $$$\mathbf{K}$$$ will be at least 1, and each $$$\mathbf{A_i}$$$ will be between 1 and $$$\mathbf{N}$$$, inclusive. Vertices $$$\mathbf{A_2}, \mathbf{A_3}, \dots, \mathbf{A_K}$$$ will all be neighbors of vertex $$$\mathbf{A_1}$$$.
After that, your program must output Vreni's choice for their turn in the same format: the first line with the number of blue vertices to be colored red, followed by the second line with the numbers of those vertices, in such an order that all vertices except the first one are neighbors of the first one.
If all vertices are red after Vreni's turn, it means that Vreni has won and this game is over. The next game starts immediately if there is one. If this was the last game for this test case, then the next test case starts immediately if there is one. If this was the last test case, the judge will send no further input to your program, and the program must send no further output.
On the other hand, if all vertices are red after Ueli's move, it means that Vreni has lost and therefore your program did not pass the test case. In this case, instead of starting a new exchange by printing the last move that colors all remaining blue vertices red, the judge will print a single number $$$-1$$$ and will not print any further output, and will not process any further games or test cases.
If the judge receives an invalidly formatted or invalid line (like outputting an unexpected number of integers, or integers out of range, or outputting a set of edges that do not form a tree, or trying to color a vertex that is already red, or trying to color a vertex that is not a neighbor of the first vertex colored in this turn) from your program at any moment, the judge will also print a single number $$$-1$$$ and will not print any further output. If your program continues to wait for the judge after receiving a $$$-1$$$, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment.
The judge is deterministic. In other words, if you make two attempts that print the same numbers, you will get the same inputs from the judge. However, of course the judge can make different moves in different games on the same tree.
Time limit: 60 seconds.
Memory limit: 1 GB.
$$$1 \le \mathbf{M} \le 50$$$.
$$$\mathbf{T}=1$$$.
$$$\mathbf{N}=30$$$.
$$$1 \le \mathbf{T} \le 10$$$.
$$$31 \le \mathbf{N} \le 40$$$.
No two test cases use the same value of $$$\mathbf{N}$$$.
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.
Note that the testing tool just makes random choices for Ueli unless it can win in one turn. Therefore, it might be easier to win against the testing tool than against the real judge, which will try harder to win.
2
3
1 2 1 3
1
1 3
2 1 2
4
1 2 2 3 2 4
2
3 2 1 3
1 4
2 2 3
1 1
-1
Note that the sample interaction does not satisfy the constraints of either test set, as its $$$\mathbf{N}$$$ values are too small. It is only presented to clarify the input and output format.
Below is an illustration of Case #2, Game #1 at the beginning and after each turn:
Below is an illustration of Case #2, Game #2 at the beginning and after each turn:
In the original GoroSort problem from 2011, Goro could hold as many elements in place as he wanted; using the terminology of this problem, he could create arbitrary many box color groups with $$$1$$$ ball (element) each. But unlike in this problem, he was only allowed to use at most one color group of size greater than $$$1$$$. That made the optimal strategy relatively straightforward: he could repeatedly permute all list elements that were not in the correct places.
That strategy puts one additional element in the right place each turn, in expectation, which is clearly too slow for this problem. (Our version of that solution takes almost $$$100000$$$ rounds!) What is more surprising is that the crux of the original problem — namely, thinking in terms of expected numbers of elements that become correctly placed after the bump — can even be misleading in this problem!
It is intutively clear that any elements that are already in the right place should be left alone (i.e., each should be put in its own color group). It also seems reasonable to not break up pairs of elements that are swapped (i.e., each is in the other's place). We can also reasonably guess that splitting such a pair would be useless, and that putting additional elements in that group would be worse than handling those other elements in their own group(s).
What about the other elements? One very tempting strategy is to try to pair them up into "trespasser pairs" such that one member of the group is in the other member's place. It may not be possible to do this with every element, but we can, e.g., find a way to tack leftovers onto existing trespasser pairs.
Consider a trespasser pair ($$$x, y$$$), where $$$x$$$ belongs where $$$y$$$ is and $$$y$$$ belongs somewhere else entirely. The judge's "bumping" (permutation) process will put $$$x$$$ in the right place with probability $$$\frac{1}{2}$$$. So if we somehow manage to create around $$$\frac{\mathbf{N}}{2}$$$ trespasser pairs, each bump will put around $$$\frac{\mathbf{N}}{4}$$$ more elements in the right places. This seems quite good, and it is good enough to pass Test Set 1, but not the other two. (Our trespasser-pair-based solutions take between $$$15000$$$ and $$$16300$$$ rounds, depending on the care taken with implementation details.)
Any permutation — and therefore any state in this problem — can be described as a multiset of cycles of particular lengths. For example, each element that is already in the correct place is a $$$1$$$-cycle, and each pair of swapped elements is a $$$2$$$-cycle.
If we try to implement the pairing idea above in a greedy way, we may miss some opportunities to form trespasser pairs. We can get as many as possible by first finding all the cycles, then going through each cycle and chopping it into trespasser pairs, plus perhaps one "trespasser trio" at the end. (A trespasser trio is a set of elements $$$x, y, z$$$, in some order, such that $$$y$$$ is in $$$x$$$'s place, $$$z$$$ is in $$$y$$$'s place, and $$$z$$$ belongs outside of the group.) These improvements (especially creating trespasser trios where needed) help a lot, but not enough to pass Test Set 2; our trespasser pairs + one trio solution takes around $$$13100$$$ rounds.
But what if we leave the cycles as they are, and make each cycle its own permutation group? Now we do much better, and pass Test Set 2 as well (but not Test 3; we take about $$$11800$$$ rounds). Why is this cycle-based strategy so much better than the trespasser pair strategies?
Here's the problem with chopping into trespasser pairs. Suppose that we have a $$$4$$$-cycle like $$$2 3 4 1$$$. If we split it into two trespasser pairs $$$2 3$$$ and $$$4 1$$$, we will (in expectation) put one element in the correct place. But, as we will see later on, we get the same expectation of $$$1$$$ if we designate the entire cycle as one group.
Does this necessarily mean these strategies are equally good? Let's set our expectations appropriately! We really care about the expected total number of rounds to finish sorting, so let's work toward calculating that instead. First we observe that:
Comparing these two probability distributions directly, and canceling out the parts that are the same, we need to know which is better:
Now we can assess each of those states in terms of the expected number of rounds to completion. A $$$3$$$-cycle turns out to take $$$3$$$ rounds, in expectation, to become all $$$1$$$-cycles. (This comes from solving $$$\mathbf{E}[3] = 1 + \frac{1}{3} \cdot \mathbf{E}[3] + \frac{1}{2}\mathbf{E}[2] + \frac{1}{6}(0)$$$, and using the fact that $$$\mathbf{E}[2] = 2$$$.) By a similar analysis, two $$$2$$$-cycles take $$$\frac{8}{3}$$$ rounds, in expectation, to become all $$$1$$$-cycles. (And if we are lucky enough to reach four $$$1$$$-cycles directly, $$$0$$$ additional rounds are needed.)
Therefore, chopping up a $$$4$$$-cycle into two trespasser pairs is strictly worse than leaving it as is! We wouldn't have known this if we had argued purely based on the expected number of correctly placed elements; it also matters what we leave behind. Intuitively, the trespassers can only be dealt with after their companions have been correctly placed, so the chopping strategy is less parallelizable. But we shouldn't assume this will always be true no matter how we chop...
It's tedious to perform the above analysis for cycles longer than $$$4$$$. But we shouldn't give up hope. The expectations for the two strategies were the same for $$$4$$$-cycles, but will that hold up in general?
Let's think about how many cycles we expect to see in a random permutation of length $$$\mathbf{N}$$$. You may have heard of the following problem: everyone loses their hats all at once, and each person puts on a random hat; in expectation, how many people get their own hats back? The probability that the each person gets their own hat is $$$\frac{1}{\mathbf{N}}$$$, and then by linearity of expectation, the total number of instances of someone getting their own hat is $$$\frac{1}{\mathbf{N}} \cdot \mathbf{N} = 1$$$.
So this gives us the expected number of $$$1$$$-cycles. We can make a similar argument about $$$2$$$-cycles: there are $$${\mathbf{N} \choose 2}$$$ distinct pairs of elements that could form a 2-cycle, and for each one, the probability that each has the other's element is $$$\frac{1}{\mathbf{N}} \cdot \frac{1}{\mathbf{N}-1}$$$. This all boils down to $$$\frac{1}{2}$$$. Indeed, the answer for general $$$k$$$-cycles is $$$\frac{1}{k}$$$.
Then how many total cycles should we expect? It's $$$\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{\mathbf{N}}$$$. You may recognize this as the expression for the $$$\mathbf{N}$$$-th harmonic number. The harmonic numbers grow rather slowly; $$$H_{100}$$$, for example, is just over $$$5$$$.
Therefore, if there are only around $$$5$$$ cycles in our initial random permutation of length $$$\mathbf{N} = 100$$$, we expect to place around $$$5$$$ elements. But if we chop the cycles into, say, $$$50$$$ trespasser pairs, we should expect to place around $$$25$$$ elements! How can it possibly be better to leave such large cycles alone? Does the argument about leaving more mess behind really still hold up?
One issue with chopping into pairs is that, intuitively, many roads to completion include forming one or more $$$4$$$-cycles, and we have now seen that the pair-chopping strategy mishandles them. (And now we have reason to suspect that it mishandles larger cycles as well).
What if we chop a cycle into chunks larger than pairs? For example, if we chop a $$$6$$$-cycle into two trespasser trios, each of them will produce $$$2 \cdot \frac{1}{3} = \frac{2}{3}$$$ correctly placed elements in expectation. That's $$$\frac{4}{3}$$$ overall, which is less than the $$$3 \cdot \frac{1}{2} = \frac{3}{2}$$$ we would have gotten from chopping into trespasser pairs. But these trespasser trios leave less of a mess; each one can only leave one element to clean up later, so there will be two such elements as compared to three.
It is hard to directly weigh the costs of cleaning up these leftover elements against the benefits of correctly placing more elements in expectation. The math for our $$$4$$$-cycle example was already a bit cumbersome to carry out in a timed round, and there is not a strong incentive to do even more of it when the local testing tool can quickly tell us how well a strategy does, and when all three test sets are Visible. Indeed, we can find that leaving all cycles of length less than $$$6$$$ intact, and breaking all cycles of length $$$6$$$ or more into trespasser trios (or trespasser sets of four or five, when there are extra elements) does much better than leaving all cycles intact, and lets us pass Test Set 3, taking about $$$10950$$$ rounds.
We can do even better by choosing different chunk lengths (e.g. break each cycle of length $$$c$$$ into chunks of size roughly $$$\sqrt{c}$$$, to get down to around $$$10500$$$ rounds), but that is not necessary for this problem.
Given the lower limits for $$$\mathbf{N}$$$, we can check all possible contiguous subsets (as long as we check each one quickly). One way is to iterate through all possible starting indices for the contiguous subset. Then, for each starting index, we can loop through all possible sizes in order.
We can keep track of the counts of each color as well as the number of hat colors have counts that are invalid (not $$$\mathbf{0}$$$ and not in the acceptable range for that color). Note that when we extend our subset, only the hat color that the newly added child has is affected. If this changed whether or not this color is valid, we update the count of valid and invalid colors as needed. Then, if this count is equal to $$$\mathbf{C}$$$, we can increment our total answer (as long as the subset is of length at least $$$2$$$ and at most $$$\mathbf{N} - 1$$$).
Because checking each contiguous subset is done in $$$O(1)$$$ time and there are $$$O(\mathbf{N}^2)$$$ subsets to check, our time complexity for Test Set 1 is $$$O(\mathbf{N}^2)$$$.
For Test Set 2, $$$\mathbf{N}$$$ is too large to check each contiguous subset separately. We can speed this up by using a Segment Tree to check all possible subset lengths at once (for each starting index). We can remove the cyclic part of the problem by appending the array to itself.
Given a starting index, $$$S$$$, each color has two (possibly empty) ranges of ending indices that are valid for this color (meaning the number of hats of this color is either 0 or in the acceptable range). If we use add $$$1$$$ to our segment tree for each value in these ranges and for all colors, we can count the number values (ending indices) in our segment tree for the range $$$[S + 1, S + \mathbf{N} - 2]$$$ that have a value of exactly $$$\mathbf{N}$$$. This count will tell us how many contiguous subsets are valid for our current start index.
Now, all we need to do is update our segment tree when moving the starting index to the right. Notice that moving our starting index to the right by one will only affect the valid end index ranges for the hat color of the child being removed (the one that previously was our starting index). If we precompute for each position, where is the next occurrence of that child's hat color, we can compute how the valid ranges for this color will move in $$$O(1)$$$. The exact implementation of this is left as an exercise to the reader.
Given that our segment tree operations each take $$$O(\log \mathbf{N})$$$ time, we can count the number of contiguous subsets for each starting index and move the starting index to the right both in $$$O(\log \mathbf{N})$$$ time. This gives us a final time complexity of $$$O(\mathbf{N} \log \mathbf{N})$$$.
This is a variation of the classic graph coloring problem, where the rooms, exits, and mascots of the problem form the nodes, edges, and colors of a graph.
Cases where there is a cycle of length two (two rooms x and y where there is an exit from x to y and an exit from y to x) are obviously impossible. We will show later that these are the only impossible cases, by giving an algorithm that always produces a coloring for graphs with no cycles of length two.
Given the low limits, it is possible to implement a backtracking solution: recursively try coloring each vertex in each color. There are techniques which will help speed up the solution. For example, you can keep track of the colors that shouldn't be used for a vertex (since one of its neighbors was previously colored with that color).
However, plain backtracking algorithms are unlikely to work for Test Set 2, since early color assignments might make it impossible to color later nodes, and it can take a long time until those early assignments are revisited by the algorithm.
Consider the graph G' which has an edge from one node to another if there is a path of length 1 or 2 linking them in G. That is, G' contains the edge (v,w) if (v,w) is in G, or there is a pair of edges (v,x) and (x,w) in G. It is sufficient to color G' so that no adjacent pair of nodes has the same color.
Since each node in G' has outdegree at most 6 (2 nodes that are one edge away in G and 4 nodes that are two edges away in G), the average indegree must be at most 6, and so at least some individual node V must have degree at most 6 + 6 = 12. No matter what colors were chosen for this node's neighbors, there is always at least one different color for this node because it has at most 12 neighbors.
The only case when the coloring is impossible for G' is when it contains a self-loop. In such a case it is also impossible for G.
Using these observations the following algorithm can be used to color G':
Here is one way to implement this solution efficiently:
Every step of the algorithm can be done in linear time, so the overall time complexity of the solution is linear.
Some heuristic approaches, like local search, can also be made to work if implemented efficiently.
This problem describes an impartial game which can be analyzed using the Sprague-Grundy theorem.
However, the number of possible states in the game is quite big. There can be $$$2^{\mathbf{N}}$$$ sets of blue vertices, and even after we use the Sprague-Grundy theorem to reduce the problem to consider only connected sets of vertices, the number of states is still big. For example, a star which has the center vertex connected to $$$\mathbf{N}-1$$$ leaves has $$$2^{\mathbf{N}-1}+\mathbf{N}-1$$$ connected sets of vertices.
We could go a bit further and notice that isomorphic subtrees can only be considered once, which reduces the number of states much more. We do not know the exact number, but the worst trees we were able to find had between 7 and 8 million non-isomorphic connected subtrees for $$$\mathbf{N}=40$$$. This is still quite hard to process within the time limit given that the processing for each state becomes quite expensive, with tree isomorphism involved.
So how could we make things simpler for ourselves?
One approach is to try to construct a concrete tree by hand that is winning for the second player. The game for this problem was intentionally chosen in such a way that this is not easy: for example, every chain (a tree where each vertex is connected to the previous one, $$$1-2-3-\dots-\mathbf{N}$$$) is winning for the first player, as they can take either 1 or 2 middle vertices and then make symmetric moves.
However, it turns out that for even values of $$$\mathbf{N}$$$ there are several relatively simple constructions. For example, consider a starlike tree consisting of the center vertex $$$1$$$ plus $$$\mathbf{N}-3$$$ chains attached to it, one chain with 3 edges ($$$1-2-3-4$$$) and all other chains with 1 edge ($$$1-5, 1-6, \dots, 1-\mathbf{N}$$$).
The number of chains with 1 edge is even, so if the first player takes the endpoint of one of them, we can take another one and arrive at a smaller starlike tree with the same property, unless there is just one left, in which case we simply have a single chain with 4 edges and 5 vertices and can win by taking one or three middle vertices of it.
If the first player takes the center vertex together with some neighbors, then we are left with one chain with 2 or 3 vertices, and some number of isolated vertices. We can choose either to eliminate the chain, or to reduce it to an isolated vertex, in such a way that the number of resulting isolated vertices is even and we will win.
If the first player takes two vertices of the longer chain together with the center vertex, then we are left with an odd number of isolated vertices, so we can take one of them and win.
If the first player makes the longer chain shorter, then we can take the center vertex together with some neighbors in such a way that an even number of isolated vertices remains.
If the first player makes a move in the middle of the longer chain such that we have a star plus a separate isolated vertex, then we can again take the center together with some of its neighbors in such a way that an even number of isolated vertices remains.
Finally, if the first player makes a move in the middle of the longer chain such that we have a star plus a chain with 2 vertices, then we remove one of the leaves of the star. If we and the first player keep removing star leaves with each move, then after one of our moves only one leaf will be left, so we will have two chains with 2 vertices each and we can do symmetric moves to win. And if the first player tries taking the center of the star, or do something to the chain with 2 vertices, then we can always get an even number of isolated vertices after our move.
We were not able to come up with a similar explicit construction for odd values of $$$\mathbf{N}$$$. Also, even for even values of $$$\mathbf{N}$$$ coming up with this construction was not required to solve the problem. You can find an alternative approach in the next section.
What can we do when $$$\mathbf{N}$$$ is odd, or when we cannot come up with the above construction for even $$$\mathbf{N}$$$?
The key idea is to consider some very restricted class of trees, so that:
We have found that many classes of trees work, for example:
Having chosen such a class, we can then quickly implement the nim-value computation, and then either do an exhaustive search over all trees in the class, or keep generating random trees in the class until we find at least one example for each value of $$$\mathbf{N}$$$ between 30 and 40.
It was also possible to choose a class of trees with enough diversity and fast enough nim-value computation, but that would still require to implement general tree isomorphism. This would of course complicate the implementation a bit more, but still allow to solve the problem. One such class is very narrow trees where vertex $$$i$$$ is connected either to vertex $$$i-1$$$ or to vertex $$$i-2$$$.
Having found the winning tree for each value of $$$\mathbf{N}$$$, we can then hardcode them in the solution we submit. We still need the nim-value computation code as part of the solution in order to actually play the game after printing the tree. This was, in fact, one of the reasons for making this problem interactive: had we just required printing a tree for a given $$$\mathbf{N}$$$, the submitted solutions would likely just consist of 10 constants, and it might be possible to just find a solution in a few guesses, at least for Test Set 1.
Of course, it might happen that you choose a class of trees that does not give a solution to all possible cases. However, given the diversity of classes that work in this problem, it is most likely possible to adjust your class slightly in such a way that you do not need to complicate the nim-value code too much, but that allows to find a solution. Of course, doing this quickly required a certain intuition or "feeling" of the problem.
While the contestants had the luxury of choosing a class of trees where finding nim-values is quick, they did not have to do it, and therefore the judge had to deal with arbitrary trees.
The judge had a very well-optimized computation of nim-values for the general case, using tree isomorphism to reduce the number of states it has to process. In the worst case we found for $$$\mathbf{N}=40$$$, it could find the nim-values for all states in about 70 seconds (this was optimized about 20x from our first version). However, we were not sure that the case we found is truly the worst (and this was another reason for making this problem interactive), and we also did not want the contestants to have to wait for a long time for the verdict.
Therefore we have introduced additional logic in the judge when considering the very first move of the game. We iterated over possible first moves in the order of increasing size of the largest connected component remaining after the move, and stopped iteration in two cases:
The order of checking the first moves ensured that only a few states would need to be visited to check the first option for the first move, because all connected components would have a size of at most 20 after it, therefore we would likely process quite a few first moves before we run out of the 500000 states budget. And for the values of $$$\mathbf{N}$$$ up to 33 or so, we would actually process all options for the first move. This allowed us to be relatively confident that we would catch most incorrect solutions, but still have the judge finish in 4 seconds per case.
After the first move, the judge always knew the nim-value exactly and played optimally.
The judge had to make another important decision: when it found itself in a losing position (which is the most important case to consider, as in the other case it could guarantee a win using the nim-values), which move should it do?
Initially the judge would make a random move in such situation. But then we noticed that even for the Test Set 1 solution described above, making random moves might not be enough to catch all bugs, since there are many bugs that would only be caught with a specific first move. Therefore, we have changed the behavior of the judge for choosing the first move: it tried to make such moves that would lead to different situations for the solution to handle after the first move in different games.
Two situations were considered different if they led to non-isomorphic configurations, with the additional step of collapsing $$$2K+1$$$ copies of the same subtree to 1 copy, and $$$2K$$$ copies of the same subtree to 2 copies, to avoid the judge wasting the games exploring different ways to remove leaves from a star. After the first move, if the judge was still in a losing position, it would make fully random moves.
Of course, this still left a possibility that some incorrect solutions would win all games against the judge, as it did not visit all possible states — there were at least 7 million states to visit potentially, but the judge had only 50 games, each visiting at most 40 states. However, we hope that the chances of this happening were quite low.