codeforces-scrape

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

2258.md (10278B)


      1 Source: https://codeforces.com/blog/entry/156316
      2 
      3 Sorry for underestimating the difficulties of the problems, especially B2 and D. We tried to serve as many cool problems as we could. And apparently, this led to some difficult ones.
      4 
      5 Thank you for participating in the round. We all hope you enjoyed all of our problems.
      6 
      7 [2258A - Odd Eraser](/contest/2258/problem/A "Codeforces Round 1118 (Div. 2)") Idea: [ItsNotMeItsYou](/profile/ItsNotMeItsYou "Master ItsNotMeItsYou"), [mychecksdead](/profile/mychecksdead "Master mychecksdead")
      8 
      9 **Hint1**
     10 
     11 Think of the case $n=3$. Can you remove the first or the last number in any way?
     12 
     13 **Solution**
     14 
     15 We cannot obtain a number larger than $\gcd(a_1,a_n)$ because the first and last numbers in the array can't be removed. We can remove all other elements by choosing $[1, i, n]$, so the answer is $\gcd(a_1, a_n)$.
     16 
     17 **Code**
     18 
     19 [388911115](/contest/2258/submission/388911115 "Submission 388911115 by ItsNotMeItsYou")
     20 
     21 **Rate the problem**
     22 
     23 Amazing
     24 
     25 Good
     26 
     27 Ok
     28 
     29 Bad
     30 
     31 Terrible
     32 
     33 [2258B1 - Carrot Chopdown (Easy Version)](/contest/2258/problem/B1 "Codeforces Round 1118 (Div. 2)") Idea: [mychecksdead](/profile/mychecksdead "Master mychecksdead")
     34 
     35 **Hint1**
     36 
     37 What is the answer for a fixed $x$?
     38 
     39 **Solution**
     40 
     41 Iterating over the values $x=1...m$, we can find the answer for each possible $x$.
     42 
     43 For any $x$, the answer is the number of carrots of length greater than or equal to $x$, plus the number of carrots of length $2x$.
     44 
     45 **Code**
     46 
     47 [388911137](/contest/2258/submission/388911137 "Submission 388911137 by ItsNotMeItsYou")
     48 
     49 **Rate the problem**
     50 
     51 Amazing
     52 
     53 Good
     54 
     55 Ok
     56 
     57 Bad
     58 
     59 Terrible
     60 
     61 [2258B2 - Carrot Chopdown (Hard Version)](/contest/2258/problem/B2 "Codeforces Round 1118 (Div. 2)") Idea: [mychecksdead](/profile/mychecksdead "Master mychecksdead") (This problem was originally designed with only $k=2$; thanks to [ItsNotMeItsYou](/profile/ItsNotMeItsYou "Master ItsNotMeItsYou") for expanding on the idea.)
     62 
     63 **Hint1**
     64 
     65 Consider solving the problem for a fixed $x$.
     66 
     67 **Hint2**
     68 
     69 Consider solving the problem for $k=2$.
     70 
     71 **Hint3**
     72 
     73 What happens if $k$ is bigger than $18$?
     74 
     75 **Hint4**
     76 
     77 What are the optimal $x$ values for cutting?
     78 
     79 **Solution**
     80 
     81 For target value $x$, it is optimal to use cuts in the following order: $x \cdot 2^{k-1}, x \cdot 2^{k-2}, \ldots, x \cdot 1$.
     82 
     83 For each $i$, $a_i=2^k \cdot x$ adds $2^k$ to the answer. Otherwise, the contribution is $\min(\frac{a_i}{x}, 2^k-1)$.
     84 
     85 The optimal $x$ is less than or equal to $\frac{m}{2^k}$ (if less than $1$, it equals $1$, and the answer is basically the sum of all carrot lengths). Moreover, no $i$ can contribute more than $2^k$ to any $x$. Using prefix sum, determine the number of values contributing $y$ to the answer for each possible $x$. This solution runs in $\mathcal{O}(n + m \log m)$.
     86 
     87 **Code**
     88 
     89 [388911156](/contest/2258/submission/388911156 "Submission 388911156 by ItsNotMeItsYou")
     90 
     91 **Rate the problem**
     92 
     93 Amazing
     94 
     95 Good
     96 
     97 Ok
     98 
     99 Bad
    100 
    101 Terrible
    102 
    103 [2258C - Far Cities](/contest/2258/problem/C "Codeforces Round 1118 (Div. 2)") Idea: [Seferoglu](/profile/Seferoglu "Expert Seferoglu") (This problem was originally designed simply to find the furthest node from the root; thanks to [cadmiumky](/profile/cadmiumky "Grandmaster cadmiumky") for expanding on the idea. Thanks to [robert9524](/profile/robert9524 "Candidate Master robert9524") for providing stronger tests on cutting random solutions without an adaptive grader.)
    104 
    105 **Hint1**
    106 
    107 How to find a diameter?
    108 
    109 **Hint2**
    110 
    111 Consider the simplest algorithm.
    112 
    113 **Solution**
    114 
    115 For each node, first determine whether it is closer to the first vertex than the longest distance seen so far. If not, just skip the node. This uses $n-1$ queries. Otherwise, while the query returns true, increase the queried distance by one. This can happen up to $n-1$ times. We can find one end of the diameter by running $2n - 2$ queries in total. Then repeat the process to find the other end of the diameter. This yields a total of $4n-4$ queries. But, as previously written, distance can increase at most $n-1$ times. So this yields a total of $3n-3$ queries.
    116 
    117 **Code**
    118 
    119 [388911205](/contest/2258/submission/388911205 "Submission 388911205 by ItsNotMeItsYou")
    120 
    121 **Rate the problem**
    122 
    123 Amazing
    124 
    125 Good
    126 
    127 Ok
    128 
    129 Bad
    130 
    131 Terrible
    132 
    133 [2258D - Magic Tiles](/contest/2258/problem/D "Codeforces Round 1118 (Div. 2)") Idea: [ItsNotMeItsYou](/profile/ItsNotMeItsYou "Master ItsNotMeItsYou")
    134 
    135 **Hint1**
    136 
    137 What happens when a range includes another?
    138 
    139 **Hint2**
    140 
    141 A range that is included by another range is useless. What happens when we remove all such useless ranges?
    142 
    143 **Hint3**
    144 
    145 We only need to solve the problem for chains of ranges. How?
    146 
    147 **Solution**
    148 
    149 In this editorial we will use BigIntegers, which are simple vectors, and addition and comparison is $\mathcal{O}(n)$. It can be proven that if one range includes another, we can remove the other. Also, it can be proven that only start and endpoints of the intervals are important, and let them be $pts$. Well-known $\mathcal{O}(n^3)$ dp exists; $dp_i$ means the maximum score if we fill all of the rows through $pts_i$; $dp_i=\max dp_j + 100^{100^{i-j}}$ if there is an interval that covers interval $[j, i)$. Because there are only $2$ columns, it can be proven that this solution works in $\mathcal{O}(n^2)$. From another perspective, you can imagine you have chains.
    150 
    151 **Code**
    152 
    153 [388911243](/contest/2258/submission/388911243 "Submission 388911243 by ItsNotMeItsYou")
    154 
    155 **Rate the problem**
    156 
    157 Amazing
    158 
    159 Good
    160 
    161 Ok
    162 
    163 Bad
    164 
    165 Terrible
    166 
    167 **Challenge**
    168 
    169 Can you solve for bigger constraints, such as $n,m \le 2 \cdot 10^5$? Thanks to [dinohaur](/profile/dinohaur "Master dinohaur") for the code: [388911329](/contest/2258/submission/388911329 "Submission 388911329 by ItsNotMeItsYou")
    170 
    171 **Answer**
    172 
    173 With using faster BigIntegers, you can solve in $\mathcal{O}(n \log n)$. For more info: <https://codeforces.com/problemset/problem/464/E>
    174 
    175 [2258E - DivMEX](/contest/2258/problem/E "Codeforces Round 1118 (Div. 2)") Idea: [ItsNotMeItsYou](/profile/ItsNotMeItsYou "Master ItsNotMeItsYou"), [carcinisation](/profile/carcinisation "International Master carcinisation") (This problem was actually designed differently. Thanks to [anpaio](/profile/anpaio "International Grandmaster anpaio") for this version.)
    176 
    177 **Hint1**
    178 
    179 What kind of integers can exist as an $f(l,r)=x$ value?
    180 
    181 **Hint2**
    182 
    183 How to check a value $x$ exists as a $f(l,r)$?
    184 
    185 **Solution**
    186 
    187 It can be seen that each value of $f$ must satisfy $f(l,r) \leq \text{smallest prime power bigger than n}$; for each $x$ that satisfies this constraint, we will try to check whether this value can be obtained or not.
    188 
    189 A range that satisfies $f(l,r)=x$ can't contain a multiple of $x$; otherwise, the set of divisors would have $x$ in it. When considering multiples of $x$ as obstacles, we realize that it is optimal to greedily select between two consecutive obstacles. Hence, at each obstacle, we check whether every number $y$ that satisfies $1 \leq y \le x$ appears as a factor of any integer between this and the previous obstacle. This solution works in $\mathcal{O}(( \sum_{i=1}^n |S_i|) \cdot n$. Where $S_x$ represents the prime powers of $x$.
    190 
    191 To optimize this solution, we iterate over all $a_i$ and check every factor of $a_i$, considering the index $i$ as an obstacle. In order to verify that every element smaller than $x$ is present between this and the previous obstacle, use a minimum segment tree. This solution works in $\mathcal{O}(( \sum_{i=1}^n |S_i|) \log n) \le \mathcal{O}(n \log^2 n)$.
    192 
    193 **Code (anpaio)**
    194 
    195 [388911266](/contest/2258/submission/388911266 "Submission 388911266 by ItsNotMeItsYou")
    196 
    197 **Rate the problem**
    198 
    199 Amazing
    200 
    201 Good
    202 
    203 Ok
    204 
    205 Bad
    206 
    207 Terrible
    208 
    209 [2258F - Plus Minus Tree](/contest/2258/problem/F "Codeforces Round 1118 (Div. 2)") Idea: [ItsNotMeItsYou](/profile/ItsNotMeItsYou "Master ItsNotMeItsYou")
    210 
    211 **Solution**
    212 
    213 Consider $\mathcal{O}(n^2)$ $dp[v][\text{#1's count in subtree of v}]$ using the merging subtrees technique. The dp is convex because we are adding only two convex functions, resulting in a convex function. Then, using small to large, you can achieve $\mathcal{O}(n \log^2 n)$ complexity.
    214 
    215 To elaborate:
    216 
    217 For $\mathcal{O}(n^2)$, you can keep dp as pairs for simplicity: $(\text{score of v}, \text{minimum score})$.
    218 
    219 As can be seen in the vector, scores are increasing by $2$. So you can keep dp with the vector's first element and then with the differences. When you merge two children's subtrees, you are basically doing a Minkowski sum, which is just updating the first element as $\text{(lhs[0].first + rhs[0].first, lhs[0].second + rhs[0].second})$, and merging the differences.
    220 
    221 Then, for each point added to $|x|$, you must add $+2$ or $-2$ ($2$ due to parity) for all differences split by $0$ (be careful not to add any difference to $[-1, +1]$).
    222 
    223 You can maintain two sets for each vertex, resulting in $\mathcal{O}(n \log^2 n)$ complexity from small to large.
    224 
    225 **Code**
    226 
    227 [388911297](/contest/2258/submission/388911297 "Submission 388911297 by ItsNotMeItsYou")
    228 
    229 **Alternative Solution**
    230 
    231 First, identify all nodes in the tree with an initial value of zero, set them to one, and store them in a candidate list. Then, until the list is completely empty, select the most advantageous node at each step. For each node, we trace the path up to the root, counting how many nodes along that path have a subtree sum greater than one ($\text{pos}$) and how many have a subtree sum less than one ($\text{neg}$), thereby calculating a score based on the difference $\text{pos} - \text{neg}$.
    232 
    233 After finding the node with the highest score among the list, select it, change its value to minus one, and decrease the subtree sums of all ancestors along the path from the chosen node to the root by two. We repeat this process until all special nodes are processed and the list is empty. And you can fasten this algorithm by HLD.
    234 
    235 $\mathcal{O}(n^3)$ code by [anpaio](/profile/anpaio "International Grandmaster anpaio"): [388911953](/contest/2258/submission/388911953 "Submission 388911953 by ItsNotMeItsYou") $\mathcal{O}(n \log^2 n)$ code by [anpaio](/profile/anpaio "International Grandmaster anpaio"): [388911806](/contest/2258/submission/388911806 "Submission 388911806 by ItsNotMeItsYou")
    236 
    237 **Rate the problem**
    238 
    239 Amazing
    240 
    241 Good
    242 
    243 Ok
    244 
    245 Bad
    246 
    247 Terrible