codeforces-scrape

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

2178.md (14835B)


      1 Source: https://codeforces.com/blog/entry/149548
      2 
      3 We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated!
      4 
      5 **Rate the contest**
      6 
      7 * Great contest:
      8 * Good contest:
      9 * Average contest:
     10 * Bad contest:
     11 
     12 ---
     13 
     14 **Did Franklin (from problem D) succeed in massacring a village of innocent elves like Frieren and Dilhan (from problem E)?**
     15 
     16 The official lore is that he got lost in a forest of oddly colored Christmas trees (from problem F) and decided instead to write this editorial.
     17 
     18 ## [2178A - Yes or Yes](/contest/2178/problem/A "Good Bye 2025")
     19 
     20 **Did you like the problem?**
     21 
     22 * Great problem:
     23 * Good problem:
     24 * Average problem:
     25 * Bad problem:
     26 * Did not solve:
     27 
     28 Idea: [conqueror_of_tourist](/profile/conqueror_of_tourist "Legendary Grandmaster conqueror_of_tourist")   
     29  Preparation + Editorial: [conqueror_of_tourist](/profile/conqueror_of_tourist "Legendary Grandmaster conqueror_of_tourist")
     30 
     31 **Hint 1**
     32 
     33 What can we say about the number of 'Yes's.
     34 
     35 **Hint 2**
     36 
     37 Consider the number of 'Yes's in the string, and what happens to this number during an operation.
     38 
     39 **Solution**
     40 
     41 Tutorial is loading...
     42 
     43 **Implementation**
     44 
     45 [Python](/contest/2178/submission/355426719 "Submission 355426719 by twosquares"), [C++](/contest/2178/submission/355426729 "Submission 355426729 by twosquares")
     46 
     47 ## [2178B - Impost or Sus](/contest/2178/problem/B "Good Bye 2025")
     48 
     49 **Did you like the problem?**
     50 
     51 * Great problem:
     52 * Good problem:
     53 * Average problem:
     54 * Bad problem:
     55 * Did not solve:
     56 
     57 Idea: [YuukiS](/profile/YuukiS "Grandmaster YuukiS")   
     58  Preparation + Editorial: [twosquares](/profile/twosquares "Master twosquares"), [YuukiS](/profile/YuukiS "Grandmaster YuukiS")
     59 
     60 **Hint 1**
     61 
     62 You have a suspicious string. For a fixed u, suppose the closest s is two characters to the right. Where must the other s be?
     63 
     64 **Answer 1**
     65 
     66 It must be two characters to the left. In particular, the two s's must be on opposite sides of the u.
     67 
     68 **Hint 2**
     69 
     70 You have a suspicious string. Suppose there are two consecutive u's. Let the closest s to the left u is three characters to the left. Where must the other s be? Where must the closest s's to the right u be?
     71 
     72 **Answer 2**
     73 
     74 The s must be three characters to the right, which is two characters to the right of the right u. However, this implies that there must be a corresponding s two characters to the left, which would be the closest s of the left u. By this reasoning, there cannot be two consecutive u's.
     75 
     76 **Solution**
     77 
     78 Tutorial is loading...
     79 
     80 **Implementation**
     81 
     82 [Python](/contest/2178/submission/355426807 "Submission 355426807 by twosquares"), [C++](/contest/2178/submission/355426795 "Submission 355426795 by twosquares")
     83 
     84 ## [2178C - First or Second](/contest/2178/problem/C "Good Bye 2025")
     85 
     86 **Did you like the problem?**
     87 
     88 * Great problem:
     89 * Good problem:
     90 * Average problem:
     91 * Bad problem:
     92 * Did not solve:
     93 
     94 Idea: [YuukiS](/profile/YuukiS "Grandmaster YuukiS")   
     95  Preparation + Editorial: [conqueror_of_tourist](/profile/conqueror_of_tourist "Legendary Grandmaster conqueror_of_tourist"), [YuukiS](/profile/YuukiS "Grandmaster YuukiS")
     96 
     97 **Hint 1**
     98 
     99 The number of children on the naughty and nice lists combined will be $n-1$. However, not all assignments to the naughty and nice lists are possible. Try figuring out exactly which assignments are possible.
    100 
    101 **Hint 2**
    102 
    103 Exactly one child will not be chosen by Santa. If we fix/decide which child this will be, what can we say about the other children?
    104 
    105 **Solution**
    106 
    107 Tutorial is loading...
    108 
    109 **Implementation**
    110 
    111 [Python](/contest/2178/submission/355426814 "Submission 355426814 by twosquares"), [C++](/contest/2178/submission/355426832 "Submission 355426832 by twosquares")
    112 
    113 ## [2178D - Xmas or Hysteria](/contest/2178/problem/D "Good Bye 2025")
    114 
    115 **Did you like the problem?**
    116 
    117 * Great problem:
    118 * Good problem:
    119 * Average problem:
    120 * Bad problem:
    121 * Did not solve:
    122 
    123 Idea: [twosquares](/profile/twosquares "Master twosquares")   
    124  Preparation + Editorial: [twosquares](/profile/twosquares "Master twosquares"), [YuukiS](/profile/YuukiS "Grandmaster YuukiS")
    125 
    126 **Hint 1**
    127 
    128 Fix the $m$ surviving elves. They must have attacked. Who are the targets of these attacks? What happens to those targets?
    129 
    130 **Answer 1**
    131 
    132 Each surviving elf must have attacked a smaller elf. Those elves die.
    133 
    134 **Hint 2**
    135 
    136 Find an upper bound on the number of elves that can survive.
    137 
    138 **Answer 2**
    139 
    140 For each surviving elf, there must be a corresponding target elf that it attacks, which dies immediately (and cannot be attacked by other surviving elves). Therefore, at most $\lfloor n/2 \rfloor$ elves can survive.
    141 
    142 **Hint 3**
    143 
    144 Once the elves that survive are fixed, and the elves they attack are fixed, there may be some remaining elves, which should not survive. Find a way to deal with them.
    145 
    146 **Hint 4**
    147 
    148 $m=0$ must be handled separately (why?). The hardest part is killing the strongest elf. Figure out when it is possible and how to do so.
    149 
    150 **Solution**
    151 
    152 Tutorial is loading...
    153 
    154 **Implementation**
    155 
    156 [Python](/contest/2178/submission/355426867 "Submission 355426867 by twosquares"), [C++](/contest/2178/submission/355426986 "Submission 355426986 by Auchenai01") (by [Auchenai01](/profile/Auchenai01 "Master Auchenai01"))
    157 
    158 ## [2178E - Flatten or Concatenate](/contest/2178/problem/E "Good Bye 2025")
    159 
    160 **Did you like the problem?**
    161 
    162 * Great problem:
    163 * Good problem:
    164 * Average problem:
    165 * Bad problem:
    166 * Did not solve:
    167 
    168 Idea: [twosquares](/profile/twosquares "Master twosquares")   
    169  Preparation + Editorial: [twosquares](/profile/twosquares "Master twosquares")
    170 
    171 **Hint 1**
    172 
    173 What are the properties/invariants of the flatten operation? Use this to find an invariant on $a$ and $b$.
    174 
    175 **Answer 1**
    176 
    177 The sum of the entire array is invariant under the flatten operation. This means $a$ and $b$ always have the same sum.
    178 
    179 **Hint 2**
    180 
    181 Assume there are no flatten operations after the final concatenate (why?). Can we find where in the hidden array $a$ the final concatenate happened?
    182 
    183 **Hint 3**
    184 
    185 From the previous hint, the final array can be split into the two arrays before the final concatenate. Which array contains the maximum?
    186 
    187 **Hint 3.1**
    188 
    189 The two arrays were flattened from some common ancestor — i.e., they were once equal before being flattened into their state just before the final concatenate. Only flatten operations have happened since they were equal.
    190 
    191 **Hint 3.2**
    192 
    193 If one array was flattened more times than the other, which contains the maximum?
    194 
    195 **Hint 3.3**
    196 
    197 How can you tell which array was flattened more times?
    198 
    199 **Answer**
    200 
    201 Flattening is an operation that intuitively "pushes down" the maximum; the array that is flattened fewer times is guaranteed to contain the maximum. Flattening also increases the length of the array by $1$, so the shorter array contains the maximum.
    202 
    203 **Hint 4**
    204 
    205 Recurse.
    206 
    207 **Solution**
    208 
    209 Tutorial is loading...
    210 
    211 **Implementation**
    212 
    213 [Python](/contest/2178/submission/355427050 "Submission 355427050 by twosquares"), [C++](/contest/2178/submission/355423821 "Submission 355423821 by Auchenai01") (by [Auchenai01](/profile/Auchenai01 "Master Auchenai01"))
    214 
    215 **Bonus**
    216 
    217 How would you write a validator for this problem? That is, given $n$ and an array $a$, determine if it can be generated by the described operations.
    218 
    219 ## [2178F - Conquer or of Forest](/contest/2178/problem/F "Good Bye 2025")
    220 
    221 **Did you like the problem?**
    222 
    223 * Great problem:
    224 * Good problem:
    225 * Average problem:
    226 * Bad problem:
    227 * Did not solve:
    228 
    229 Idea: [YuukiS](/profile/YuukiS "Grandmaster YuukiS")   
    230  Preparation + Editorial: [conqueror_of_tourist](/profile/conqueror_of_tourist "Legendary Grandmaster conqueror_of_tourist"), [YuukiS](/profile/YuukiS "Grandmaster YuukiS")
    231 
    232 **Hint 0**
    233 
    234 Try drawing the operation on some not small graphs!
    235 
    236 **Hint 1**
    237 
    238 What are the invariants of the operation?
    239 
    240 **Answer 1**
    241 
    242 The number of white vertices does not change. It also seems a lot of white vertices don't move or only move to a neighboring vertex.
    243 
    244 **Hint 2**
    245 
    246 In a single operation, what are some shared properties of the vertices whose color changed?
    247 
    248 **Answer 2**
    249 
    250 Color changes only occur within the detached subtree (why?) and it is a necessary condition that a vertex with a new color has a new parent.
    251 
    252 **Hint 3**
    253 
    254 Based on Hint 2, try to characterize the set of edges that cannot be removed no matter what operations are applied.
    255 
    256 **Answer 3**
    257 
    258 The parent edge of any black vertex cannot be removed (why?). Any other edge can be freely added and removed as long as T is a tree.
    259 
    260 **Hint 4**
    261 
    262 Consider the connected components formed by the parent edge of all black vertices (in other words, after cutting the parent edge of any white vertex). Which vertex is white within this component?
    263 
    264 **Answer 4**
    265 
    266 Exactly one vertex is white and it is the one closest to the root.
    267 
    268 **Hint 5**
    269 
    270 What does the *conquered* condition mean in terms of these connected components?
    271 
    272 **Solution**
    273 
    274 Tutorial is loading...
    275 
    276 **Implementation**
    277 
    278 [Python](/contest/2178/submission/355427800 "Submission 355427800 by golomb") (by [golomb](/profile/golomb "Grandmaster golomb")), [C++](/contest/2178/submission/355427077 "Submission 355427077 by twosquares")
    279 
    280 ## [2178G - deCH OR Dations](/contest/2178/problem/G "Good Bye 2025")
    281 
    282 **Did you like the problem?**
    283 
    284 * Great problem:
    285 * Good problem:
    286 * Average problem:
    287 * Bad problem:
    288 * Did not solve:
    289 
    290 Idea: [YuukiS](/profile/YuukiS "Grandmaster YuukiS")   
    291  Preparation + Editorial: [YuukiS](/profile/YuukiS "Grandmaster YuukiS")
    292 
    293 **Hint 1**
    294 
    295 Try to solve the problem for only $\ell=n$.
    296 
    297 **Hint 1.1**
    298 
    299 Figure out how to count the number of chains containing a specific chord (without caring about complexity)
    300 
    301 **Answer 1.1**
    302 
    303 Any chain containing a specific chord can be decomposed into a chain ending at the chord and a chain starting at the chord. Because these parts are independent the number of chains is [number of chains ending at the chord] x [number of chains starting at the chord].
    304 
    305 **Hint 1.2**
    306 
    307 Figure out how we can compute the number of chains ending at chord $1\ldots n$ in quadratic time.
    308 
    309 **Answer 1.2**
    310 
    311 For a given chord $j$, the number of chains ending at $j$ is the sum of number of chains ending at chord $i \lt j$ for every chord $i$ that intersects chord $j$ plus one (for the chain consisting of just $j$)
    312 
    313 **Hint 1.3**
    314 
    315 You only care about parity. Figure out how to speed this up to $O(n\log n)$.
    316 
    317 **Answer 1.3**
    318 
    319 Consider an XOR Fenwick Tree of size $2n$, where at $x_i$ and $y_i$ you store the parity of number of chains ending at chord $I$. Then, the value in Hint 1.2 can be found by a range XOR query over $[x_j, y_j]$ because any chord not intersecting chord $j$ will either be accounted for $0$ or $2$ times.
    320 
    321 **Hint 2**
    322 
    323 The problem forces you to incrementally compute the values for $\ell=1\ldots n$. Try to solve the problem in quadratic or cubic time while only allowing yourself to consider the chords in order (i.e. you're not allowed to go backwards to compute the number of chains starting at a given chord).
    324 
    325 **Answer 2**
    326 
    327 In addition to storing the parity of number of chains ending at chord $i$, also store the set of chords $k \lt i$ such that chord $k$ appears in an odd number of chains ending at chord $i$. Then, for a fixed $\ell$, we want to check whether every chord appears in an even number of sets (this can all be done with $n$ Fenwick trees, one for each chord).
    328 
    329 **Hint 3**
    330 
    331 You have yet to use the fact that we want *every* chord to appear an even number of times (that is, we do not need to know the specific parity for each chord). Use this to speed the solution up to $O(n\log n)$.
    332 
    333 **Solution**
    334 
    335 Tutorial is loading...
    336 
    337 **Implementation**
    338 
    339 [Python](/contest/2178/submission/355428997 "Submission 355428997 by golomb") (by [golomb](/profile/golomb "Grandmaster golomb")), [C++](/contest/2178/submission/356049651 "Submission 356049651 by YuukiS")
    340 
    341 ## [2178H - Create or Duplicate](/contest/2178/problem/H "Good Bye 2025")
    342 
    343 **Did you like the problem?**
    344 
    345 * Great problem:
    346 * Good problem:
    347 * Average problem:
    348 * Bad problem:
    349 * Did not solve:
    350 
    351 Idea: [YuukiS](/profile/YuukiS "Grandmaster YuukiS")   
    352  Preparation + Editorial: [conqueror_of_tourist](/profile/conqueror_of_tourist "Legendary Grandmaster conqueror_of_tourist"), [YuukiS](/profile/YuukiS "Grandmaster YuukiS")
    353 
    354 **Hint 1**
    355 
    356 The operation is clearly independent for each present. Solve the problem for a single type of present with value $a$.
    357 
    358 **Answer 1**
    359 
    360 Consider a graph with vertices $0\ldots m-1$. We draw an edge from $x \to (x+a) \text{ mod } m$ with cost $a$ and an edge from $x \to 2\cdot x \text{ mod } m$ with cost $k$. The desired answer is the shortest path from $a$ to $0$. However, it is not possible to combine the results for all three types without $O(n^2)$ $(\min, +)$ convolution.
    361 
    362 **Hint 2**
    363 
    364 There is one big idea that you need from here, the following small hints may help in getting you there.
    365 
    366 **Hint 2.1**
    367 
    368 It may be easier to start with no presents (but eventually force yourself to have all three).
    369 
    370 **Hint 2.2**
    371 
    372 Although we considered the operations for a given type of present independently from other types in Hint 1, we are allowed to intertwine operations as we wish.
    373 
    374 **Hint 2.3**
    375 
    376 If we tried to merge all three presents into a single graph, the primary issue is that we need to maintain three separate modulos to handle the duplicate spell. Is there any way we can fix this?
    377 
    378 **Solution**
    379 
    380 Tutorial is loading...
    381 
    382 **Implementation**
    383 
    384 [C++](/contest/2178/submission/356049605 "Submission 356049605 by YuukiS") (model sol), [C++](/contest/2178/submission/355423773 "Submission 355423773 by Auchenai01") (by [Auchenai01](/profile/Auchenai01 "Master Auchenai01"), with an optimization)
    385 
    386 **Bonus**
    387 
    388 Solve the problem in $\mathcal{O}(m)$.
    389 
    390 ## [2178I - Numbers or Fireworks](/contest/2178/problem/I "Good Bye 2025")
    391 
    392 **Did you like the problem?**
    393 
    394 * Great problem:
    395 * Good problem:
    396 * Average problem:
    397 * Bad problem:
    398 * Did not solve:
    399 
    400 Idea: [YuukiS](/profile/YuukiS "Grandmaster YuukiS")   
    401  Preparation + Editorial: [conqueror_of_tourist](/profile/conqueror_of_tourist "Legendary Grandmaster conqueror_of_tourist"), [YuukiS](/profile/YuukiS "Grandmaster YuukiS")
    402 
    403 **Hint 1a**
    404 
    405 The input essentially just creates a graph, where cities are connected if they are at distanct $\sqrt{k}$. Can you find any special properties that this graph has?
    406 
    407 **Hint 1b**
    408 
    409 The input graph is bipartite.
    410 
    411 **Hint 2**
    412 
    413 One of the color classes of the bipartite graph must have size at most 15
    414 
    415 **Hint 3**
    416 
    417 Try finding an equivalent formulation to what the explosiveness can mean (in particular, try assigning some `value' to each node not in $T$
    418 
    419 **Hint 4**
    420 
    421 We can brute force over all possible subsets of the smaller bipartite class.
    422 
    423 **Solution**
    424 
    425 Tutorial is loading...
    426 
    427 **Implementation**
    428 
    429 [C++](/contest/2178/submission/355428998 "Submission 355428998 by twosquares")