Yay Meh Nay Banger song

What is the condition for your cow to win her first match?

If your cow is not already winning her first match, there are at most two candidate positions you can swap her to.

This problem was added after 1951D - Buying Jewels was deemed too hard to be problem B. At first, we decided to hide the case of swapping with the first stronger cow from the sample test. The testers weren't too impressed:

Yay Meh Nay Banger song

If there is no additional cost (i.e. buying a ticket at day $$$i$$$ costs only $$$a_i$$$), what is the optimal buying strategy?

If there \textit{is} additional cost but $$$a_i = 1$$$ for all $$$i$$$, what is the optimal buying strategy?

The above two strategies are the same, and the primary and secondary costs are independent of each other. \textit{Surely} the solution is not just choosing $$$k$$$ cheapest tickets right?

Yay Meh Nay Banger song

Perhaps the easiest way of dealing with this problem is writing down small cases and see what happens.

This problem was originally problem B. It turned out to be too hard and was switched to C, with 1951B - Battle Cows inserted, before being further switched to D as it was still too hard.

Yay Meh Nay Banger song

Let $$$i$$$ be the first character that is different from $$$s_1$$$. Then $$$s_{1..i}$$$ is not a palindrome. If $$$s_{i+1..n}$$$ is also not a palindrome then we are done, but what can we do if it is?

It is rather unfortunate that the solution only uses partitions of at most size $$$2$$$, therefore one can "solve" the problem by brute forcing every possible partition and check validity using any string matching algorithm. Nevertheless, we tried our hardest to make sure dumber "solutions" won't pass.

Yay Meh Nay Banger song

Let's look at the ``inverseness'' of $$$(p_i, p_j)$$$ on $$$q$$$ and $$$(i, j)$$$ on $$$q \cdot p$$$. What is their relation to the inverseness of $$$(i, j)$$$ on $$$p$$$?

They either contribute $$$0$$$ or $$$1$$$ if $$$(i, j)$$$ is not an inverse on $$$p$$$, or $$$1$$$ if $$$(i, j)$$$ is an inverse on $$$p$$$. We now know the necessary condition for $$$k$$$ if there is an answer. This is also sufficient.

Yay Meh Nay Banger song

We should represent a state as the sequence of distances between each pair of consecutive balls.

This should probably help.

Yay Meh Nay Banger song

Let's binary search the answer. Every element is now either $$$0$$$ or $$$1$$$, and Alice tries to get $$$1$$$.

Let's directly construct the strategy for Alice. It can be viewed as a perfect binary game tree.

Construct the strategy greedily bottom-up.

Yay Meh Nay Banger song

This helps to check if $$$x$$$ satisfies. Pattern match it to Hall's marriage theorem.

It is possible to check if $$$x$$$ satisfies with $$$m$$$ flow runs, each flow graph having $$$O(n + m)$$$ nodes and edges.

Spanning trees are independent set of the graphic matroid. Direct sums of $$$k$$$ such matroids is also a matroid.

We can greedily select to increase $$$x_i$$$ with the least increment cost that still satisfies. Quickly simulate this via a binary search.

Yay Meh Nay Banger song