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