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.

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}$$$. 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 set of deleted elements is $$$[1, 2t]$$$ in both cases. Therefore the 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 $$$C$$$ or $$$E$$$, I would be happy to add it to the blog.