A. Monsters (easy version)

Notice that this is equivalent to maximizing the damage done by the operation of type $$$2$$$. Let us consider the case when there are 2 monsters with health $$$h$$$, and $$$h+k$$$, and no monsters with health in $$$(h, h+k)$$$. Then reducing the monster with health $$$h + k$$$ to $$$h + 1$$$ cannot make the final outcome worse. You can prove it by noticing that the operation of type $$$2$$$ can only happen $$$h$$$ times if the health of the monster is above $$$h + 1$$$. Now we get monsters with health in such a way, that there exists $$$H$$$, where there is monster with health from $$$1$$$ to $$$H$$$. Then one move of operation $$$2$$$ can kill the remaining monsters. So you only need to simulate the above process, and find out how many moves of type $$$1$$$ were required to do it.

B. Letter Exchange

Let us consider a graph with $$$3$$$ nodes $$$w, i, n$$$. For a word of type $$$wii$$$ add an edge from $$$i$$$ to $$$n$$$. For a word of type of $$$www$$$ and an edge from $$$w$$$ to $$$i$$$ and $$$w$$$ to $$$n$$$. This represents the swaps it needs to be sorted. Now instead of swapping letters between words, we swap letters between edges. Edges $$$a \to b$$$ and $$$b \to a$$$ can be swapped to make $$$a \to a$$$ and $$$b \to b$$$. Notice self edges are redundant, so we can drop them. For edges $$$a \to b$$$ and $$$b \to c$$$, we get $$$a \to c$$$ and $$$b \to b$$$. The rest of the possibilities are symmetric versions of these. Therefore to swap these in the minimum number of moves, we should maximize the number of times we use the first operation, that removed 2 edges at once, or minimize the number of times we do the operation of type 2.

We claim that the minimum number of times we need to use the operation of type 2 is the absolute value of the cyclic flow in the graph. The cyclic flow is defined as following. Let the flow from $$$a \to b$$$ be the difference of edges from $$$a \to b$$$ and $$$b \to a$$$. Then the absolute value of this equal for all $$$a, b$$$. Notice this by the fact that the indegree and outdegree of each node must be equal. Call this value the cyclic flow.

The operation of type $$$1$$$ doesn't change the cyclic flow, and operation of type 2 changes cyclic flow by 1 in any direction (Notice the signed cyclic flow is additive). Therefore we must use the operation of type $$$2$$$ at least that many times. This is also constructible, since just doing operations of type 1 until its possible, then using operations of type 2 to get rid of the cycles is valid strategy.

Therefore you just need to simulate doing it.

C. Monsters (hard version)

Consider doing the process in reverse. From the easy version, we deduce that there exists $$$H > 0$$$ s.t. there is some monster with health $$$h$$$ for all $$$1 \le h \le H$$$. This effectively forms a matching between $$$[1, H]$$$ and some subset of monsters, such that the health of the monster is larger, and the sum of differences is minimised. Additionally, the health of all monsters is less than $$$H$$$. We only need to keep track of the monster mapped to health $$$h$$$ at each point of time.

Let us prove the assignment with larger $$$H$$$ is strictly optimal. Let us consider two solutions, one with $$$H = x$$$, and one with $$$H = x + 1$$$. If it is possible to not use the largest element for $$$H$$$, we will not use it. We can show this by direct exchange argument, by replacing the matching. If there exists solution with $$$H = x + 1$$$, it is possible to remove any element greater than $$$x$$$ and still have matching. Then we could simply have maximum be at $$$x + 1$$$, and produce strictly better solution. Therefore $$$H$$$ is always maximum possible. It is also then obvious, that if there exists monster with $$$h > H$$$, the current solution is not optimal.

Consider doing the solution for the entire array and removing one by one. Then if the removed monster wasn't already matched the solution is still optimal. Let us consider removing the monster was matched with $$$h$$$. Then we can retain the value of $$$H$$$ if there exists replacement for it. This is true because there are $$$H - h$$$ monsters with more health than $$$h$$$, since all are in matching if there is no replacement, but we need $$$H - h + 1$$$. So checking if the value of $$$H$$$ is still same is checking if there exists replacement.

Then we claim, that picking the smallest replacement, and not changing the rest of the matching produces an optimal solution.

Lemma : If there exists a solution, there exists a sorted solution with respect to $$$[1, H]$$$. We can prove this by exchange argument on every inversion. Therefore the following solution is optimal, when considering the set of sorted matchings. Go from $$$[1, H]$$$. Pick the smallest available element at each step.

We will now find that with the above two algorithms, the set of chosen elements in both the matchings will be equal, and therefore will have equal cost.

Let us consider the case where $$$x$$$ is matched to a lower cost than the sorted solution. Then any replacement for this will work for optimal too, and since smaller replacement means better than optimal, it will do as good as optimal.

If it is matched to higher cost than optimal, Let us consider $$$k_1$$$ and $$$k_2$$$, there must be no excess elements between $$$k_1$$$ and $$$k_2$$$, otherwise you could replace $$$x$$$ by it, and the solution is not optimal.

If there is no replacement, then we can simply replace the monster matched to $$$h$$$ with the monster matched to $$$H$$$, and decrement $$$H$$$.

Therefore we can deduce that the set of matched elements is equal, and therefore the solutions are equivalent, which solves the problem.

Solution — Courtesy of jeroenodb

D. Wooden Spoon

We can find the Wooden spoon uniquely by this process. Create a binary tree, where the leaves are the players. We consider the maximum wins instead of the minimum for algebraic convenience. The winner of node is the maximum of its children. Start at the root, and go to the loser of the game. Do this until you reach a leaf node. Now we need some way to find the probability of each person being the final leaf of this process. Let us consider the dynamic programming relation $$$dp[d][s]$$$, as the probability of the person with skill $$$s$$$ being the node we reach after $$$d$$$ iterations of the above process.

We also claim the following invariant $$$:$$$ The probability of any person $$$x < s$$$ being in the subtree of $$$s$$$ is equiprobable.

Let us now consider finding the probability of transition from $$$dp[d+1][x]$$$ from $$$dp[d][s]$$$. Let $$$sz(d)$$$ be the size of the subtree after doing $$$d$$$ steps of the process, or equivalently $$$2^{n - d}$$$. Then the number of way to split the subtree of $$$s$$$ into two sets is $$$\binom{s - 1}{sz(d+1)}\binom{s - 1}{sz(d+1) - 1}$$$. The number of ways to split so that the loser of one subtree is $$$x$$$ is $$$\binom{x - 1}{sz(d+1) - 1}\binom{s - sz(d+1) - 1}{sz(d+1) - 1}$$$. This transition also satisfies our previous invariant, therefore its a valid dynamic programming solution. Notice that each factor in the probability transition depends only on $$$x$$$ or only on $$$s$$$. So we can use prefix sums with some multiplication to calculate it efficiently.

F. Minimums or Medians

We basically need to find the set of constructible strings. For this we should first analyze how the median and minimum operations interplay. Let us imagine 2 pointers at the 2 medians of the array at all times. If we do a minimum operation, both these pointers move forward to the next element. If we do a median operation, they delete the current element, and move outwards. This also implies the larger element deleted by any median operation is monotonically increasing.

With this analysis we can make our first claim. For any constructible string, the smallest remaining number, if it exists will always be odd. This is trivial to see by invariant. At each point the array will satisfy $$$a[i] \equiv i \mod 2$$$.

Now let's go for a harder claim. For any constructible string with smallest remaining number being $$$2t + 1$$$, it is possible to construct it with exactly $$$t$$$ minimum operations.

If the median acts on some pair $$$(x, y)$$$, then there must be no elements currently between $$$x$$$ and $$$y$$$. Therefore we notice that either $$$max(x, y) < 2t + 1$$$, or $$$min(x, y) > 2t + 1$$$. Since the larger element is monotonically increasing, we also know that only some prefix of median operations satisfy $$$max(x, y) < 2t + 1$$$. We replace all median operations with $$$max(x, y) < 2t + 1$$$ with minimum operations. Notice that on the first median operation, the number of deleted elements to the left of $$$2t + 1$$$ is equal. Therefore this claim is true.

Now its quite natural to fix $$$t$$$, the number of minimum operations we did. Then all median operations act on numbers larger than $$$2t + 1$$$. Let us now look what the possible median operation actions look like. Notice that the right midpoint doesn't just increase every move, it increases by exactly one. Therefore we can claim the largest deletable element is $$$n + k$$$.

Let's go for the next claim. Let $$$b$$$ be the number of elements in $$$[1, n]$$$ deleted with median operations. The set of deleted elements is $$$[n-b+1, n]$$$, and additionally, $$$[n+1, n+b]$$$ must also be deleted. This requires the same observation of medians not "skipping" numbers, except now we look at the gap between $$$n$$$ and $$$n+1$$$. The right endpoint is always larger than $$$n+1$$$, and the left endpoint here is less than $$$n$$$. Therefore at each point we can only delete the largest element less than $$$n$$$ and the smallest element larger than $$$n+1$$$.

Now let's additionally fix the balance $$$b$$$. Now consider the numbers $$$[n+b+1, n+k]$$$.

We claim, you can delete any subset of these numbers, as long as the length of every deleted segment is even. We first delete the $$$[n-b+1, n+b]$$$ trivially. Then we do a minimum operation and have the end points of $$$(n+b+1, n+b+2)$$$. From here we do the simple algorithm, of go to the midpoint of the next even length deleted segment, and do operations until that segment is deleted. It is quite easy to see that this will delete the necessary segments, and is possible since the higher end of the median can reach $$$n + k$$$.

The next step only involve equation bashing, but the high level idea is as follows. If you have $$$x$$$ elements and you want $$$2s$$$ elements deleted, then the number of ways to do it is $$$\binom{x - s}{s}$$$. When you add the combinatorial terms over all pairs $$$t, b$$$ such that answer is $$$\binom{x}{y}$$$ you might notice the possible $$$y$$$ for each $$$x$$$ forms contigous range. Also as you increase $$$x$$$, this ranges changes by at most 1 in either direction. Since $$$\sum \binom{x + i}{y}$$$ is easier to compute than $$$\sum \binom{x}{i}$$$, we can kindof transpose the sum.

I think there is easier interpretation of this if you loop $$$b$$$ before $$$t$$$. If anyone has such interpretation feel free to share it in comments.

If anyone wants to write down their solutions to $$$E$$$, I would be happy to add it to the blog.