So! We hope you enjoyed the round. Internally, we called this round Trollforces, because as you knew, most solutions should be unexpected :)

Some fun fact: there are ~ 30 pictures in this round, totaling ~ 144 KB.

Here is the editorial, written with mixed point of views of all writers (hence "I" may refer to any of us).

330A - Тортминатор by dolphinigle

Long solution:

• Once an evil strawberry, always an evil strawberry (since they can’t be eaten).
• Thus, if a row cannot be eaten before any eat is performed, it can never be eaten.
• Same with column.
• Thus, you can know which columns and which rows you can eat.
• Just try to eat them all and calculate how many cells you actually eat.

Short solution:

• A row or a column cannot be eaten if it has at least one strawberry.
• A cell cannot be eaten if both its row and its column cannot be eaten -- otherwise you can eat the row/column and eat it!

If there are r' rows that cannot be eaten, and c' columns that cannot be eaten, then there are r' * c' cells that cannot be eaten -- a cell such that both its row and columns cannot be eaten.

Since all other cells can be eaten, answer is R * C — r' * c'.

330B - Строим дорогу by jonathanirvings

• Since m < n/2, there exists at least one node that is not incident to any edge.
• The constraints can be satisfied if and only if the graph is a star graph: http://en.wikipedia.org/wiki/Star_(graph_theory). We can just create a star graph centered with the node and connect it to all other nodes.

330C - Очищение / 329A - Очищение by dolphinigle

• Obviously the minimum possible answer is n (why?). But is it always possible to purify all the cells with n spells?
• If there exist a row consisting of entirely "E" cells and a column consisting of entirely "E" cells, then the answer is -1. This is since the cell with that row and that column cannot be purifed.
• Otherwise, without loss of generality let's suppose there is no row consisting entirely of "E". Then, for each row, find any "." cell. Purify it. The case with no column consisting entirely of "E" is similar.

330D - Биридианский лес / 329B - Биридианский лес by dolphinigle

The only non ad hoc problem in the round! ...sort of. Despite the very long problem statement, the solution is really simple.

• We should take any shortest path from S to E (yes, any!). We will see why this is optimal at the end.
• If a breeder can reach E faster than or equal to us, then he will battle us. This is since he can simply walk to E and waits for us there.
• Otherwise, they can never battle us by contradiction. Assume they battled us, but they cannot reach cell E from their location faster or equal to us. If the battle us in cell X, then cell X is part of the shortest path from S to E that you are travelling. Since he is able to battle us there, he must be able to arrive at cell X <= us. But then, that means he can walk from X to E and reach E before or equal to us! Contradiction.
• This is optimal, since any breeder that we battle in this solution must also be battled in any other solution (the other breeders should immediately go to E and wait).
• You can use Breadth-First Search once from exit cell to obtain the shortest paths from each breeder to it.

Thoughts

I tried to make this clearer by separating the paragraphs by topic. Did it work well?

Btw, mikemon is pronounced "mi-ke-mon", not "mike"-mon -- similar to how Pokemon is pronounced "po-ke-mon" not "poke"-mon >:).

330E - Перестроим граф / 329C - Перестроим граф by fushar

First, I would like to apologize the missing node 3 in the picture of the first example. It was a mistake :(

Intended, deterministic solution:

• If n <= 7, brute force all possible subsets of the edges (at most 2^(7 * (7 — 1) / 2)), and check if they satisfy the constraint.
• Otherwise, a solution always exists. Here is how to construct one.
• Partition the nodes into connected components. Note that each component will be either a cycle or a chain. List the nodes of each component in order of the cycle/chain. For example, for the first example, the partition would be { <1, 2, 3>, <4, 5, 6, 8, 7> }. For each component, we do not care whether it is a cycle or a chain.
• For each component, reorder the nodes such that all nodes in the odd positions are in the front. For example, component ABCDEFGHI is reordered into ACEGIBDFH. (Each letter represent a node.)
• Pick any component with the largest number of nodes. If the number of nodes in it is even, swap the first two nodes. For example, ABCDEFGH -> ACEGBDFH -> CAEGBDFH.
• For each other component, insert the nodes alternately between the largest component. For example, if the other components are acebd and 1324, insert them as follows: CAEGBDFH -> C a A c E e G b B d DFH -> C 1 a 3 A 2 c 4 EeGbBdDFH.
• Connect adjacent nodes so that the number of edges is m, connecting the last with the first nodes if necessary.

The deterministic solution is very tricky. Therefore, I made the pretest quite strong. Some tricky cases:

• 4-cycle and 1-chain (covered in the example)
• 3-cycle and 3-cycle
• 4-cycle and 3-cycle (very tricky! many submissions failed on this case)

Actually, we can do brute force when n <= 6, but this requires a special handling: when the largest component has 4 nodes, we should swap the first node with the third node (not the second). This is to handle the 4-cycle-and-3-cycle case.

Troll solution, nondeterministic:

Do the following many times:

x = [1, 2, 3, ..., n]
random_shuffle(x)
for i = 1 to m:
    if the edge (x[i], x[(i+1)%n]) is in input:
        // fail this iteration, repeat the entire procedure

if didn’t fail:
    // we obtain a solution!
    for i = 1 to m:
        print x[i], x[(i+1)%n]

If didn’t obtain solution:
    print -1

So, the question is, for large n what is the probability that a permutation is not "bad"? This can be computed (or at least approximated) similar to computing derangement probability -- I obtained a result above 0.1, which means in 100 iterations it should succeed if there was a solution. ...There is a solution if n > 7, so it should work.

329D - Злой храм и двигающиеся камни by dolphinigle

Post your solution in the comment! Here's mine for the last case! (approximately 120,000 sounds). You can get the number of sounds your solution produces when submitting it to the server.

1 copy of
v<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v^

24 copies of
v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.
v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^

24 copies of
v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^
.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^

1 copy of
>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^
....................................................................................................

1 1

I wonder if there’s a solution with ~150,000 sounds or more... the (theoretical) upper bound is 100^3 / something, so it may be feasible...?

329E - Зло by dolphinigle

The solution to this problem is actually quite simple: 4122927

This problem asks us to prove something very long (the proof below is of 80+ lines).

Assume that the number of cities is at least 4. The case where it's less than 4 is trivial.

First, we will assume that no two cities will have same X or Y coordinates. To get this assumption, we can juxtapose every city very slightly that it will not change the answer.

The keys are : A) "Manhattan Distance", B) the tour starts and ends at the same city. Suppose we know a tour. The total distance traveled will be |X1 — X2| + |Y1 — Y2| + |X3 — X2| + |Y3 — Y2| ...

Let's separate the X and Y coordinates for simplicity. Note that each city will contribute twice to this value, for example X2 was in |X1 — X2| and |X3 — X2| in the example above. Manhattan distance implies that each of these values will either be multiplied by +1 or -1, depending on the other coordinate being compared in the absolute term. Furthermore, the number of values that are multiplied by +1 must equal the number of values that are multiplied by -1 (since in each absolute term, one is multiplied by +1 and the other by -1). This directly implies an upper bound on the maximum length of the tour.

If we list all the X coordinates of the cities, and we put each of them twice in this list, and sort them, the maximum will be gained if we multiply the last half by +1 and the first half by -1, and finally summing them up. Note that all of these reasoning applies to the Y coordinate, and summing both maximum of X and Y, we receive an upper bound on the length of the tour.

If we can find a tour with this length, our job is done. In some case, it's possible. Let's investigate!

First, if we have the medians of the X and the Ys as in the list above, we can separated the field like below :

 A  | B
    |
---------
    |
 C  | D

The lines corresponds to the median for both X and Y.

At most one city will lie on each of the median lines (recall our assumption that X and Ys are distinct).

Let's call each A B C and D as boxes. Below, we will refer box A as simply A (applies to B, C, and D too)

To obtain the value above, from a city in B we must go to a city in C. Same reasoning yields : B->C, C->B, A->D, D->A. Here, pairs of cities become apparrent, A and D are paired as well as B and C.

First, if either A+D is empty or B+C is empty, then we can obtain the upper bound above. We simply alternates between the two remaining pair. So let's assume that A+D is not empty and B+C is not empty.

First, let's investigate the relationship between B and C (A and B will also exhibits this relationship).

Theorem 1:

|B — C| <= 1.

Why:

First, if there are no cities in the medians or there is a single city in the center of the median :

A median divides the region into two areas with the same number of cities, so we have:

a) A+B = C+D
b) A+C = B+D

substituting A from a to b yields :

(C+D-B)+C = B+D
2C = 2B
B = C

And the theorem follows.

Next, suppose there are two cities in the median, one for each median line :

Let's suppose the median is one above and one on the right. All other cases will be similar. By definition of median...

a) (A + B + 1) = (C + D)
b) (A + C) = (B + D + 1)

Substituing a into b yields

(C + D - B - 1 + C) = (B + D + 1)
2C = 2B + 2
C = B + 1

which also implies A = D

Applying the same technique to other cases will give:

C = B and A = D+1
C = B-1 and A = D
C = B and A = D-1

And the theorem follows.

Note also that the one with the extra 1 city will be the one that is not adjacent to any median city (adjacent being the city lies in the boundary of the box)

OK, so in the following observations, we will assume the upper bound (that is, the sorted list of both X and Ys have their first half multiplied by -1 while the rest by +1), and trying to find a solution that's as close as possible to this upper bound.

The following will be another case analysis.

Theorem 2:

If there are two cities in the medians (that is, one in each median line), then the upper bound can be achieved.

Why:

We use pair of boxes to denote either A and D or B and C. From the second part of the proof for theorem 1, there will be a pair of boxes that contain different number of cities. Let's pick this pair, and start at the one with the most boxes. We keep alternating with its pair until we end up back in our starting box. Then, we simply move to either of the median city. From there we move to the other pair of box, the farthest one of the two. Alternate between the two, go to the other median city, and return to the starting city. It's easy to see that this will be optimal and have the upper bound as its value.

Now, let's see if there are no cities in the medians. First of all, this implies that the number of cities is even. Second, this implies that our upper bound which has the X and Y lists as -1 -1 -1 ... -1 1 ... 1 1 1 will not work (since this implies we have to continuously alternate between the two pairs of boxes, however, we can't switch between the pair of boxes). So, at least a modification would be required. The smallest possible modification is obtained by swapping the medians, that is, it becomes : -1 -1 -1 ... -1 -1 1 -1 1 1 ... 1 1 1. This is sufficient. Why? So, there are two cities that changes since the number of cities is even. Furthermore, these two cities will be the closest to the median line (let's assume these coordinates are X, that is, they're the closest to the vertical median line) and lies at two different boxes. Then, we proceed as follows. We start at one of these two cities. Alternate and end at the other side. If the other city is at that box, we make it so that we end at that city, and in this case, we can move to a city in the other box pair while respecting the list of X coordinates (we can do so since this city is the closest to the median line). Otherwise, the city will be in the other pair of boxes. We simply move there and it can be shown that we still respect the list of X coordinates. Alternate and at the end, go back to the starting city. All of these can be shown to still respect the list above.

This is optimal since this is the next largest possible upper bound if upper bound cannot be achieved.

Now, if there is a single city in the center of both medians, then the upper bound cannot be achieved. To see this, the upper bound can only be achieved if from a city in a box we move to another city in its box pair or to the center city. However, since both pair of boxes contains a city, we will need to move at least twice between them. Since there's only one center city, this is not possible.

Observe that this case implies an odd number of cities. Hence, we can't simply swap the median since it swaps the x coordinates of the same median city. Instead, we do this :

-1 -1 ... -1 -1 1 1 -1 1 ... 1 1

or

-1 -1 ... -1 1 -1 -1 1 1 ... 1 1

That is, we swap to either one of the neighboring city. With the same reasoning as above, we can show that we respect this list of X coordinates.

To achieve O(N) expected performance, note that the only operations we need are : grouping elements into boxes and median finding. Both can be done in expected O(N) time (expected since although there is a worst-case O(N) selection algorithm, it's ugly).

Thoughts:

Actually I intended to reword this into a three-paragraph weird story, but that seems a little too evil >:), so it was left out.