2078.md (25740B)
1 Source: https://codeforces.com/blog/entry/140505 2 3 I hope everyone enjoyed the tasks, and thank you for participating. 4 5 Thank you to the coordinators and testers for suggesting solutions and modifications to the tasks, as I alone wouldn't be able to solve my own tasks or make it to how it is right now. Also thank you to them for dealing with me since July. 6 7 Please tell me in the comments if the editorial is written incorrectly or unintelligibly somewhere. I'm not the best at phrasing some things, and would appreciate amendments to the editorial. 8 9 [2078A - Final Verdict](/contest/2078/problem/A "Codeforces Round 1008 (Div. 2)") 10 11 **Hint** 12 13 Something doesn't change after each operation. 14 15 **Solution** 16 17 The average of the entire array doesn't change after each operation. Simply check whether the average value of $a$ is $x$ or not. 18 19 Time complexity: $\mathcal{O}(n)$ per test case. 20 21 Submission: [310297520](/contest/2078/submission/310297520 "Submission 310297520 by omsincoconut") 22 23 [2078B - Vicious Labyrinth](/contest/2078/problem/B "Codeforces Round 1008 (Div. 2)") 24 25 **Hint 1** 26 27 Try to put as many people in cell $n$ as possible. 28 29 **Hint 2** 30 31 The minimum sum of distances will always be $1$. 32 33 **Solution** 34 35 The following configuration gives $1$ as the sum of distances. 36 37 For odd $k$: $n, n, \ldots, n, n, n-1$ 38 39 For even $k$: $n-1, n-1, \ldots, n-1, n, n-1$ 40 41 And the sum of distances cannot be $0$. 42 43 **Proof** 44 45 Look at this as a directed (or more specifically, a functional) graph. There will be a cycle, and people in the same cycle will never be in the same cell, so not everyone can simultaneously be in cell $n$. 46 47 Time complexity: $\mathcal{O}(n)$ per test case. 48 49 Submission: [310297574](/contest/2078/submission/310297574 "Submission 310297574 by omsincoconut") 50 51 **Extra** 52 53 Prove that the optimal configuration is unique. 54 55 [2077A - Breach of Faith](/contest/2077/problem/A "Codeforces Round 1008 (Div. 1)") 56 57 **Hint 1** 58 59 Rearrange the equation around. 60 61 **Hint 2** 62 63 Try to maximize the missing number. 64 65 **Solution** 66 67 The equation can be rearranged to 68 69 $ a_{2n} = a_1 + (a_3 - a_2) + (a_5 - a_4) + \ldots + (a_{2n-1} - a_{2n-2}) + a_{2n+1} $ 70 71 Choose $a_1$ as the largest number, $a_3, a_5, \ldots, a_{2n+1}$ as the next $n$ largest numbers, and the rest as $a_2, a_4, \ldots, a_{2n-2}$. The value of the missing number $a_{2n}$ will be larger than $a_1$, and so larger than every number in $b$. 72 73 Time complexity: $\mathcal{O}(n \log n)$ per test case. Logarithmic factor is from sorting. 74 75 Submission: [310297635](/contest/2077/submission/310297635 "Submission 310297635 by omsincoconut") 76 77 **Note** 78 79 There are some randomization solutions where we just shuffle $b$ randomly, fill the missing number, and attempt it as a possible solution. I do not have a proof or disproof of whether this would work well enough. 80 81 [2078D - Scammy Game Ad](/contest/2078/problem/D "Codeforces Round 1008 (Div. 2)") 82 83 **Hint 1** 84 85 It is optimal to place everyone on the same lane. 86 87 **Hint 2** 88 89 Think about the multiplier. 90 91 **Hint 3** 92 93 It is best to think of each $\tt{+}$ as "how much can we multiply this by". 94 95 **Solution 1** 96 97 This is the **greedy** solution. 98 99 When we get more people, place all to where the $\tt{x}$ will occur first. If both lanes have the next multiply at the same gate pair, then choose the one with higher multiply. If the multiply is the same, look to the next multiply. 100 101 **Proof** 102 103 It's easier to think of $\tt{+}$ as $\tt{x} 1$. The idea is as follows. 104 105 Consider the range of gate pairs between two pairs with different multiply, and the pairs in the range all have the same multiply. You have $l$ people on the left side and $r$ on the right side before you enter the range. In this range, you will gain a constant number of people, say $x$, regardless of your actions here. You choose to allocate $y$ to the left side. 106 107 At the end of the range, there's a pair of gates $\tt{x} a$ $\tt{x} b$ where $a \gt b$ (same argument for case $a \lt b$). After passing the gate, you will gain $(a-1)(l+y) + (b-1)(r+x-y)$ more people. With the current number people of $l+y$ on the left side and $r+x-y$ on the right side, we can see that maximizing $y$ is the optimal choice, because there always exist an allocation such that both number of people on the left and right side will exceed those with lower selection of $y$. 108 109 Time complexity: $\mathcal{O}(n)$ per test case. $\mathcal{O}(n^2)$ implementations are also acceptable. 110 111 Submission: [310297718](/contest/2078/submission/310297718 "Submission 310297718 by omsincoconut") 112 113 **Solution 2** 114 115 This is the **dynamic programming** solution. 116 117 Let $dp_l[i]$ and $dp_r[i]$ be the maximum possible multiplication possible that can be applied if a person enters the $i$-th left and right gate, respectively. Then we have the following equation (only for left is written, it's the same for the right). 118 119 If the gate is $\tt{+}$ 120 121 $dp_l[i] = dp_l[i+1]$ 122 123 If the gate is $\tt{x}$ by $a$ 124 125 $dp_l[i] = dp_l[i+1] + (a-1)\max(dp_l[i+1], dp_r[i+1])$ 126 127 For each $\tt{+}$, we choose to place people at the side with more multiplication. 128 129 Time complexity: $\mathcal{O}(n)$ per test case. 130 131 Submission: [310297763](/contest/2078/submission/310297763 "Submission 310297763 by omsincoconut") 132 133 **Note** 134 135 $n = 30$ constraint is due to overflow. The maximum answer is the case with $n = 30$, the first pair of gates is $\tt{+} 1000$ $\tt{+} 1000$, and the other pairs of gates are $\tt{+} 1000$ $\tt{x} 3$, giving the answer $171644573789571884 \lt 10^{18}$. 136 137 It is possible to solve this task under modulo and force $\mathcal{O}(n)$ solution, but it will be hard, or maybe impossible, to implement the DP solution which requires min/max operations, so I decided against it. 138 139 [2077B - Finding OR Sum](/contest/2077/problem/B "Codeforces Round 1008 (Div. 1)") 140 141 **Hint 1** 142 143 Try to get information on half of the bits. 144 145 **Hint 2** 146 147 Alternate the bits. 148 149 **Solution** 150 151 The queries are $\ldots 0101_2$ and $\ldots 1010_2$. 152 153 It's easier to look at the case with only two binary digits first. 154 155 Let the result of query $01_2$ be $q_1$ and $10_2$ be $q_2$. 156 157 Observe that if 158 159 * $q_2 = 100_2$ then the first (from the right) digit of both $x$ and $y$ is $0$. 160 * $q_2 = 101_2$ then the first (from the right) digit of one of $x$ or $y$ is $0$, and the other one is $1$. 161 * $q_2 = 110_2$ then the first (from the right) digit of both $x$ and $y$ is $1$. 162 163 Similarly, if 164 165 * $q_1 = 10_2$ then the second (from the right) digit of both $x$ and $y$ is $0$. 166 * $q_1 = 100_2$ then the second (from the right) digit of one of $x$ or $y$ is $0$, and the other one is $1$. 167 * $q_1 = 110_2$ then the second (from the right) digit of both $x$ and $y$ is $1$. 168 169 To generalize to every other digit, apply the same logic to every consecutive pair of digits in $x$ and $y$. Note that you must account for the carries from the digits before too. 170 171 After this, you will know for every digit position whether both $x$ and $y$ are $0$, are $1$, or have one $0$ and one $1$. You can use this information to find $(m|x) + (m|y)$ for any $m$. 172 173 Time complexity: $\mathcal{O}(\log \max (x))$ per test case. 174 175 Submission: [310297820](/contest/2077/submission/310297820 "Submission 310297820 by omsincoconut") 176 177 [2077C - Binary Subsequence Value Sum](/contest/2077/problem/C "Codeforces Round 1008 (Div. 1)") 178 179 **Hint 1** 180 181 Find a closed-form expression for the score of a binary string. 182 183 **Hint 2** 184 185 The closed-form expression for the score of a binary string is 186 187 $\lfloor \frac{cnt_0-cnt_1}{2} \rfloor \lceil \frac{cnt_0-cnt_1}{2} \rceil$ 188 189 Where $cnt_0$ and $cnt_1$ are the number of $\tt{0}$ and $\tt{1}$ in the binary string, respectively. 190 191 **A useful rearrangement** 192 193 $\lfloor \frac{cnt_0-cnt_1}{2} \rfloor \lceil \frac{cnt_0-cnt_1}{2} \rceil = \frac{(cnt_0-cnt_1)^2}{4} - \frac{(cnt_0-cnt_1 \mod 2)}{4}$ 194 195 **Hint 3** 196 197 The expression for counting subsequences might be simpler than you think. 198 199 **Solution** 200 201 Think of $\tt{0}$ as $-1$ and $\tt{1}$ as $1$. Let us count the number of subsequences of a binary string which will have the sum of $i$. Let $cnt_0$ and $cnt_1$ as the number of $\tt{0}$ and $\tt{1}$ in the binary string. The number of subsequences is 202 203 ${n} \choose {i + cnt_0}$ 204 205 **Proof** 206 207 We change the perspective on $\tt{0}$ slightly from contributing $-1$ to the sum if chosen and $0$ to the sum if not chosen, to contributing $0$ to the sum if chosen and $1$ to the sum if not chosen. This changes the problem to having $cnt_0 + cnt_1 = n$ distinct objects and needing to pick $i+cnt_0$ of them. 208 209 So the desired sum of the score over all subsequences (see expression of score of a single string in Hint 2) is 210 211 $ \sum_{i = -cnt_0}^{n - cnt_0} {{n} \choose {i + cnt_0}} (\frac{i^2}{4} - \frac{(i \mod 2)}{4}) $ 212 213 At this point, you can throw convolution at the problem by precomputing the answer for $cnt_0 = 0, 1, \ldots, n$ and solve it in $\mathcal{O}(n \log n + q)$. 214 215 Submission: [310298025](/contest/2077/submission/310298025 "Submission 310298025 by omsincoconut") 216 217 Alternatively, you can do more algebra to arrive at a closed-form expression. 218 219 $ 2^{n-4}(n(n+1) - 4cnt_0n + 4cnt_0^2 - 2) $ 220 221 **Proof** 222 223 Consider 224 225 $\sum_{i = -cnt_0}^{n - cnt_0} {{n} \choose {i + cnt_0}} i^2$ 226 227 $= \sum_{i = 0}^{n} {{n} \choose {i}} (i-cnt_0)^2$ 228 229 $= \sum_{i = 0}^{n} {{n} \choose {i}} i^2 - 2cnt_0 \sum_{i = 0}^{n} {{n} \choose {i}} i + cnt_0^2 \sum_{i = 0}^{n} {{n} \choose {i}} 1$ 230 231 $= n(n+1) \cdot 2^{n-2} - 2cnt_0 n \cdot 2^{n-1} + cnt_0^2 \cdot 2^n$ 232 233 And 234 235 $\sum_{i = -cnt_0}^{n - cnt_0} {{n} \choose {i + cnt_0}} (i \mod 2) = 2^{n-1}$ 236 237 So 238 239 $\frac{1}{4} \sum_{i = -cnt_0}^{n - cnt_0} {{n} \choose {i + cnt_0}} i^2 + (i \mod 2)$ 240 241 $= \frac{1}{4} (n(n+1) \cdot 2^{n-2} - 2cnt_0 n \cdot 2^{n-1} + cnt_0^2 \cdot 2^n - 2^{n-1})$ 242 243 $= 2^{n-4}(n(n+1) - 4cnt_0n + 4cnt_0^2 - 2)$ 244 245 Time complexity: $\mathcal{O}(n+q)$ per test case. 246 247 Submission: [310297950](/contest/2077/submission/310297950 "Submission 310297950 by omsincoconut") 248 249 [2077D - Maximum Polygon](/contest/2077/problem/D "Codeforces Round 1008 (Div. 1)") 250 251 **Hint 1** 252 253 Find a way to get the answer if you fixed the largest value or the first value of the subsequence. 254 255 **Hint 2** 256 257 Sufficiently long (which is not that long) arrays will definitely be polygon side lengths. 258 259 **Solution** 260 261 Suppose we consider some integer $x$, and we try to find the lexicographically largest subsequence (say $s$) such that the maximum element of $s$ is $x$. 262 263 We can do it greedily. 264 265 For the subsequence $s$ to be valid, we need to ensure that the sum of the elements of $s$ is greater than $2x$. 266 267 So, our greedy strategy is like we have an empty vector $s$, and we iterate over the array $a$ from left to right, and for each element $a_i$, we do the following: 268 269 If $s$ is not empty and $a_i$ is greater than the last element of $s$, we will check whether we can make the total sum of $s$ greater than $2x$, if we remove the last element of $s$. Now what can be the maximum possible sum of $s$? We can just append all the elements of $a$ which are less than or equal to $x$, and are present to the right of $a_i$ to $s$. 270 271 Append $a_i$ to $s$. 272 273 Thus, we see that the subsequence $s$ is the lexicographically largest subsequence such that the maximum element of $s$ is $x$. 274 275 Now, we have $O(n)$ candidates for the maximum element of $s$. We cannot find the best subsequence for each candidate, as it will be too slow. 276 277 Here comes the key observation. 278 279 Now, what can be the maximum possible size of a sorted vector $v$ such that there does not exist any subsequence of $v$ which can form the sides of a valid polygon? 280 281 We should have $v_i \gt \sum_{j=1}^{i-1} v_j$. 282 283 Now, to get the maximum possible size of $v$, we should have $v_1 = 1$ and $v_i = 2^{i - 2}$ for $i \geq 2$. 284 285 Thus, the maximum possible size of $v$ can be $p = \log_2(10^9) + 2$. 286 287 Our claim is that in the lexicographically largest subsequence $s$, the maximum element should be one of the largest $p + 1$ elements of $a$. 288 289 Suppose we do not have the maximum element of $s$ in the largest $p + 1$ elements of $a$. Let's consider the multiset of the largest $p + 1$ elements of $a$. As we saw above, there should be a subsequence (say $t$) of this multiset which forms the sides of a valid polygon. Now if we insert the elements of $t$ in $s$, we will get a subsequence $s'$ such that $s'$ is valid and $s'$ is lexicographically larger than $s$. 290 291 Thus, we cannot have a subsequence $s$ such that $s$ is the largest possible subsequence and the maximum element of $s$ is not in the largest $p + 1$ elements of $a$. 292 293 Time complexity: $\mathcal{O}(n \log \max(a))$ per test case. 294 295 Submission: [310298095](/contest/2077/submission/310298095 "Submission 310298095 by omsincoconut") 296 297 [2077E - Another Folding Strip](/contest/2077/problem/E "Codeforces Round 1008 (Div. 1)") 298 299 **Hint 1** 300 301 Folding is basically alternating the parity of the indices. 302 303 **Hint 2** 304 305 Maximum subarray sum. 306 307 **Solution** 308 309 As mentioned in Hint 1, we can see that if the darkness of the cells $i_1, i_2, \ldots, i_k$ increases in some operation, the parity of $i_j$ should be different from that of $i_{j+1}$ for $1 \le j \le k - 1$ 310 311 **Diagram** 312 313  314 315 Let us try to find $f(a[1, n])$. 316 317 Consider an array $b$ such that $b_i = (-1)^i a_i$ for all $1 \le i \le n$. 318 319 Let us perform exactly one operation, and say our subsequence of indices is $i_1, i_2, \ldots, i_k$. 320 321 Let $a'$ be the updated array after performing the operation, and $b'_i = (-1)^{i'} a'_i$ for all $1 \le i \le n$. 322 323 Now we can see that 324 325 $ \left| \sum_{i = l}^{r} b'_i - \sum_{i = l}^{r} b_i \right| \le 1, $ 326 327 for all $1 \le l \le r \le n$. 328 329 This is so because for any subarray $b[l, r]$, if $x$ elements at odd indices and $y$ elements at even indices were selected, we should have $|x - y| \le 1$. 330 331 So, we can see that after any operation, the absolute sum of any subarray of $b$ decreases by at most $1$. 332 333 Thus, this gives us a lower bound for the value of $f(a[1, n])$, which is 334 335 $ \max_{1 \le l \le r \le n} \left| \sum_{i = l}^{r} b_i \right|. $ 336 337 Now let us consider the following greedy algorithm for selecting a subsequence $s$ of indices: 338 339 * Start from $i = 1$ and move to the right. 340 * If $b_i$ is zero, we continue. 341 * If $s$ is empty, we append $i$ to $s$, and continue. 342 * If $i$ does not have the same parity as the last element of $s$, we append $i$ to $s$, and continue. 343 * Otherwise, we continue. 344 345 Now suppose $T$ is the set of pairs of indices $(l, r)$ such that $b_l$ and $b_r$ are nonzero and 346 347 $ \left| \sum_{i = l}^{r} b_i \right| $ 348 349 is maximized. 350 351 We can prove that the absolute sum of all subarrays in $T$ would be reduced by $1$ after performing the operation. 352 353 We can notice that if $(l, r) \in T$, then $l$ and $r$ should have the same parity. Otherwise, 354 355 $ \max \left( \left| b[l + 1, r] \right|, \left| b[l, r - 1] \right| \right) \gt \left| b[l, r] \right|. $ 356 357 Next, we claim that $l$ should be in $s$. 358 359 Suppose $l$ is not in $s$. This means that there should be an index $k$ in $s$ such that $k$ has the same parity as $l$ and there are no nonzero elements between $k$ and $l$ that have a parity different from $l$. 360 361 Now if that is the case, then $b[k, r]$ would have a greater absolute sum than $b[l, r]$. 362 363 Thus, we conclude that $l$ will always be in $s$. 364 365 Now let $d$ be the largest index in $s$ smaller than or equal to $r$. 366 367 First of all, we should have $d \ge l$. 368 369 Now $d$ should have the same parity as $r$. 370 371 This is so because if that is not the case, we should have $d \lt r$ and we would have selected $r$ or any other element having the same parity as $r$ after $d$ in $s$. 372 373 Thus, we can see that for all the pairs $(l, r) \in T$, we should have $l$ in $s$ and the largest element smaller than or equal to $r$ in $s$ should have the same parity as that of $r$. This implies that the absolute sum of all subarrays in $T$ would be reduced by $1$ after performing the operation. 374 375 This is because if $l$ is odd, we would have added $1, -1, 1, -1, \ldots, 1$ to the subarray $b[l, r]$, increasing the subarray sum of $b[l, r]$ by $1$. 376 377 And if $l$ is even, we would have added $-1, 1, -1, 1, \ldots, -1$ to the subarray $b[l, r]$, decreasing the subarray sum of $b[l, r]$ by $1$. 378 379 Now we can see that the greedy algorithm would achieve the lower bound. 380 381 So, the answer for the array $a$ is the maximum absolute sum over all subarrays of $b$. 382 383 Let us consider an array $c$ such that 384 385 $ c_i = c_{i - 1} + b_i, \quad \text{with } c_0 = 0. $ 386 387 We can further notice that the maximum absolute sum over all subarrays of $b$ is equal to 388 389 $ \max_{1 \le i \le n} c_i - \min_{1 \le i \le n} c_i. $ 390 391 Now we can see that 392 393 $ f(a[l, r]) = \max_{l \le i \le r} c_i - \min_{l \le i \le r} c_i. $ 394 395 Thus, 396 397 $ \sum_{l = 1}^{n} \sum_{r = l}^{n} f(a[l, r]) = \sum_{l = 1}^{n} \sum_{r = l}^{n} \max_{l \le i \le r} c_i - \min_{l \le i \le r} c_i. $ 398 399 So, 400 401 $ \sum_{l = 1}^{n} \sum_{r = l}^{n} f(a[l, r]) = \sum_{l = 1}^{n} \sum_{r = l}^{n} \max_{l \le i \le r} c_i - \sum_{l = 1}^{n} \sum_{r = l}^{n} \min_{l \le i \le r} c_i. $ 402 403 Finding the value of 404 405 $ \sum_{l = 1}^{n} \sum_{r = l}^{n} \max_{l \le i \le r} c_i $ 406 407 is a fairly standard exercise, which can be done using a stack in $O(n)$ time. 408 409 Submission: [310317161](/contest/2077/submission/310317161 "Submission 310317161 by satyam343") 410 411 [2077F - AND x OR](/contest/2077/problem/F "Codeforces Round 1008 (Div. 1)") 412 413 **Hint 1** 414 415 Characterize the property of a good pair of arrays. 416 417 **Hint 2** 418 419 Think about the last operation that turns a good pair of arrays into the same array. 420 421 **Solution** 422 423 $(a, b)$ is a good pair only if at least one of these two conditions hold 424 425 * $a = b$ 426 * There exist two distinct indices $i$, $j$ such that $b_i$ is a submask of $b_j$. 427 428 **Proof** 429 430 If $a \neq b$, then you need to do at least one operation to $a$. In the last operation, if you choose $i$, $j$, $x$, then $a_i$ is a submask of $x$ and $x$ is a submask of $a_j$. So in the final array, there must be at least one pair of submask and supermask. 431 432 Next, we will show that this is sufficient. For every index $k$ other than $i$ and $j$, you can do this. 433 434 * Perform operation with $k$, $i$, $0$ 435 * Perform operation with $i$, $k$, $b_k$ 436 437 Then 438 439 * Perform operation with $i$, $j$, $0$ 440 * Perform operation with $j$, $i$, $0$ 441 * Perform operation with $j$, $i$, $b_i$ 442 * Perform operation with $i$, $j$, $b_j$ 443 444 We need to check the two cases. 445 446 In the first case, the minimum cost will be $\sum_{i=1}^n |a_i - b_i|$. 447 448 In the second case, we want the minimum cost to create a submask-supermask pair in $b$. 449 450 **Solution 1** 451 452 For explanation simplicity, consider the graph $G$ with $2m$ vertices, representing the numbers from $1$ to $2m$. In this graph, there's an unweighted edge from vertex $i$ to vertex $i+1$, and from vertex $i$ to all submask vertices. Color all vertices in which its value appears in $b$. The answer is the shortest path between all pairs of distinct colored vertices. 453 454 The implementation itself (see below) uses dynamic programming consisting of three phases. The dynamic programming tracks the first and second closest vertex to each vertex, because the first closest vertex would be itself. 455 456 * Propagate each colored vertices up (from $i$ to $i+1$). 457 * Propagate to the submasks (from $i$ to its submasks). 458 * Propagate down (from $i$ to $i-1$). 459 460 Time complexity: $\mathcal{O}(n \log n + m \log m)$ per test case. The $\log n$ factor is from the implementation which checks for duplicates in $b$ by sorting. 461 462 Submission: [310298215](/contest/2077/submission/310298215 "Submission 310298215 by omsincoconut") 463 464 **Solution 2** 465 466 Submission: [310317931](/contest/2077/submission/310317931 "Submission 310317931 by satyam343") 467 468 [2077G - RGB Walking](/contest/2077/problem/G "Codeforces Round 1008 (Div. 1)") 469 470 **Hint 1** 471 472 It might help to solve this task with two colors first. As in, minimize the difference between red and blue. 473 474 **Hint 1.1** 475 476 Walking back and forth can do wonders. 477 478 **Solution for this** 479 480 Let the difference between the red edges and the blue edges passed be $d$. 481 482 Let the edge weights of the red edges be $r_1, r_2, \ldots$ and the blue edges be $b_1, b_2, \ldots$. 483 484 Let $c = gcd(r_1, r_2, \ldots, b_1, b_2, \ldots)$ and $C = lcm(r_1, r_2, \ldots, b_1, b_2, \ldots)$. 485 486 We can find a walk with $d=0$ which passes every edge and returns to vertex $1$. 487 488 **Proof** 489 490 For each edge, walk to one of its endpoint, walk that edge, and then walk back to vertex $1$ using the same walk. This way, we passed through every edge an even number of times. 491 492 We will now walk back and forth using the edges we passed. This way, we can add to $d$ by some linear combination of $2r_1, 2r_2, \ldots, 2b_1, 2b_2, \ldots$. Because $d$ is divisible by $2c$, we can add to it such that $d=0$ by Bézout's identity. 493 494 Note: About the "can add by some linear combination", there's the slight caveat that we can only add the red and subtract the blue. We can subtract the red (or similarly, add the blue) by first subtracting from blue by $2C$, then add back red just so that it is deficit by the edge weight. 495 496 After passing every edge and returning to vertex $1$ with $d=0$, we can walk from vertex $1$ to vertex $n$. If the walk have $d$ divisible by $2c$, then the answer is $0$ and $c$ otherwise. The proof of this is similar to the proof above. 497 498 To check if a walk with $d$ divisible by $2c$ exist or not, create a state graph where each vertex is either "reach the vertex with $d$ divisible by $2c$" and "$d$ not divisible by $2c$". 499 500 **Hint 2** 501 502 In the two-color version (in Hint 1), we created a state graph on the parity. Can a similar idea be used? 503 504 **Hint 3** 505 506 Think about each color separately first. 507 508 **Solution** 509 510 Let 511 512 * the edge weights of the red edges be $r_1, r_2, \ldots$, the green edges be $g_1, g_2, \ldots$ and the blue edges be $b_1, b_2, \ldots$. 513 * $\gcd(r_1, r_2, \ldots)$, $\gcd(g_1, g_2, \ldots)$ and $\gcd(b_1, b_2, \ldots)$ be $c_r, c_g, c_b$. 514 * the sum of weights of red, green and blue edges traversed be $d_r, d_g, d_b$. 515 516 Define $ \lt d_{r_1}, d_{g_1}, d_{b_1} \gt = \lt d_{r_2}, d_{g_2}, d_{b_2} \gt $ only if $d_{r_1}-d_{g_1} = d_{r_2}-d_{g_2}$, $d_{r_1}-d_{b_1} = d_{r_2}-d_{b_2}$ and $d_{g_1}-d_{b_1} = d_{g_2}-d_{b_2}$. 517 518 In a similar manner to hint 1, there's a walk that passes through every edge and have $ \lt d_r, d_g, d_b \gt = \lt 0, 0, 0 \gt $. Furthermore, if we have $ \lt d_r, d_g, d_b \gt $, then we can have $ \lt d_r + 2g_r, d_g, d_b \gt $ and $ \lt d_r - 2g_r, d_g, d_b \gt $. The analogous statement holds for the other two colors. 519 520 Consequently, from any reachable $ \lt d_r, d_g, d_b \gt $, we can have $ \lt s_r, s_g, s_b \gt $, where $s_r$ is either $0$ or $c_r$ depending on whether $d_r \equiv 0$ ($\mod 2c_r$) or $d_r \equiv c_r$ ($\mod 2c_r$). The idea holds similarly for the other two colors. This invites us to look at each vertex as $8$ possible states, corresponding to $3$ binary options of each color. 521 522 We simply need to solve the answer for each reachable state then take the minimum. Each state corresponds to the following system of linear congruences. 523 524 $ d_r \equiv s_r (\mod 2c_r) $ $ d_g \equiv s_g (\mod 2c_g) $ $ d_b \equiv s_b (\mod 2c_b) $ 525 526 We aim to minimize $\max(d_r, d_g, d_b) - \min(d_r, d_g, d_b)$ over all triplets which satisfy the conditions. 527 528 To do so, we will fix one of them, which we'll suppose is $d_r$, as the minimum. 529 530 Denote $f_g(p)$ and $f_b(p)$ as the minimum possible $d_g - (d_r + 2pc_r)$ and $r_b - (d_r + 2pc_r)$ where $r_g, r_p \geq d_r + 2pc_r$. 531 532 We want to find 533 534 $ \min_{k \in \mathbb{Z}} \max(f_g(k), f_b(k)) $ 535 536 Observe that $f_g(k + c_g) = f_g(p)$ and $fb(k + c_b) = f_b(p)$. By the Chinese remainder theorem, the expression above reduces to 537 538 $ \min_{0 \leq k \lt \gcd(c_g, c_b)} \max(\min_{(k_g \mod \gcd(c_g, c_b) = k)} f_g(k_g), \min_{(k_b \mod \gcd(c_g, c_b) = k)} f_b(k_b)) $ 539 540 Which can be evaluated in $\mathcal{O}(x)$. 541 542 Time complexity: $\mathcal{O}(n \log x + x)$ per test case. The logarithmic factor is from gcd computations. 543 544 Submission: [310298269](/contest/2077/submission/310298269 "Submission 310298269 by omsincoconut") 545 546 **Some ending notes** 547 548 **Rating predictions** 549 550  551 552 **A small (?) story of this contest.** 553 554 This contest was originally proposed as a Div. 2 only. It was changed to Div. 1 + Div. 2 because we found task 1G, which was originally proposed with only two colors as 2D. 555 556 The contest itself retained little of the original proposal, and most of the tasks were once proposed for a lower position. 557 558 * 2B was proposed as 2A. 559 * 1A/2C was proposed as 2A. 560 * 2D was proposed as 2B. The base story is credited to my friend Punpun. 561 * 1B/2E was proposed as 2C. 562 * 1C/2F was proposed as 2E with $n \leq 5000$. The testers found the solutions for the current version. 563 * 1D was originally made for permutation arrays only. Credit to [satyam343](/profile/satyam343 "Expert satyam343") for making the task. 564 * 1E/2G was proposed as 2D with binary arrays. The testers found the solutions for the current version. The idea of folding and dropping color is credited to my friend Punpun. 565 * 1F was proposed in a much easier form as 2B. It was buffed by [satyam343](/profile/satyam343 "Expert satyam343"). 566 567 **Original formulation** 568 569 Given arrays $a$, $b$ both of length $n$, perform the following operation no more than $2n$ times such that $a_i \neq b_i$ holds for at most $2$ values of $i$. The operation is the same one which is used to define a good pair of arrays. 570 571 * 1G was proposed as 2D with two colors. Solving this easier version can hint the full solution. 572 573 **About Arcaea and the soundtracks** 574 575 Arcaea is a good rhythm game with good mechanics, music, and story. In some tasks, I put music from Arcaea in it because I want to.