2155.md (21391B)
1 Source: https://codeforces.com/blog/entry/147174 2 3 Hello, Codeforces! 4 5 Sorry for the late editorial. Our national olympiad just finished and we were sorting everything out. 6 7 We also apologize for weak tests on D that made an incorrect solution pass. Many testers submitted the same solution and we mistakenly thought that it was correct given the low bound on the number of batteries. Still, we hope that the contest was a fun and valuable experience for all contestants. 8 9 The editorial was prepared by [efishel](/profile/efishel "Мастер efishel") and me. If you have any questions about the problems or the solutions, please ask in the comments. 10 11 ### [2155A - Эль фучо](/contest/2155/problem/A "Codeforces Round 1056 (Div. 2)") 12 13 **Hint 1** 14 15 When two teams in the same group face off against each other, exactly one of them stays in the group. 16 17 **Solution 1** 18 19 The answer for all $n$ is $2n-2$. 20 21 Let's consider the winners' group first. Note that exactly one team drops to the losers' bracket for every match in this group. Only one team is left in the winners' group right before the end, so $n-1$ matches must have been played in the winners' group right before the final match. 22 23 Similar logic applies to the losers' group. $n-1$ teams in total drop down to the losers' group over the course of the tournament. For every match played between two teams in this group, exactly one team is eliminated from the tournament. A single team in left in this group right before the final match, so $n-2$ matches must have been played in the losers' group right before the final match. 24 25 Finally, we add the final match to our calculation, bringing the total to 26 27 $(n-1)+(n-2)+1 = 2n-2$ 28 29 **Code (C++)** 30 31 ``` 32 #include <bits/stdc++.h> 33 34 using namespace std; 35 36 int main() { 37 38 int n, t; 39 40 cin >> t; 41 42 while(t--) { 43 44 cin >> n; 45 46 cout << 2*n-2 << "\n"; 47 48 } 49 50 } 51 ``` 52 53 **Solution 2** 54 55 Alternatively, we can simulate the process directly. 56 57 Suppose there are $a$ teams in the winners' group and $b$ teams in the losers' group right before a round. 58 59 First, $\left \lfloor \frac{b}{2} \right \rfloor$ matches are played among the teams in the losers' group, so $\left \lfloor \frac{b}{2} \right \rfloor$ are eliminated in this step. We subtract this number from $b$ and add $\left \lfloor \frac{b}{2} \right \rfloor$ to the total number of matches played. 60 61 Then, $\left \lfloor \frac{a}{2} \right \rfloor$ matches are played among the teams in the winners' group, so $\left \lfloor \frac{a}{2} \right \rfloor$ of them drop down to the losers' group. We subtract this number from $b$ and add $\left \lfloor \frac{b}{2} \right \rfloor$ to the total number of matches played. 62 63 After simulating $\mathcal{O}(\log (n))$ rounds as described above, both brackets are left with a single team, so we add $1$ to our total. 64 65 Time complexity: $\mathcal{O}(\log (n))$ 66 67 **Code (C++)** 68 69 ``` 70 #include <bits/stdc++.h> 71 72 using namespace std; 73 74 int main() { 75 76 int n, t, winners, losers, ans; 77 78 cin >> t; 79 80 while(t--) { 81 cin >> n; 82 winners = n; 83 losers = 0; 84 ans = 0; 85 86 while(max(losers, winners) > 1) { 87 ans += losers/2; 88 losers = (losers+1)/2; 89 90 ans += winners/2; 91 losers += winners/2; 92 winners++; 93 winners /= 2; 94 } 95 96 ans++; 97 98 cout << ans << "\n"; 99 } 100 } 101 ``` 102 103 ### [2155B - Великий побег Авраама](/contest/2155/problem/B "Codeforces Round 1056 (Div. 2)") 104 105 **Hint 1** 106 107 There is exactly one value of $k$ that doesn't work 108 109 **Hint 2** 110 111 Two arrows facing each other trap Abraham forever. 112 113 **Solution** 114 115 We claim that the only value of $k$ for which the answer is $\texttt{NO}$ is $k = n*n-1$. 116 117 If $k = n^2-1$ were possible, Abraham should be trapped forever from exactly $n^2-(n^2-1) = 1$ starting cell, but the arrow in that cell would necessarily point towards the outside of the grid, or in the direction of another cell from which Abraham will eventually escape, so this situation is impossible and we should print $\texttt{NO}$. 118 119 All other values of $k$ are achievable with the following construction: 120 121 1. Fill up rows of the grid with $\texttt{U}$ from left to right and from top to bottom. You should place $k$ of this letter in total. 122 2. Fill every cell that doesn't have a $\texttt{U}$ already and isn't in the last row with a $\texttt{D}$. (These cells might be non-existent) 123 3. Fill the leftmost unoccupied cell in the last row with an $R$ and all the cells to its right with an $L$. (Note that at least one $L$ is placed). 124 125 This works because, if Abraham steps on a $\texttt{U}$, he will be pushed onto another $\texttt{U}$, and so on until he leaves the board. 126 127 On the other hand, if he steps on a $\texttt{D}$, he will be carried along all the way to an $\texttt{R}$ or $\texttt{L}$ in the last row. It's easy to see that these directions necessarily trap Abraham. 128 129 Time complexity: $\mathcal{O}(n^2)$ 130 131 **Code (Python)** 132 133 ``` 134 t = int(input()) 135 136 for q in range(t): 137 n, k = (int(x) for x in input().split()) 138 139 if(k == n*n-1): 140 print("NO") 141 else: 142 print("YES") 143 for i in range(n): 144 145 s = "" 146 for j in range(n): 147 if(k > 0): 148 s += "U" 149 k -= 1 150 elif(i == n-1 and j == n-1): 151 s += "L" 152 elif(i == n-1): 153 s += "R" 154 else: 155 s += "D" 156 157 print(s) 158 ``` 159 160 ### [2155C - Плащи древних волшебников](/contest/2155/problem/C "Codeforces Round 1056 (Div. 2)") 161 162 **Hint 1** 163 164 What's the maximum value that $|a_{i+1} - a_i|$ can attain for any $i$? 165 166 **Hint 2** 167 168 Bound the number of possible cape arrangements 169 170 **Solution** 171 172 Suppose that Harry's list corresponds to at least one arrangement of capes. The main claim is that any two consecutive values in his list differ by at most $1$. 173 174 Note that when Harry walks from position $i$ to position $i+1$, the visibility of wizard $1$ to $i-1$ and $i+2$ to $n$ is unaffected, so there are four possible situations regarding the other $2$ wizards: 175 176 * Wizards $i$ and $i+1$ wear their capes to their left. Wizard $i+1$ becomes visible and wizard $i$ can still be seen from position $i+1$, so $a_{i+1}-a_i = 1$ 177 * Wizards $i$ and $i+1$ wear their capes to their right. Wizard $i+1$ remains visible while wizard $i$ becomes invisible from position $i+1$, so $a_{i+1}-a_i = -1$ 178 * Wizard $i$ wears his cape to his left while wizard $i+1$ wears his cape to his right. Both wizards are still visible from position $i+1$, so $a_{i+1}-a_i = 0$ 179 * Wizard $i$ wears his cape to his left while wizard $i+1$ wears his cape to his right. Wizard $i+1$ becomes visible, but wizard $i$ becomes invisible when moving to position $i+1$, so $a_{i+1}-a_i = 0$ 180 181 In summary, if both wizards wear their capes the same way, the difference between the corresponding entries in Harry's list is $1$. Else, it is $0$. Note that this determines a unique possibility (it might be invalid) for the entire cape arrangement based on how wizard $1$ is wearing his cape only if $|a_{i+1}-a_i| \lt 2$ for all $1 \le i \lt n$. 182 183 Thus, there are at most two possible arrangements for the wizards' capes. We can construct both of them and check whether they are consistent with Harry's list. 184 185 Time complexity: $\mathcal{O}(n)$ 186 187 **Code (Python)** 188 189 ``` 190 def validar(x, n, a): 191 flag = False 192 visibles = 1 193 194 for i in range(2, n+1): 195 if(x[i] == 1): 196 visibles += 1 197 198 if(visibles == a[1]): 199 flag = True 200 201 for i in range(1, n): 202 if(x[i] == 1 and x[i+1] == 1): 203 visibles -= 1 204 elif(x[i] == 0 and x[i+1] == 0): 205 visibles += 1 206 207 if(a[i+1] != visibles): 208 flag = False 209 break 210 211 return flag 212 213 t = int(input()) 214 215 for i in range(t): 216 sol1 = [] 217 sol2 = [] 218 sol1.append(0) 219 sol2.append(0) 220 sol1.append(0) 221 sol2.append(1) 222 flag = True 223 cont = 0 224 225 n = int(input()) 226 arr = [] 227 arr.append(0) 228 arr.extend(map(int, input().split())) 229 230 for j in range(1, n): 231 if(arr[j+1]-arr[j] > 1): 232 flag = False 233 break 234 235 if(arr[j+1]-arr[j] == 0): 236 sol1.append(1-sol1[j]) 237 sol2.append(1-sol2[j]) 238 else: 239 sol1.append(sol1[j]) 240 sol2.append(sol2[j]) 241 242 if(not flag): 243 print(0) 244 continue 245 246 if(validar(sol1, n, arr)): 247 cont += 1 248 249 if(validar(sol2, n, arr)): 250 cont += 1 251 252 print(cont) 253 ``` 254 255 ### [2155D - Батарейки](/contest/2155/problem/D "Codeforces Round 1056 (Div. 2)") 256 257 **Hint 1** 258 259 Place the batteries in order on a circumference. 260 261 **Hint 2** 262 263 If there are $a$ working batteries, can we bound the distance between some pair of them in terms of $n$ and $a$? 264 265 **Solution** 266 267 Arrange the batteries in clockwise order on a circumference such that the arc length between any two consecutive batteries is $1$, and let the indices of the working batteries be $1 \le b_1 \lt b_2 \lt \dots \lt b_a \le n$. 268 269 Let the distance between two working batteries $b_i$ and $b_{i+1}$ be $b_j-b_i$ if $i \lt a$ and $b_1+n-b_a$ if $i = a$. Note that this matches the length of a circle arc between $b_i$ and $b_{i+1}$ that doesn't contain any other working battery. 270 271 Observe that the sum of the distances between $b_i$ and $b_{i+1}$ for $1 \le i \le a$ (indices taken $\bmod a$) is exactly $n$, since the corresponding circle arcs make up the entire circumference. Since there are $a$ pairs of working batteries, by Pigeonhole Principle there is some distance that is less than or equal to $\left \lfloor \frac{n}{a} \right \rfloor$ 272 273 Consequently, the following strategy works: For every $i$ from $1$ to $\left \lfloor \frac{n}{a} \right \rfloor$, and for every $j$ from $1$ to $n$, query batteries $j$ and $j+i \bmod n$ (if $j+i = 0$, query with battery $n$) which is equivalent to querying battery $j$ and the one $i$ positions ahead clockwise. 274 275 The above takes at most 276 277 $n \times \left \lfloor \frac{n}{a} \right \rfloor \le \left \lfloor \frac{n^2}{a} \right \rfloor$ 278 279 trials, as desired. 280 281 **Code** 282 283 ``` 284 #include <bits/stdc++.h> 285 286 using namespace std; 287 288 void main_() { 289 290 int n, x; 291 cin >> n; 292 293 for (int i = 1; i < n; i++) 294 for (int j = 1; j <= n; j++) { 295 296 x = (i+j)%n; 297 298 if(x == 0) { 299 x = n; 300 } 301 302 cout << j << " " << x << endl; 303 304 int res; 305 cin >> res; 306 307 if (res) { 308 return; 309 } 310 } 311 } 312 313 int main() { 314 315 int t = 1; 316 cin >> t; 317 while (t--) 318 main_(); 319 320 return 0; 321 } 322 ``` 323 324 ### [2155E - Мимо и Юю](/contest/2155/problem/E "Codeforces Round 1056 (Div. 2)") 325 326 **Hint 1** 327 328 When $n = 1$, the total number of turns is fixed. 329 330 **Hint 2** 331 332 When $n = 2$, the winning and losing states depend only on the parity of the amount of tokens in each column. 333 334 **Solution** 335 336 For convenience, let's denote with $d_i$ the number of tokens located in column $i$. 337 338 It's worth noting that the game lasts a finite amount of turns because, the array $[ d_m, d_{m-1}, \dots d_1 ]$ becomes lexicographically smaller (strictly) after each turn. 339 340 Note that we can think of each token independently, as tokens are only removed one at a time by the players. 341 342 We first deal with the case $n = 1$. Let $c_i$ be the column where token $i$ is located. We will prove by induction that token $i$ contributes $2^{c_i-2}$ turns to the game whenever $c_i \ge 2$. That is, $2^{c_i-2}$ turns are necessary and sufficient to remove token $i$ and all the tokens it spawns from the board. 343 344 Base case $c_i = 2$: A player moves token $i$ to column $1$. No tokens are added to the board, so $1 = 2^0$ turns are played in total. 345 346 Otherwise, $c_i-2$ tokens will be added to the board after choosing token $i$, one in each of columns $2, 3, \dots {c_i-1}$. By the induction hypothesis, removing these tokens and all the tokens they spawn will take 347 348 $ \sum_{j=2}^{c_i-1} 2^{j-2} = 2^0+2^1+\dots+2^{i-3} = 2^{c_i-2}-1$ 349 350 turns. Adding the initial turn to the total, we get $2^{c_i-2}-1+1 = 2^{c_i-2}$ turns in total. 351 352 The answer is equivalent to the parity of the number of turns performed in total, obtained by summing the contribution of turns by each token. Only tokens in column $2$ contribute an odd amount of turns ($2^0 = 1$ turn) while every other token contributes an even amount of turns ($0$ or $2^{j-2}$ turns), so we just need to print $\texttt{Mimo}$ if there is an odd number of tokens on column $2$ or $\texttt{Yuyu}$ if there is an even amount. 353 354 The only other case is when $n \ge 2$. We claim that the second player wins if and only if, for all $i \ge 2$, 355 356 $d_i \equiv 0 \; \bmod 2$ 357 358 * If $d_i = 0$ for all $i \ge 2$: The game is automatically a losing state. 359 * $d_i \equiv 0 \; \bmod 2$ for all $i \ge 2$ turns out to also be a losing state. Any move would cause some $d_j$ (in particular, $j = b_1$) to go from even to odd; thus, the opponent is given a winning game, as we will prove below. 360 361 We claim that $d_j \equiv 1 \; \bmod 2$ for some $j \ge 2$ is a winning state. Denote the maximum of all such $j$ as $j_{max}$. Our objective will be to give the opponent a game which falls under the first or second bullet point ($d_i \equiv 0 \; \bmod 2$ for all $i \ge 2$). If such a thing is always possible, after a finite amount of moves, the state given to the opponent will necessarily be exactly that of the first bullet point (the "minimal" losing state), proving these states are winning. 362 363 By definition of $j_{max}$, $d_i \equiv 0 \; \bmod 2$ for all ($i \gt j_{max}$). Performing a turn with chosen token $c$ in column $j_{max}$ causes $d_{j_{max}}$ to become $0 \bmod 2$. For all columns $i$ ($i \lt j_{max}$) a move that achieves $d_i \equiv 0 \; \bmod 2$ is as follows: 364 365 * If $d_i \equiv 0 \; \bmod 2$: Make sure $2$ tokens are added to column $i$. 366 * If $d_i \equiv 1 \; \bmod 2$: Make sure $1$ token is added to column $i$. 367 368 Such a move is possible because $n \ge 2$. This is an example of how it could look like: 369 370  371 372 Time complexity: $\mathcal{O}(k)$ or $\mathcal{O}(k\log m)$ depending on implementation. 373 374 **Code** 375 376 ``` 377 #include <bits/stdc++.h> 378 using namespace std; 379 using ll = long long; 380 using vll = vector <ll>; 381 382 void tc () { 383 ll n, m, k; 384 cin >> n >> m >> k; 385 set <ll> st; 386 for (ll id = 0; id < k; id++) { 387 ll i, j; 388 cin >> i >> j; 389 if (j == 1) continue; 390 if (n == 1 && j != 2) continue; 391 if (st.count(j)) 392 st.erase(j); 393 else 394 st.insert(j); 395 } 396 cout << (st.size() > 0 ? "Mimo" : "Yuyu") << '\n'; 397 } 398 399 int main () { 400 cin.tie(nullptr) -> sync_with_stdio(false); 401 ll T; cin >> T; while (T--) { tc(); } 402 return 0; 403 } 404 ``` 405 406 ### [2155F - Цветное дерево Хуана](/contest/2155/problem/F "Codeforces Round 1056 (Div. 2)") 407 408 **Hint 1** 409 410 Consider the graph formed by the vertices with color $x$ and the edges between them. What happens if a query contains two vertices in the one of this graph's connected components ("color components")? 411 412 **Hint 2** 413 414 After assigning IDs to each "color component" (for all colors), we can calculate the answer for two vertices by counting the number of components which contain both of them. 415 416 **Hint 3** 417 418 We can precompute the answer for all possible queries containing vertex $x$ with DFS. 419 420 **Hint 4** 421 422 Determining all answers with only one of the two aforementioned methods is very expensive. Is there some way to balance the complexity by using one over the other in certain situations? 423 424 **Solution** 425 426 There are some solutions with square-root complexity with an additional log factor that can pass if optimized enough, but we will present an $\mathcal{O}((n+q+s)\sqrt s)$ solution. 427 428 Let's first transform the problem from calculating the intersection of $C_w$ for all nodes $w$ in the path from $a_i$ to $b_i$ ($\left| C_{a_i} \cap \dots \cap C_{b_i} \right|$) to calculating the intersection of 2 sets: $D_{a_i}$ and $D_{b_i}$. We will calculate $\left|D_{a_i} \cap D_{b_i}\right|$ in average square-root complexity, using the best of 2 algorithms for each type of query. 429 430 First, let's define the sets $D_1, D_2, \dots D_n$. Let a *maximal color component* be a set of vertices, all of which contain some color $x$ in their sets, such that there is no other vertex with color $x$ adjacent to some vertex of the maximal component. We will assign an arbitrary ID to each maximal color component, and $D_u$ will contain the IDs of the maximal color components which node $u$ belongs to. 431 432 Note that $\left| D_u \right| = \left| C_u \right|$. Also note that the answer now is simply $\left|D_{a_i} \cap D_{b_i}\right|$. A possible $\mathcal{O}\left(n+s+k\right)$ algorithm calculating the sets $D_i$ is to maintain $k$ stacks while doing a DFS where, when visiting node $u$, stack $c$ contains the ancestors of node $u$ with color $c$. Checking the top of the stack suffices to know if a new component is created, or inherited from one's parent. 433 434 Here are 2 algorithms which calculate the cardinality of the intersection: One answers a query for a given pair of nodes $a_i$, $b_i$ and runs in $\mathcal{O}\left( |D_{a_i}|+|D_{b_i}| \right)$. The other calculates the answer between a fixed node $u$ and all $n$ nodes in $\mathcal{O}\left( n+s \right)$. 435 436 The first algorithm relies on sorting the sets $D_u$ (stored in lists or arrays), and then using the two-pointers technique to calculate the intersection of two sorted arrays in linear time. The second algorithm roots the tree in $u$ and starts a DFS, where the frequency of all $k$ colors across ancestors is maintained. For every node $v$, it calculates if the frequency of every color in $C_v$ is equal to its depth. 437 438 Let $B$ be a fixed integer. We precompute answers when $|D_u| \ge B$ using the $\mathcal{O}\left( n+s \right)$ algorithm. Otherwise, we use the $\mathcal{O}\left( |D_{a_i}|+|D_{b_i}| \right)$ algorithm for queries in which $|D_{a_i}|, |D_{b_i}| \le B$. The complexity of this approach is $\mathcal{O}\left( qB + (s/B)(n+s) \right)$ because there are at most $s/B$ vertices whose sets have a cardinality greater than $B$. Setting $B$ to be around $\sqrt s$, we get that our procedure runs in $\mathcal{O}\left(q\sqrt s + \sqrt s (n+s) \right) = \mathcal{O}\left( (n+q+s)\sqrt s \right)$. 439 440 Time complexity: $\mathcal{O}\left( (n+q+s)\sqrt s \right)$ 441 442 Memory complexity: $\mathcal{O}\left( s + n\sqrt s \right)$ 443 444 **Code** 445 446 ``` 447 #include <bits/stdc++.h> 448 using namespace std; 449 using ll = long long; 450 using vll = vector <ll>; 451 452 const ll MAXN = 3E5+16, B = 800; 453 vll adj[MAXN]; 454 vll cols[MAXN], comps[MAXN]; 455 ll comp_col[MAXN]; 456 ll timer = 1, cur = 1; 457 ll last[MAXN]; 458 bool active[MAXN]; 459 ll curMap[MAXN]; 460 int preProc[MAXN/B+16][MAXN]; 461 462 void dfs1 (ll u, ll par) { 463 vll th(cols[u].size()), th2(cols[u].size()); 464 comps[u].resize(cols[u].size()); 465 for (ll i = 0; i < cols[u].size(); i++) { 466 ll c = cols[u][i]; 467 th[i] = last[c]; 468 th2[i] = comp_col[c]; 469 comp_col[c] = (last[c] == par ? comp_col[c] : timer++); 470 comps[u][i] = comp_col[c]; 471 last[c] = u; 472 } 473 for (ll v : adj[u]) { 474 if (v == par) continue; 475 dfs1(v, u); 476 } 477 for (ll i = 0; i < cols[u].size(); i++) { 478 ll c = cols[u][i]; 479 last[c] = th[i]; 480 comp_col[c] = th2[i]; 481 } 482 } 483 484 void tc () { 485 ll n, k, s, q; 486 cin >> n >> k >> s >> q; 487 fill(adj, adj+n, vll({})); 488 for (ll i = 1; i < n; i++) { 489 ll u, v; 490 cin >> u >> v; 491 u--; v--; 492 adj[u].push_back(v); 493 adj[v].push_back(u); 494 } 495 timer = 1; 496 cur = 1; 497 fill(cols, cols+n, vll({})); 498 fill(comps, comps+n, vll({})); 499 fill(comp_col, comp_col+k, -16); 500 fill(last, last+k, -16); 501 for (ll i = 0; i < s; i++) { 502 ll x, c; 503 cin >> x >> c; 504 x--; c--; 505 cols[x].push_back(c); 506 } 507 dfs1(0, 0); 508 for (ll u = 0; u < n; u++) { 509 sort(comps[u].begin(), comps[u].end()); 510 } 511 for (ll u = 0; u < n; u++) { 512 if (cols[u].size() < B) continue; 513 // >= B 514 for (ll c : comps[u]) active[c] = true; 515 for (ll v = 0; v < n; v++) { 516 preProc[cur][v] = 0; 517 for (ll c : comps[v]) { 518 preProc[cur][v] += active[c]; 519 } 520 } 521 for (ll c : comps[u]) active[c] = false; 522 curMap[u] = cur++; 523 } 524 while (q--) { 525 ll u, v; 526 cin >> u >> v; 527 u--; v--; 528 if (cols[u].size() >= B) { 529 cout << preProc[curMap[u]][v] << ' '; 530 continue; 531 } 532 if (cols[v].size() >= B) { 533 cout << preProc[curMap[v]][u] << ' '; 534 continue; 535 } 536 ll ans = 0; 537 ll p1 = 0; 538 for (ll p2 = 0; p2 < comps[v].size(); p2++) { 539 while (p1 < comps[u].size() && comps[u][p1] < comps[v][p2]) p1++; 540 if (p1 == comps[u].size() || comps[u][p1] != comps[v][p2]) continue; 541 ans++; 542 } 543 cout << ans << ' '; 544 } 545 cout << '\n'; 546 } 547 548 int main () { 549 cin.tie(nullptr) -> sync_with_stdio(false); 550 ll T; cin >> T; while (T--) { tc(); } 551 return 0; 552 } 553 ```