After two consecutive Div. 2 contests, we hosted another Div. 1 + Div. 2. The hard problems of the round were authored by tourist. We'd like to thank him for all the effort he's put into preparing the tasks.

The notoriety of the author attracted a large number of people, and once again, we broke the records of registered users and users who submitted at least one solution. Over 500 people managed to solve at least one problem.

Initially, we were planning on having a regular round with 7 problems and a constest duration of 2 hours. While preparing Tree Anitchain (Hard), tourist thought it's a really nice problem to ask for any valid permutation, not necessarily the first lexicographical one. This is how Tree Antichain (Easy) was born. We decided to increase the contest duration to 2 hours and 30 minutes. It's interesting to note that the best strategy was to jump straight to the hard version, and then just submit the same code for the easy one. However, only 8 out of the 24 users who solve both did this. Missing on the optimal strategy didn't stop user-2726 from winning, though.

The second hardest problem, Parallel Lines, was solved by 10 people, indicating a harder than usual task. Many others had lots of wrong submissions, hoping to exploit potentially weak tests. This was not the case, as tourist spent a lot of effort in order to fail wrong probabilistic solutions.

The last problem, Checkroom Hooks, was really hard, with only 2 accepted solutions. Besides user-2726 and user-3479, user-3237 was really close to solving it too (he would've won the contest).

We hope you had a great time participating. Congratulations to the winners:

1. user-2726
2. user-3237
3. user-1749
4. user-2816
5. user-3924

We also chose the winners of the random prizes: csacademy.com/code/e7HBBEHv

Congrats user-8123 for winning 50$ or a CS Academy t-shirt and user-4010 for winning a Skype lesson with user-2724!

Solution

For each size between $1$ and $100$ we can count how many left shoes and right shoes we have. The number of pairs of a certain size we can make is equal to the minimum of these two values.

Official implementation

Solution

Let's say we are going to spend $N$ of the $K$ dollars to increase the attack. Then $A + N * X = S + (K - N) * Y$, so $N = \frac{S + K * Y - A}{X + Y}$. We have a solution if this value is an integer in $[0, K]$.

Another solution is to binary search the value of $N$. For a fixed value, if the final $A < S$, we need to increase $N$, otherwise decrease it.

Official implementation

Editorial solution:

Solution using binary search:

Solution

Let's call conflict a pair of adjacent elements such that $|A_i - A_{i+1}| > K$. If we swap two elements with indices $i$ and $j$ we can only solve conflict between $A_i$ or $A_j$ and their neighbours. So there are at most $4$ conflicts we can solve.

We can start by identifying all the initial conflicts. If there are more than $4$, we have no solution. If there is no conflict, the array is obviously valid. Otherwise, let's say we take the first conflict between $A_i$ and $A_{i+1}$. One of these two elements should be involved in the swap. We can take one of them and check all the $N-2$ possibilities. There are a two things we need to check:

• The swap doesn't create new conflicts
• The initial conflicts are solved

Official implementation

Solution

There is no solution if the tree is a star, because the internal vertex neighbours all the $N-1$ leaves.

In all the other cases, it is possible to build a solution. Suppose we color the vertices black and white such that there is no edge connecting vertices of the same color. Because a tree is bipartite, we can always find such a coloring.

If we just print all the white vertices, followed by all the black vertices, the only potential pair of adjacent vertices that can be connected by an edge is the last white vertex and the first black one. So if we can find one pair of white and black vertices that are not connected, we can build a solution. If the graph is not a star, it must contain some path of length $\geq 3$. On such a path, the first vertex and the last vertex of opposite color don't share an edge.

Official implementation

Solution

Let's analyse an easier version of this problem, where the only nodes we can select are leaves. Let's say we have $K = 2^N$ leaves and we label them from $0$ to $K-1$, from left to right.

If we are allowed to select only $1$ leaf, we can choose any of them. If we are allowed to choose $2$ leaves, one of them should be from the first half, the other one from the second half. If we can choose $4$ leaves, each of them should be from a different quarter. In general, if we can select $2^X$ leaves, we divide the leaves in buckets of size $\frac{K}{2^X}$ and we can take a leaf from each bucket. If the number of leaves is not a power of two, we can build the solution for the closest power of two. Then we eliminate some of the selected leaves until we are left with the desired number of nodes.

In the general case where we can select nodes of different depths, we can use the same principle. We start building the solution from the leaves and move up towards the root. Let's say we've selected the leaves, and we want to select the nodes at depth $N-1$. There's no point to select the parents of the selected leaves, as they will not mark any extra edges. Even more, if the leaves were from distinct buckets of size $2^X$, their parents will be from distinct buckets of size $2^{X-1}$. If there are any buckets of size $2^{X-1}$ that don't contain any parent, we can use them to select the nodes of the current depth. If we are still allowed to select some extra nodes for the current depth, we can split all the buckets in half and select a node from each half that doesn't contain an already selected node or a parent. We can repeat this step while necessary, until we select all the nodes at the current depth or we hit the limit.

Official implementation

Editorial implementation:

Another approach, which sets nodes from top to bottom

Solution

As you can read in the editorial for the easy version, we have a solution if the graph is not a star.

Now let's say we chose a prefix $A_1, A_2, ... A_K$ of the permutation and we want to check if it's possible to build a solution starting with this prefix. It turns out we can always do this if by removing vertices $A_1, A_2, ... A_K$ the remaining graph is not a star. Let's prove this:

We color the vertices in black and white, so no two neighbouring vertices have the same color. Assuming that $A_K$'s neighbours are black, if the graph is not connected, we can just choose all the white vertices, followed by all the black vertices, making sure the adjacent white and black pair is made up of vertices from different components. If the graph is connected (but not a star), we again choose all the white vertices followed by the black ones and we'll always find a pair of vertices of different colors that don't share an edge.

Knowing this, we can just build the solution incrementally. At each step we maintain a set of all the available vertices, and try to append them to the solution in increasing order. We can check if the remaining graph is not a star by maintaining a multiset of degrees - the largest degree should be less than the number of remaining vertices minus $1$.

A careful implementation is needed to avoid $O(N^2)$ complexity.

Official implementation

Solution

If $N \leq 2*K$, there is a simple $O(N^2 * \text{hashset})$ solution. Consider the slopes of all lines passing through two points. For each slope, we have several pairs of points (edges in a future graph) which belong to the same line of that slope. Then, the number of connected components in the graph is the answer for this slope.

Otherwise, if $N \geq 2*K$, consider the multiset of slopes of all lines passing through two points out of the first $2*K$ points. The best slope appears at least $K$ times in this multiset. Since we have $K*(2*K-1)$ slopes in total, we have only at most $2*K-1$ candidate slopes. We can check each of these explicitly to get an $O(N*K * \text{hashset})$ solution.

Official implementation

Solution

Suppose we wish to simulate the process. Let's maintain a set of segments of free hooks between every two neighboring occupied hooks. For a segment $s$ of $k(s)$ consecutive free hooks, consider the value of $d(s) = (k(s) + 1) / 2$ (integer division) which is the distance from a center hook of this segment to the closest occupied hook. A new person chooses a random center hook inside some segment with the largest $d(s)$. Note that if $k(s)$ is even, then there are two center hooks for segment $s$.

This simulation will be correct until every free hook has a neighboring occupied hook. After that, every person just chooses a random remaining hook. From now on we'll disregard this final phase of the process, but it's fairly easy to account for.

Time for an important observation. Suppose person $i$ is choosing a segment randomly from the set $s_1, s_2, ..., s_{m_i}$, where $m_i > 1$. Then, independent of person $i$'s choice, person $i+1$ will have to choose one of the remaining segments in this set, that is, they will have $m_i - 1$ options. The same applies to person $i+2$ if $m_i > 2$, and so on.

Note that segments of even and odd length in the same set have different probabilities to be chosen, though. Segments of even length have two center hooks, so they are more probable to be chosen.

Let $f(n_{even}, n_{odd}, t)$ be the probability that if there are $n_{even}$ segments of even length and $n_{odd}$ segments of odd length in some set, then a center hook of an odd-length segment will be chosen on step $t$ of removing elements from this set. The values of $f$ can be easily calculated with dynamic programming.

Using the values of $f$, now we can find the probabilities of different hooks chosen on different steps of our non-deterministic process. The solution goes as follows.

Every time, we find the set of segments $s$ with the largest $d(s)$. Then, if this set contains $m_i$ segments, we can calculate the required probabilities for the next $m_i$ steps.

But here comes trouble. Segments of even length have two center hooks, and we don't know which one is occupied, so we can't deterministically move on with the simulation!

Here comes the final twist. In case of even-length segments, simply pretend that the leftmost center hook is always chosen. In fact, this might not be true. But if the rightmost center hook was chosen, the situation would be symmetric with regard to the center of the segment. So once we have found the probabilities for all the remaining steps for hooks inside this segment, make these probabilities symmetric!

For example, suppose we had a segment consisting of hooks 1 through 6, and after step $i$ we pretend to have taken hook 3. As we continue, we find the probabilities $a_{j,1}, ..., a_{j,6}$ for all $j > i$. Then, we replace $a_{j,1}$ and $a_{j,6}$ with $(a_{j,1} + a_{j,6}) / 2$, and do the same with $a_{j,2}$ and $a_{j,5}$, and with $a_{j,3}$ and $a_{j,4}$.

Overall, the solution works in $O(n^3)$ due to the number of states in $f$, but it's very fast in practice. Solutions with better asymptotics are possible, but not required.