Codeforces Global Round 25 Editorial
Разница между en10 и en11, 0 символ(ов) изменены
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:↵

![ ](https://cdn.discordapp.com/attachments/1197769839956197497/1226184088050864238/problemb.png?ex=6623d7eb&is=661162eb&hm=b1029e196afc732015a64ca871e70ca70a8e5ef2683bf523ee11fe9d28c10ebe&)↵
</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.net/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>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en17 Английский Kuroni 2024-04-09 04:37:29 12
en16 Английский Kuroni 2024-04-06 22:39:23 4 Tiny change: 'sion:255371841]\n</spoil' -> 'sion:255374619]\n</spoil'
en15 Английский Kuroni 2024-04-06 22:17:39 62
en14 Английский Kuroni 2024-04-06 22:00:44 436
en13 Английский Kuroni 2024-04-06 21:32:07 12
en12 Английский Kuroni 2024-04-06 21:25:50 14 Tiny change: 've: [user:tourist,2024-04-0' -> 've: [user:ecnerwala,2024-04-0'
en11 Английский MofK 2024-04-06 21:19:36 0 (published)
en10 Английский Kuroni 2024-04-06 21:18:41 192 Tiny change: 'he problems, click [' -> 'he problem statements, click ['
en9 Английский Kuroni 2024-04-06 20:15:39 1785
en8 Английский MofK 2024-04-06 19:51:40 1433
en7 Английский MofK 2024-04-06 19:00:06 56
en6 Английский MofK 2024-04-06 18:57:58 1063
en5 Английский MofK 2024-04-06 18:55:06 12
en4 Английский MofK 2024-04-06 18:51:01 121
en3 Английский MofK 2024-04-06 17:59:12 1126
en2 Английский MofK 2024-04-06 17:18:21 522
en1 Английский MofK 2024-04-06 17:04:51 1433 Initial revision (saved to drafts)