codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1951.md (8181B)


      1 Source: https://codeforces.com/blog/entry/128116
      2 
      3 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).
      4 
      5 [1951A - Dual Trigger](/contest/1951/problem/A "Codeforces Global Round 25")
      6 
      7 Author: [MofK](/profile/MofK "Grandmaster MofK")   
      8  Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
      9  First solve: [xiachong](/profile/xiachong "Grandmaster xiachong") at 00:01
     10 
     11 **Tutorial and Implementation**
     12 
     13 Tutorial is loading...
     14 
     15 [255371605](/contest/1951/submission/255371605 "Submission 255371605 by Kuroni")
     16 
     17 **Rate this problem**
     18 
     19 Yay
     20 
     21 Meh
     22 
     23 Nay
     24 
     25 Banger song
     26 
     27 [1951B - Battle Cows](/contest/1951/problem/B "Codeforces Global Round 25")
     28 
     29 Author: [MofK](/profile/MofK "Grandmaster MofK")   
     30  Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
     31  First solve: [pavement](/profile/pavement "Master pavement") at 00:05
     32 
     33 **Hint 1**
     34 
     35 What is the condition for your cow to win her first match?
     36 
     37 **Hint 2**
     38 
     39 If your cow is not already winning her first match, there are at most two candidate positions you can swap her to.
     40 
     41 **Tutorial and Implementation**
     42 
     43 Tutorial is loading...
     44 
     45 [255371643](/contest/1951/submission/255371643 "Submission 255371643 by Kuroni")
     46 
     47 **Comments from the authors**
     48 
     49 This problem was added after [1951D - Buying Jewels](/contest/1951/problem/D "Codeforces Global Round 25") 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:
     50 
     51 ![ ](/predownloaded/d9/15/d915ad709a1e6b7ad88880dab0b1966eb0bcbfa1.png)
     52 
     53 **Rate this problem**
     54 
     55 Yay
     56 
     57 Meh
     58 
     59 Nay
     60 
     61 Banger song
     62 
     63 [1951C - Ticket Hoarding](/contest/1951/problem/C "Codeforces Global Round 25")
     64 
     65 Author: [MofK](/profile/MofK "Grandmaster MofK")   
     66  Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
     67  First solve: [arvindf232](/profile/arvindf232 "Legendary Grandmaster arvindf232") at 00:11
     68 
     69 **Hint 1**
     70 
     71 If there is no additional cost (i.e. buying a ticket at day $i$ costs only $a_i$), what is the optimal buying strategy?
     72 
     73 **Hint 2**
     74 
     75 If there \textit{is} additional cost but $a_i = 1$ for all $i$, what is the optimal buying strategy?
     76 
     77 **Hint 3**
     78 
     79 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?
     80 
     81 **Tutorial and Implementation**
     82 
     83 Tutorial is loading...
     84 
     85 [255371666](/contest/1951/submission/255371666 "Submission 255371666 by Kuroni")
     86 
     87 **Rate this problem**
     88 
     89 Yay
     90 
     91 Meh
     92 
     93 Nay
     94 
     95 Banger song
     96 
     97 [1951D - Buying Jewels](/contest/1951/problem/D "Codeforces Global Round 25")
     98 
     99 Author: [MofK](/profile/MofK "Grandmaster MofK")   
    100  Prepared by [MofK](/profile/MofK "Grandmaster MofK")   
    101  First solve: [conqueror_of_tourist](/profile/conqueror_of_tourist "Legendary Grandmaster conqueror_of_tourist") at 00:14
    102 
    103 **Hint**
    104 
    105 Perhaps the easiest way of dealing with this problem is writing down small cases and see what happens.
    106 
    107 **Tutorial and Implementation**
    108 
    109 Tutorial is loading...
    110 
    111 [255371688](/contest/1951/submission/255371688 "Submission 255371688 by Kuroni")
    112 
    113 **Comments from the authors**
    114 
    115 This problem was originally problem B. It turned out to be too hard and was switched to C, with [1951B - Battle Cows](/contest/1951/problem/B "Codeforces Global Round 25") inserted, before being further switched to D as it was still too hard.
    116 
    117 **Rate this problem**
    118 
    119 Yay
    120 
    121 Meh
    122 
    123 Nay
    124 
    125 Banger song
    126 
    127 [1951E - No Palindromes](/contest/1951/problem/E "Codeforces Global Round 25")
    128 
    129 Author: [MofK](/profile/MofK "Grandmaster MofK")   
    130  Prepared by [MofK](/profile/MofK "Grandmaster MofK")   
    131  First solve: [DottedCalculator](/profile/DottedCalculator "Specialist DottedCalculator") at 00:16
    132 
    133 **Hint**
    134 
    135 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?
    136 
    137 **Tutorial and Implementation**
    138 
    139 Tutorial is loading...
    140 
    141 [255371747](/contest/1951/submission/255371747 "Submission 255371747 by Kuroni")
    142 
    143 **Comments from the authors**
    144 
    145 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.
    146 
    147 **Rate this problem**
    148 
    149 Yay
    150 
    151 Meh
    152 
    153 Nay
    154 
    155 Banger song
    156 
    157 [1951F - Inversion Composition](/contest/1951/problem/F "Codeforces Global Round 25")
    158 
    159 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
    160  Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
    161  First solve: [CeItic](/profile/CeItic "Pupil CeItic") at 00:42
    162 
    163 **Hint 1**
    164 
    165 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$?
    166 
    167 **Hint 2**
    168 
    169 They either contribute $0$ or $2$ 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.
    170 
    171 **Tutorial and Implementation**
    172 
    173 Tutorial is loading...
    174 
    175 [255371767](/contest/1951/submission/255371767 "Submission 255371767 by Kuroni")
    176 
    177 **Rate this problem**
    178 
    179 Yay
    180 
    181 Meh
    182 
    183 Nay
    184 
    185 Banger song
    186 
    187 [1951G - Clacking Balls](/contest/1951/problem/G "Codeforces Global Round 25")
    188 
    189 Author: [MofK](/profile/MofK "Grandmaster MofK")   
    190  Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
    191  First solve: [Little09_love_YCY](/profile/Little09_love_YCY "Master Little09_love_YCY") at 00:19
    192 
    193 **Hint 1**
    194 
    195 We should represent a state as the sequence of distances between each pair of consecutive balls.
    196 
    197 **Hint 2**
    198 
    199 [This should probably help.](https://codeforces.com/blog/entry/77284#comment-620956)
    200 
    201 **Tutorial and Implementation**
    202 
    203 Tutorial is loading...
    204 
    205 [255371802](/contest/1951/submission/255371802 "Submission 255371802 by Kuroni")
    206 
    207 **Rate this problem**
    208 
    209 Yay
    210 
    211 Meh
    212 
    213 Nay
    214 
    215 Banger song
    216 
    217 [1951H - Thanos Snap](/contest/1951/problem/H "Codeforces Global Round 25")
    218 
    219 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
    220  Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
    221  First solve: [ecnerwala](/profile/ecnerwala "Legendary Grandmaster ecnerwala") at 01:34
    222 
    223 **Hint 1**
    224 
    225 Let's binary search the answer. Every element is now either $0$ or $1$, and Alice tries to get $1$.
    226 
    227 **Hint 2**
    228 
    229 Let's directly construct the strategy for Alice. It can be viewed as a perfect binary game tree.
    230 
    231 **Hint 3**
    232 
    233 Construct the strategy greedily bottom-up.
    234 
    235 **Tutorial and Implementation**
    236 
    237 Tutorial is loading...
    238 
    239 [255374619](/contest/1951/submission/255374619 "Submission 255374619 by Kuroni")
    240 
    241 **Rate this problem**
    242 
    243 Yay
    244 
    245 Meh
    246 
    247 Nay
    248 
    249 Banger song
    250 
    251 [1951I - Growing Trees](/contest/1951/problem/I "Codeforces Global Round 25")
    252 
    253 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
    254  Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
    255  First solve: [rainboy](/profile/rainboy "Master rainboy") at 02:27
    256 
    257 **Hint 1**
    258 
    259 [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).
    260 
    261 **Hint 2**
    262 
    263 It is possible to check if $x$ satisfies with $n$ flow runs, each flow graph having $O(n + m)$ nodes and edges.
    264 
    265 **Hint 3**
    266 
    267 Spanning trees are independent sets 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).
    268 
    269 **Hint 4**
    270 
    271 We can greedily select to increase $x_i$ with the least increment cost that still satisfies. Quickly simulate this via a binary search.
    272 
    273 **Tutorial and Implementation**
    274 
    275 Tutorial is loading...
    276 
    277 [255371862](/contest/1951/submission/255371862 "Submission 255371862 by Kuroni")
    278 
    279 **Rate this problem**
    280 
    281 Yay
    282 
    283 Meh
    284 
    285 Nay
    286 
    287 Banger song
    288 
    289 **UPD**: Added implementations.