Hi, we hope you enjoyed our problems! For the playlist of songs used in the problem statements, click [this link](https://www.youtube.com/playlist?list=PLTVdHvnX6LZhAJre49E7M7tpGA30WlBM3).↵
↵
[problem:1951A]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:xiachong,2024-04-06] at 00:01↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951A]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:1,yay]↵
Meh [likes:1,meh]↵
Nay [likes:1,nay]↵
Banger song [likes:2]↵
</spoiler>↵
↵
[problem:1951B]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:pavement,2024-04-06] at 00:05↵
↵
<spoiler summary="Hint 1">↵
What is the condition for your cow to win her first match?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If your cow is not already winning her first match, there are at most two candidate positions you can swap her to.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951B]↵
</spoiler>↵
↵
<spoiler summary = "Comments from the authors">↵
This problem was added after [problem:1951D] 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:↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:3,yay]↵
Meh [likes:3,meh]↵
Nay [likes:3,nay]↵
Banger song [likes:4]↵
</spoiler>↵
↵
[problem:1951C]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:arvindf232,2024-04-06] at 00:11↵
↵
<spoiler summary="Hint 1">↵
If there is no additional cost (i.e. buying a ticket at day $i$ costs only $a_i$), what is the optimal buying strategy?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If there \textit{is} additional cost but $a_i = 1$ for all $i$, what is the optimal buying strategy?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951C]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:5,yay]↵
Meh [likes:5,meh]↵
Nay [likes:5,nay]↵
Banger song [likes:6]↵
</spoiler>↵
↵
[problem:1951D]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:MofK,2024-04-06]↵
<br>↵
First solve: [user:conqueror_of_tourist,2024-04-06] at 00:14↵
↵
<spoiler summary="Hint">↵
Perhaps the easiest way of dealing with this problem is writing down small cases and see what happens.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951D]↵
</spoiler>↵
↵
<spoiler summary = "Comments from the authors">↵
This problem was originally problem B. It turned out to be too hard and was switched to C, with [problem:1951B] inserted, before being further switched to D as it was still too hard.↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:7,yay]↵
Meh [likes:7,meh]↵
Nay [likes:7,nay]↵
Banger song [likes:8]↵
</spoiler>↵
↵
[problem:1951E]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:MofK,2024-04-06]↵
<br>↵
First solve: [user:DottedCalculator,2024-04-06] at 00:16↵
↵
<spoiler summary="Hint">↵
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?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951E]↵
</spoiler>↵
↵
<spoiler summary = "Comments from the authors">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:9,yay]↵
Meh [likes:9,meh]↵
Nay [likes:9,nay]↵
Banger song [likes:10]↵
</spoiler>↵
↵
[problem:1951F]↵
↵
Author: [user:Kuroni,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:CeItic,2024-04-06] at 00:42↵
↵
<spoiler summary="Hint 1">↵
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$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951F]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:11,yay]↵
Meh [likes:11,meh]↵
Nay [likes:11,nay]↵
Banger song [likes:12]↵
</spoiler>↵
↵
[problem:1951G]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:Little09_love_YCY,2024-04-06] at 00:19↵
↵
<spoiler summary="Hint 1">↵
We should represent a state as the sequence of distances between each pair of consecutive balls.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
[This should probably help.](https://codeforces.me/blog/entry/77284#comment-620956)↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951G]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:13,yay]↵
Meh [likes:13,meh]↵
Nay [likes:13,nay]↵
Banger song [likes:14]↵
</spoiler>↵
↵
[problem:1951H]↵
↵
Author: [user:Kuroni,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:tourist,2024-04-06] at 01:34↵
↵
<spoiler summary="Hint 1">↵
Let's binary search the answer. Every element is now either $0$ or $1$, and Alice tries to get $1$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Let's directly construct the strategy for Alice. It can be viewed as a perfect binary game tree.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Construct the strategy greedily bottom-up.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951H]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:15,yay]↵
Meh [likes:15,meh]↵
Nay [likes:15,nay]↵
Banger song [likes:16]↵
</spoiler>↵
↵
[problem:1951I]↵
↵
Author: [user:Kuroni,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:rainboy,2024-04-06] at 02:27↵
↵
<spoiler summary="Hint 1">↵
[This helps to check if $x$ satisfies](https://en.wikipedia.org/wiki/Nash-Williams_theorem). Pattern match it to [Hall's marriage theorem](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem).↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
It is possible to check if $x$ satisfies with $m$ flow runs, each flow graph having $O(n + m)$ nodes and edges.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Spanning trees are independent set of the graphic matroid. [Direct sums of $k$ such matroids is also a matroid](https://en.wikipedia.org/wiki/Matroid#:~:text=.%5B20%5D-,Sums%20and%20unions,-%5Bedit%5D).↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
We can greedily select to increase $x_i$ with the least increment cost that still satisfies. Quickly simulate this via a binary search.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951I]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:17,yay]↵
Meh [likes:17,meh]↵
Nay [likes:17,nay]↵
Banger song [likes:18]↵
</spoiler>↵
↵
↵
[problem:1951A]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:xiachong,2024-04-06] at 00:01↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951A]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:1,yay]↵
Meh [likes:1,meh]↵
Nay [likes:1,nay]↵
Banger song [likes:2]↵
</spoiler>↵
↵
[problem:1951B]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:pavement,2024-04-06] at 00:05↵
↵
<spoiler summary="Hint 1">↵
What is the condition for your cow to win her first match?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If your cow is not already winning her first match, there are at most two candidate positions you can swap her to.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951B]↵
</spoiler>↵
↵
<spoiler summary = "Comments from the authors">↵
This problem was added after [problem:1951D] 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:↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:3,yay]↵
Meh [likes:3,meh]↵
Nay [likes:3,nay]↵
Banger song [likes:4]↵
</spoiler>↵
↵
[problem:1951C]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:arvindf232,2024-04-06] at 00:11↵
↵
<spoiler summary="Hint 1">↵
If there is no additional cost (i.e. buying a ticket at day $i$ costs only $a_i$), what is the optimal buying strategy?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If there \textit{is} additional cost but $a_i = 1$ for all $i$, what is the optimal buying strategy?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951C]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:5,yay]↵
Meh [likes:5,meh]↵
Nay [likes:5,nay]↵
Banger song [likes:6]↵
</spoiler>↵
↵
[problem:1951D]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:MofK,2024-04-06]↵
<br>↵
First solve: [user:conqueror_of_tourist,2024-04-06] at 00:14↵
↵
<spoiler summary="Hint">↵
Perhaps the easiest way of dealing with this problem is writing down small cases and see what happens.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951D]↵
</spoiler>↵
↵
<spoiler summary = "Comments from the authors">↵
This problem was originally problem B. It turned out to be too hard and was switched to C, with [problem:1951B] inserted, before being further switched to D as it was still too hard.↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:7,yay]↵
Meh [likes:7,meh]↵
Nay [likes:7,nay]↵
Banger song [likes:8]↵
</spoiler>↵
↵
[problem:1951E]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:MofK,2024-04-06]↵
<br>↵
First solve: [user:DottedCalculator,2024-04-06] at 00:16↵
↵
<spoiler summary="Hint">↵
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?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951E]↵
</spoiler>↵
↵
<spoiler summary = "Comments from the authors">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:9,yay]↵
Meh [likes:9,meh]↵
Nay [likes:9,nay]↵
Banger song [likes:10]↵
</spoiler>↵
↵
[problem:1951F]↵
↵
Author: [user:Kuroni,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:CeItic,2024-04-06] at 00:42↵
↵
<spoiler summary="Hint 1">↵
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$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951F]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:11,yay]↵
Meh [likes:11,meh]↵
Nay [likes:11,nay]↵
Banger song [likes:12]↵
</spoiler>↵
↵
[problem:1951G]↵
↵
Author: [user:MofK,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:Little09_love_YCY,2024-04-06] at 00:19↵
↵
<spoiler summary="Hint 1">↵
We should represent a state as the sequence of distances between each pair of consecutive balls.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
[This should probably help.](https://codeforces.me/blog/entry/77284#comment-620956)↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951G]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:13,yay]↵
Meh [likes:13,meh]↵
Nay [likes:13,nay]↵
Banger song [likes:14]↵
</spoiler>↵
↵
[problem:1951H]↵
↵
Author: [user:Kuroni,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:tourist,2024-04-06] at 01:34↵
↵
<spoiler summary="Hint 1">↵
Let's binary search the answer. Every element is now either $0$ or $1$, and Alice tries to get $1$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Let's directly construct the strategy for Alice. It can be viewed as a perfect binary game tree.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Construct the strategy greedily bottom-up.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951H]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:15,yay]↵
Meh [likes:15,meh]↵
Nay [likes:15,nay]↵
Banger song [likes:16]↵
</spoiler>↵
↵
[problem:1951I]↵
↵
Author: [user:Kuroni,2024-04-06]↵
<br>↵
Prepared by [user:Kuroni,2024-04-06]↵
<br>↵
First solve: [user:rainboy,2024-04-06] at 02:27↵
↵
<spoiler summary="Hint 1">↵
[This helps to check if $x$ satisfies](https://en.wikipedia.org/wiki/Nash-Williams_theorem). Pattern match it to [Hall's marriage theorem](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem).↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
It is possible to check if $x$ satisfies with $m$ flow runs, each flow graph having $O(n + m)$ nodes and edges.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Spanning trees are independent set of the graphic matroid. [Direct sums of $k$ such matroids is also a matroid](https://en.wikipedia.org/wiki/Matroid#:~:text=.%5B20%5D-,Sums%20and%20unions,-%5Bedit%5D).↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
We can greedily select to increase $x_i$ with the least increment cost that still satisfies. Quickly simulate this via a binary search.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1951I]↵
</spoiler>↵
↵
<spoiler summary="Rate this problem">↵
Yay [likes:17,yay]↵
Meh [likes:17,meh]↵
Nay [likes:17,nay]↵
Banger song [likes:18]↵
</spoiler>↵
↵
