Hi, we hope you enjoyed our problems! For the playlist of songs used in the problem statements, click this link.
1951A - Dual Trigger
Author: MofK
Prepared by Kuroni
First solve: xiachong at 00:01
1951B - Battle Cows
Author: MofK
Prepared by Kuroni
First solve: pavement at 00:05
Hint 1What is the condition for your cow to win her first match?
Hint 2If your cow is not already winning her first match, there are at most two candidate positions you can swap her to.
Comments from the authorsThis 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:
1951C - Ticket Hoarding
Author: MofK
Prepared by Kuroni
First solve: arvindf232 at 00:11
Hint 1If there is no additional cost (i.e. buying a ticket at day $$$i$$$ costs only $$$a_i$$$), what is the optimal buying strategy?
Hint 2If there \textit{is} additional cost but $$$a_i = 1$$$ for all $$$i$$$, what is the optimal buying strategy?
Hint 3The 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?
1951D - Buying Jewels
Author: MofK
Prepared by MofK
First solve: conqueror_of_tourist at 00:14
HintPerhaps the easiest way of dealing with this problem is writing down small cases and see what happens.
Comments from the authorsThis 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.
1951E - No Palindromes
Author: MofK
Prepared by MofK
First solve: DottedCalculator at 00:16
HintLet $$$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?
Comments from the authorsIt 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.
1951F - Inversion Composition
Author: Kuroni
Prepared by Kuroni
First solve: CeItic at 00:42
Hint 1Let'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$$$?
Hint 2They 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.
1951G - Clacking Balls
Author: MofK
Prepared by Kuroni
First solve: Little09_love_YCY at 00:19
Hint 1We should represent a state as the sequence of distances between each pair of consecutive balls.
1951H - Thanos Snap
Author: Kuroni
Prepared by Kuroni
First solve: tourist at 01:34
Hint 1Let's binary search the answer. Every element is now either $$$0$$$ or $$$1$$$, and Alice tries to get $$$1$$$.
Hint 2Let's directly construct the strategy for Alice. It can be viewed as a perfect binary game tree.
Hint 3Construct the strategy greedily bottom-up.
1951I - Growing Trees
Author: Kuroni
Prepared by Kuroni
First solve: rainboy at 02:27
Hint 2It is possible to check if $$$x$$$ satisfies with $$$m$$$ flow runs, each flow graph having $$$O(n + m)$$$ nodes and edges.
Hint 4We can greedily select to increase $$$x_i$$$ with the least increment cost that still satisfies. Quickly simulate this via a binary search.