2071.md (28726B)
1 Source: https://codeforces.com/blog/entry/140115 2 3 We hope you enjoyed the problems! Thank you for participating in the contest! We would love to hear your feedback in the comments. 4 5 **How did you find the contest?** 6 7 * Great: 8 * Good: 9 * Average: 10 * Bad: 11 * Trash: 12 13 **Which problem was your favorite?** 14 15 * A: 16 * B: 17 * C: 18 * D1: 19 * D2: 20 * E: 21 * F: 22 23 **Which problem did you find the least enjoyable?** 24 25 * A: 26 * B: 27 * C: 28 * D1: 29 * D2: 30 * E: 31 * F: 32 33 [2071A - The Play Never Ends](/contest/2071/problem/A "Codeforces Round 1007 (Div. 2)") 34 35 **Hints** 36 37 **Hint 1** 38 39 When Fofo is the spectator of the first match, what is the earliest subsequent game in which he will spectate again? 40 41 **Hint 2** 42 43 Suppose Sosai wins the first game. What becomes clear? 44 45 **Solution** 46 47 Once the winner of the first match is decided, the rest of the game is completely predictable. 48 49 For example, if Hohai wins the first match which Fofo spectated, we can see that: 50 51 $ {} $ $ \text{Sosai} \overset{\text{Spectator of 1st: Fofo}}{\longleftrightarrow} \text{Hohai} $ $ \text{Fofo} \overset{\text{Spectator of 2nd: Sosai}}{\longleftrightarrow} \text{Hohai} $ $ \text{Fofo} \overset{\text{Spectator of 3rd: Hohai}}{\longleftrightarrow} \text{Sosai} $ $ \text{Hohai} \overset{\text{Spectator of 4th: Fofo}}{\longleftrightarrow} \text{Sosai} $ $ \text{Hohai} \overset{\text{Spectator of 5th: Sosai}}{\longleftrightarrow} \text{Fofo} $ $ \text{Sosai} \overset{\text{Spectator of 6th: Hohai}}{\longleftrightarrow} \text{Fofo} $ $ \text{Sosai} \overset{\text{Spectator of 7th: Fofo}}{\longleftrightarrow} \text{Hohai} $ 52 53 No matter who wins in the second match, Hohai won't be able to continue playing in the third match (even if he wins the second match) since he has already played two times in a row. Similarly, Fofo won't be able to play in the fourth match because he has already played twice in a row, regardless of the match result. 54 55 As a result, Fofo won't be able to spectate in the $k$-th match for any $k$ of the form $3x + 1$. 56 57 The overall time complexity is: $O(1)$. 58 59 **Code** 60 61 ``` 62 #include<bits/stdc++.h> 63 using namespace std; 64 void solve() { 65 int k; 66 cin >> k; 67 if (k % 3 == 1) { 68 cout << "Yes\n"; 69 } else { 70 cout << "No\n"; 71 } 72 } 73 int main() { 74 ios::sync_with_stdio(0), cin.tie(0); 75 int tt = 1; 76 cin >> tt; 77 while (tt--) { 78 solve(); 79 } 80 } 81 ``` 82 83 **Rate the Problem** 84 85 * Amazing problem: 86 * Good problem: 87 * Average problem: 88 * Bad problem: 89 * Didn't solve: 90 91 [2071B - Perfecto](/contest/2071/problem/B "Codeforces Round 1007 (Div. 2)") 92 93 **Hints** 94 95 **Hint 1** 96 97 Consider the identity permutation, defined by $p_i = i$. When and why does this permutation not work? 98 99 **Hint 2** 100 101 The smallest index $i$ where the issue occurs must satisfy the condition that $1 + \ldots + i$ is a perfect square. What is the simplest and most efficient way to resolve this issue? 102 103 **Solution** 104 105 The first observation is that if the sum $1 + 2 + … + n = \frac{n(n+1)}{2}$ is a perfect square, no valid perfect permutation exists. 106 107 To prove that a solution always exists otherwise, start with the identity permutation $p_i = i$ and iterate through indices from $1$ to $n$. We keep on iterating as long as the prefix sum till that moment isn’t a perfect square. If the prefix sum up to index $k$ becomes a perfect square, $\frac{k(k+1)}{2} = x^2$, swap $p_k$ and $p_{k + 1}$. This changes the prefix sum to $x^2 + 1$, which is not a perfect square. 108 109 To ensure this method works, we must show that $\frac{(k+1)(k+2)}{2}$ cannot also be a perfect square. Assume for contradiction that $\frac{(k+1)(k+2)}{2} = y^2$. Then: 110 111 $ y^2 = x^2 + k + 1 $ 112 113 Since $x \gt \frac{k}{2}$ (because $x^2 = \frac{k(k+1)}{2} \gt \frac{k^2}{4}$), we have: 114 115 $ {} $ $ y^2 = x^2 + k + 1 \lt x^2 + 2x + 1 = (x+1)^2 \le y^2 $ 116 117 which is a contradiction. Thus, $\frac{(k+1)(k+2)}{2}$ cannot be a perfect square, and the process can be repeated until all indices are processed, ensuring a valid permutation. 118 119 The overall time complexity is: $O(n)$. 120 121 **Code** 122 123 ``` 124 #include<bits/stdc++.h> 125 using namespace std; 126 void solve() { 127 auto check = [&](int k) { 128 int j = sqrtl((int64_t)k * (k + 1) / 2); 129 return ((int64_t)j * j != (int64_t)k * (k + 1) / 2); 130 }; 131 int n; 132 cin >> n; 133 if (!check(n)) { 134 cout << "-1\n"; 135 return; 136 } 137 vector<int> ans(n + 1); 138 for (int i = 1; i <= n; i++) { 139 ans[i] = i; 140 } 141 int j = 0; 142 for (int i = 1; i <= n; i++) { 143 while ((int64_t)j * j < (int64_t)i * (i + 1) / 2) j++; 144 if ((int64_t)j * j == (int64_t)i * (i + 1) / 2) { 145 swap(ans[i], ans[i + 1]); 146 } 147 cout << ans[i] << " "; 148 } 149 cout << "\n"; 150 } 151 int main() { 152 ios::sync_with_stdio(0), cin.tie(0); 153 int tt = 1; 154 cin >> tt; 155 while (tt--) { 156 solve(); 157 } 158 } 159 ``` 160 161 **Rate the Problem** 162 163 * Amazing problem: 164 * Good problem: 165 * Average problem: 166 * Bad problem: 167 * Didn't solve: 168 169 [2071C - Trapmigiano Reggiano](/contest/2071/problem/C "Codeforces Round 1007 (Div. 2)") 170 171 **Hints** 172 173 **Hint 1** 174 175 Root the tree at vertex $\textrm{en}$. What observations can you make? 176 177 **Hint 2** 178 179 Can the cheese be placed at the vertices in a specific sequence that prevents the mouse from moving farther away from vertex $\textrm{en}$? 180 181 **Solution** 182 183 First, root the tree at vertex $\textrm{en}$ and approach it step by step. Observe that after processing all vertices at the largest depth $n−1$, the mouse’s current depth cannot exceed $n−1$. By repeating this process for the next largest depth $n−2$, the mouse’s depth will inevitably become $n−2$ or less. Continuing this way, we process vertices in descending order of depth until we reach the root, achieving the desired result. 184 185 The overall time complexity is: $O(n)$. 186 187 **Code** 188 189 ``` 190 #include<bits/stdc++.h> 191 using namespace std; 192 void solve() { 193 int n, s, e; 194 cin >> n >> s >> e; 195 vector adj(n + 1, vector<int> ()); 196 for (int i = 1; i < n; i++) { 197 int u, v; 198 cin >> u >> v; 199 adj[u].push_back(v), adj[v].push_back(u); 200 } 201 vector dis(n + 1, vector<int> ()); 202 vector<int> d(n + 1); 203 auto dfs = [&](auto &&self, int v, int par) -> void { 204 d[v] = d[par] + 1; 205 dis[d[v]].push_back(v); 206 for (int u: adj[v]) { 207 if (u == par) continue; 208 self(self, u, v); 209 } 210 }; 211 dfs(dfs, e, 0); 212 for (int i = n; i >= 1; i--) { 213 for (int j: dis[i]) { 214 cout << j << " "; 215 } 216 } 217 cout << "\n"; 218 } 219 int main() { 220 ios::sync_with_stdio(0), cin.tie(0); 221 int tt = 1; 222 cin >> tt; 223 while (tt--) { 224 solve(); 225 } 226 } 227 ``` 228 229 **Rate the Problem** 230 231 * Amazing problem: 232 * Good problem: 233 * Average problem: 234 * Bad problem: 235 * Didn't solve: 236 237 [2071D1 - Infinite Sequence (Easy Version)](/contest/2071/problem/D1 "Codeforces Round 1007 (Div. 2)") 238 239 **Hints** 240 241 **Hint 1** 242 243 Try to determine the connection between $a_{2m}$ and $a_{2m+1}$ for indices where $2m \gt n$. 244 245 **Hint 2** 246 247 Try to express $a_{2m}$ as the XOR of a short prefix of terms plus at most one extra term. 248 249 **Solution** 250 251 For convenience, assume $n$ is odd (if not, increment $n$ and handle the edge case separately). Start by precomputing the first $2n$ terms $a_1, a_2, \ldots, a_{2n}$. For queries with indices less than or equal to $2n$, directly return the precomputed value. For $2m \gt n$, observe the following relationship 252 253 $ a_{2m} = a_1 \oplus a_2 \oplus \ldots \oplus a_m = a_{2m + 1}. $ 254 255 Define $p = a_1 \oplus a_2 \oplus \ldots \oplus a_n$. Notice that when $m \gt n$, we can decompose the XOR sum as: 256 257 $ {} $ $ a_{2m} = a_1 \oplus a_2 \oplus \ldots \oplus a_m = a_1 \oplus a_2 \oplus \ldots \oplus a_n \oplus (a_{n + 1} \oplus a_{n + 2}) \oplus (a_{n + 3} \oplus a_{n + 4}) \oplus \ldots \oplus a_m $ $ a_{2m} = p \oplus (a_{n + 1} \oplus a_{n + 2}) \oplus (a_{n + 3} \oplus a_{n + 4}) \oplus \ldots \oplus a_m $ 258 259 Since $n$ is odd, the pairs $(a_{n + 1} \oplus a_{n + 2}), (a_{n + 3} \oplus a_{n + 4}), \ldots$ cancel out. This simplifies the formula to: 260 261 $ {} $ $ a_{2m} = a_{2m + 1} = \begin{cases} p & \text{if } m \text{ is odd}, \\ p \oplus a_m & \text{if } m \text{ is even}. \end{cases} $ 262 263 As a result, we can compute $a_m$ recursively by halving $m$ until $m \le 2n$, applying the parity rule at each step. 264 265 The overall time complexity is: $O(n+\log(m))$. 266 267 **Code** 268 269 ``` 270 #include<bits/stdc++.h> 271 using namespace std; 272 void solve() { 273 int n; 274 int64_t l, r; 275 cin >> n >> l >> r; 276 vector<int> a(n + 1); 277 for (int i = 1; i <= n; i++) { 278 cin >> a[i]; 279 } 280 vector<int> pref(n + 1); 281 for (int i = 1; i <= n; i++) { 282 pref[i] = pref[i - 1] + a[i]; 283 } 284 if (n % 2 == 0) { 285 n++; 286 int cur = pref[n / 2] & 1; 287 a.push_back(cur); 288 pref.push_back(pref.back() + cur); 289 } 290 for (int i = n + 1; i <= n * 2; i++) { 291 a.push_back(pref[i / 2] & 1); 292 pref.push_back(pref[i - 1] + a[i]); 293 } 294 int p = pref[n] & 1; 295 auto get = [&](int64_t x) { 296 int ret = 0; 297 while (true) { 298 if (x <= n * 2) { 299 ret ^= a[x]; 300 break; 301 } 302 ret ^= p; 303 if ((x / 2 - n) % 2 == 0) { 304 break; 305 } 306 x /= 2; 307 } 308 return ret; 309 }; 310 cout << get(l) << "\n"; 311 } 312 int main() { 313 ios::sync_with_stdio(0), cin.tie(0); 314 int tt = 1; 315 cin >> tt; 316 while (tt--) { 317 solve(); 318 } 319 } 320 ``` 321 322 **Rate the Problem** 323 324 * Amazing problem: 325 * Good problem: 326 * Average problem: 327 * Bad problem: 328 * Didn't solve: 329 330 [2071D2 - Infinite Sequence (Hard Version)](/contest/2071/problem/D2 "Codeforces Round 1007 (Div. 2)") 331 332 **Hints** 333 334 **Hint 1** 335 336 Generalize the recursive method for evaluating an index to handle the computation of the prefix sum. 337 338 **Solution** 339 340 First, check the editorial of D1. 341 342 **D&C Approach** 343 344 To upgrade the solution, we define a recursive function: 345 346 $ \text{sum}(m) = \left( \displaystyle\sum_{\substack{i \leq m \\ i \text{ even}}} a_i,\; \displaystyle\sum_{\substack{i \leq m \\ i \text{ odd}}} a_i \right). $ 347 348 We precompute the even and odd prefix sums for $m \le 2n$. For $m \gt 2n$, the term $a_m$ follows: 349 350 $ {} $ $ a_m = \begin{cases} p & \text{if } \lfloor \frac{m}{2} \rfloor \text{ is odd}, \\ p \oplus a_{\lfloor \frac{m}{2} \rfloor} & \text{if } \lfloor \frac{m}{2} \rfloor \text{ is even}. \end{cases} $ 351 352 For simplicity, assume $m \equiv 1 \pmod{4}$ (if not, keep incrementing $m$ and adjusting its contribution separately). 353 354 Define 355 356 $ e = \displaystyle\sum_{\substack{n \lt i \leq \lfloor \frac{m}{2} \rfloor \\ i \text{ even}}} a_i = a_{n+1} + a_{n+3} + \dots + a_{\lfloor \frac{m}{2} \rfloor} $ 357 358 This sum can be expressed as: 359 360 $e = \text{sum}(\lfloor \frac{m}{2} \rfloor)_{\text{even}} - prefix_{\text{even}}(n). $ 361 362 The pairs we're interested in computing are (keep in mind that $n$ is odd): 363 364 $ {} $ $ a_{2n} = a_{2n + 1} = p $ $ a_{2n + 2} = a_{2n + 3} = p \oplus a_{n + 1} $ $ a_{2n + 4} = a_{2n + 5} = p $ $ a_{2n + 6} = a_{2n + 7} = p \oplus a_{n + 3} $ $ \vdots $ $ a_{m - 3} = a_{m - 2} = p $ $ a_{m - 1} = a_{m} = p \oplus a_{\lfloor \frac{m}{2} \rfloor} $ 365 366 Notice that the sums of the above even and odd indices are equal, and depend on $p$: 367 368 $ {} $ $ both = \begin{cases} e & \text{if } p = 0, \\ (\lfloor \frac{m}{2} \rfloor - n + 1) - e & \text{if } p = 1. \end{cases} $ 369 370 Thus, the final sums are: 371 372 $ \text{sum}(m)_{\text{even}} = prefix_{\text{even}}(2n - 1) + both $ $ \text{sum}(m)_{\text{odd}} = prefix_{\text{odd}}(2n - 1) + both $ 373 374 As a result, we can compute $\text{sum}(m)$ recursively by halving $m$ until $m \le 2n$, benefitting the precomputed even and odd prefix sums at each step. 375 376 The overall time complexity is: $O(n+\log(m))$. 377 378 **Code** 379 380 ``` 381 #include<bits/stdc++.h> 382 using namespace std; 383 void solve() { 384 int n; 385 int64_t l, r; 386 cin >> n >> l >> r; 387 vector<int> a(n + 1); 388 for (int i = 1; i <= n; i++) { 389 cin >> a[i]; 390 } 391 vector<int> pref(n + 1); 392 for (int i = 1; i <= n; i++) { 393 pref[i] = pref[i - 1] + a[i]; 394 } 395 if (n % 2 == 0) { 396 n++; 397 int cur = pref[n / 2] & 1; 398 a.push_back(cur); 399 pref.push_back(pref.back() + cur); 400 } 401 for (int i = n + 1; i <= n * 2; i++) { 402 a.push_back(pref[i / 2] & 1); 403 pref.push_back(pref[i - 1] + a[i]); 404 } 405 vector<int> even(n * 2 + 1); 406 for (int i = 1; i <= n * 2; i++) { 407 even[i] = even[i - 1] + (i & 1 ? 0 : a[i]); 408 } 409 int p = pref[n] & 1; 410 auto get = [&](int64_t x) { 411 int ret = 0; 412 while (true) { 413 if (x <= n * 2) { 414 ret ^= a[x]; 415 break; 416 } 417 ret ^= p; 418 if ((x / 2 - n) % 2 == 0) { 419 break; 420 } 421 x /= 2; 422 } 423 return ret; 424 }; 425 auto sum = [&](auto&& self, int64_t m) -> pair<int64_t, int64_t> {// {sum even, sum odd} 426 if (m <= n * 2) { 427 return {even[m], pref[m] - even[m]}; 428 } 429 int64_t eve = even[n * 2 - 1], odd = pref[n * 2 - 1] - eve; 430 if (m % 2 == 0) { 431 m += 1, odd -= get(m); 432 } 433 if (m / 2 % 2) { 434 m += 1, eve -= get(m); 435 m += 1, odd -= get(m); 436 } 437 auto [e, _] = self(self, m / 2); 438 e -= even[n]; 439 int64_t c = m / 2 - n + 1, both = (p ? c - e : e); 440 eve += both, odd += both; 441 return {eve, odd}; 442 }; 443 int64_t ans = 0; 444 auto [re, ro] = sum(sum, r); 445 ans += re + ro; 446 auto [le, lo] = sum(sum, l - 1); 447 ans -= le + lo; 448 cout << ans << "\n"; 449 } 450 int main() { 451 ios::sync_with_stdio(0), cin.tie(0); 452 int tt = 1; 453 cin >> tt; 454 while (tt--) { 455 solve(); 456 } 457 } 458 ``` 459 460 **Rate the Problem** 461 462 * Amazing problem: 463 * Good problem: 464 * Average problem: 465 * Bad problem: 466 * Didn't solve: 467 468 [2071E - LeaFall](/contest/2071/problem/E "Codeforces Round 1007 (Div. 2)") 469 470 **Hints** 471 472 **Hint 1** 473 474 Think about an unordered pair $(u, v)$ where both u and v are leaves in the final forest. Consider dividing all such pairs into separate categories based on their relationship in the original tree. 475 476 **Hint 2** 477 478 Let the first category be the pairs that are directly connected (neighbors), and analyze under what conditions both vertices become leaves. 479 480 **Hint 3** 481 482 For the pairs that are not direct neighbors, focus on those that share a common neighbor. Investigate how the state (fallen or not) of their neighbors influences the possibility of both vertices becoming leaves. 483 484 **Solution** 485 486 Let $fall_{i} $ denote the probability that the $i$-th node falls. We partition the unordered pairs $(u,v)$ into three categories: 487 488 1. $u$ and $v$ are direct neighbors. 489 2. $u$ and $v$ share a common neighbor. 490 3. Pairs that do not satisfy the first two conditions. 491 492 Now, let us analyze the contribution of the first category to the final answer. For a pair $(u,v)$ of direct neighbors, both vertices become leaves if neither $u$ nor $v$ falls and if all of their other neighbors fall. Thus, the contribution of a specific pair $(u,v)$ is given by: 493 494 $ {} $ $ contribution_1(u,v) = (1 - fall_{u}) \cdot (1 - fall_{v}) \cdot \prod_{\substack{k \text{ is a neighbor of } u \text{ or } v,\, k \neq u,\, k \neq v}} fall_{k}. $ 495 496 The whole contribution of the first category is: 497 498 $ {} $ $\sum_{(u,v) \text{ are neighbors}} contribution_1(u,v).$ 499 500 For the second category, $u$ and $v$ share a neighbor, so this shared neighbor either must be the only one not falling among the neighbors of $u$ and $v$, or it must fall and exactly one of the other neighbors of both $u$ and $v$ must not fall. Additionally, both $u$ and $v$ must not fall anyway. Therefore, the contribution for a pair $(u,v)$ in the second category is given by: 501 502 $ {} $ $ e_i = (\prod_{c \text{ is a neighbor of } i, \, c \neq s} fall_{c}) \cdot (\sum_{c \text{ is a neighbor of } i, \, c \neq s} \frac{1 - fall_{c}}{fall_{c}}) $ $ {} $ $ contribution_2(u,v) = (1 - fall_{u}) \cdot (1 - fall_{v}) \cdot (1 - fall_{s}) \cdot \prod_{\substack{k \text{ is a neighbor of } u \text{ or } v,\, k \neq u,\, k \neq v,\, k \neq s }} fall_{k} $ $ {} $ $ + (1 - fall_{u}) \cdot (1 - fall_{v}) \cdot (fall_{s}) \cdot e_u \cdot e_v $ 503 504 where $s$ is the shared neighbor of $u$ and $v$. 505 506 The whole contribution of the second category is: 507 508 $ {} $ $\sum_{(u,v) \text{ share a neighbor}} contribution_2(u,v).$ 509 510 Moving to the third category: Here, $u$ and $v$ are neither direct neighbors nor do they share any common neighbor. In this case, the events that $u$ and $v$ become leaves are completely independent. 511 512 Define $leaf_{i} = (1 - fall_{i}) \cdot (\prod_{c \text{ is a neighbor of } i} fall_{c}) \cdot (\sum_{c \text{ is a neighbor of } i} \frac{1 - fall_{c}}{fall_{c}})$ as the probability that vertex $i$ becomes a leaf. Hence, for a pair $(u,v)$ in this category, the contribution is given by: 513 514 $ {} $ $ contribution_3(u,v) = leaf_{u} \cdot leaf_{v}.$ 515 516 The whole contribution of the third category is: 517 518 $ {} $ $\sum_{(u,v) \in \text{third category}} contribution_3(u,v).$ 519 520 The final answer is obtained by summing the contributions from all three categories. We can compute the contribution of the third category by summing $leaf_{i} \cdot leaf_{j}$ for all pairs $(i, j)$ with $i \lt j$, and then subtracting the contributions corresponding to pairs that satisfy one of the first two categories. The contribution of the second category can be computed by iterating over each node and accumulating the contributions from its neighbors (since these pairs share that node as their only common neighbor). The contribution of the first category can be computed in linear time too. 521 522 The overall time complexity is $O(n \cdot \log M)$, where the $\log$ factor arises from the modular inverse computations. 523 524 **Code** 525 526 ``` 527 #include<bits/stdc++.h> 528 using namespace std; 529 const int mod = 998244353; 530 int add(int x, int y) { 531 return x + y - (x + y >= mod) * mod; 532 } 533 void add2(int &x, int y) { 534 x += y; 535 if (x >= mod) x -= mod; 536 } 537 int mul(int x, int y) { 538 return int((int64_t)x * y % mod); 539 } 540 int sub(int x, int y) { 541 return x - y + (x < y) * mod; 542 } 543 void sub2(int &x, int y) { 544 x -= y; 545 if (x < 0) x += mod; 546 } 547 int pwr(int x, int y) { 548 int ret = 1; 549 while (y) { 550 if (y & 1) ret = mul(ret, x); 551 x = mul(x, x); 552 y /= 2; 553 } 554 return ret; 555 } 556 int inv(int x) { 557 return pwr(x, mod - 2); 558 } 559 int norm(int64_t x) { 560 x %= mod; 561 if (x < 0) x += mod; 562 return int(x); 563 } 564 void solve() { 565 int n; 566 cin >> n; 567 vector adj(n + 1, vector<int> ()); 568 vector<int> p(n + 1); 569 for (int i = 1; i <= n; i++) { 570 int q; 571 cin >> p[i] >> q; 572 p[i] = mul(p[i], inv(q)); 573 //here, p[i] is the probability that node i will fall 574 } 575 for (int i = 1; i < n; i++) { 576 int u, v; 577 cin >> u >> v; 578 adj[u].push_back(v), adj[v].push_back(u); 579 } 580 vector<int> p1(n + 1), p2(n + 1); 581 for (int i = 1; i <= n; i++) { 582 p1[i] = sub(1, p[i]); 583 for (int u: adj[i]) { 584 p1[i] = mul(p1[i], p[u]); 585 } 586 //p1[i] is the probability that node i won't fall, but all nodes around it will fall 587 for (int u: adj[i]) { 588 add2(p2[i], mul(p1[i], mul(inv(p[u]), sub(1, p[u])))); 589 } 590 //p2[i] is the probability that node i will be a leaf (it won't fall, all it's neighbors except one will fall) 591 } 592 int ans = 0, sum = 0; 593 for (int i = 1; i <= n; i++) { 594 add2(ans, mul(p2[i], sum)); 595 add2(sum, p2[i]); 596 } 597 //take all contributions of unordered pairs 598 for (int i = 1; i <= n; i++) { 599 //recalculate the contribution of neighboring pairs 600 for (auto u: adj[i]) { 601 if (u < i) continue; 602 //avoid calculating the same pair probabilty twice 603 int pi = mul(p1[i], inv(p[u])); 604 //pi is the probability that every neighbour of i would fall except for u (not including the probability of u not falling down) 605 int pu = mul(p1[u], inv(p[i])); 606 //pu is the probability that every neighbour of u would fall except for i (not including the probability of i not falling down) 607 //this case is just a tree of 2 nodes, both of them are leaves 608 add2(ans, mul(pi, pu)); 609 //subtract the old contribution 610 sub2(ans, mul(p2[i], p2[u])); 611 } 612 //recalculate the contribution of pairs with a shared neighbour which is node i (ie calculate the contribution for pairs u, v such that dis(u, v) = 2 and dis(u, i) = dis(v, i) = 1 613 sum = 0; 614 for (int u: adj[i]) { 615 sub2(ans, mul(sum, p2[u])); 616 add2(sum, p2[u]); 617 //subtract the old contribution 618 } 619 //p[i] doesn't fall 620 sum = 0; 621 for (int u: adj[i]) { 622 int pu = mul(p1[u], inv(p[i])); 623 //pu is the probability that node u is a leaf connected to node i 624 add2(ans, mul(sum, pu)); 625 add2(sum, mul(pu, sub(1, p[i]))); 626 } 627 //p[i] falls 628 sum = 0; 629 for (int u: adj[i]) { 630 int pu = sub(p2[u], mul(p1[u], mul(inv(p[i]), sub(1, p[i])))); 631 //pu is the probability that node u is a leaf not connected to node i 632 add2(ans, mul(sum, pu)); 633 add2(sum, mul(pu, inv(p[i]))); 634 } 635 } 636 cout << ans << "\n"; 637 } 638 int main() { 639 ios::sync_with_stdio(0), cin.tie(0); 640 int tt = 1; 641 cin >> tt; 642 while (tt--) { 643 solve(); 644 } 645 } 646 ``` 647 648 **Rate the Problem** 649 650 * Amazing problem: 651 * Good problem: 652 * Average problem: 653 * Bad problem: 654 * Didn't solve: 655 656 [2071F - Towering Arrays](/contest/2071/problem/F "Codeforces Round 1007 (Div. 2)") 657 658 **Hints** 659 660 **Hint 1** 661 662 Binary search on $p$. After fixing $p$, find the maximum $p$-towering subsequence. 663 664 **Hint 2** 665 666 if we denote the set of indexes that correspond to the maximum "increasing" $p$-towering subsequence on prefix $i$ as $S_i$, then for any $i \lt n$: $S_i \subseteq S_{i + 1}$. 667 668 **Solution** 669 670 Let's do binary search on $p$. After fixing some $p$ our goal is to find the maximum $p$-towering subsequence and check if the length of that subsequence $s$ satisfies $n - s \le k$. 671 672 To find the maximum $p$-towering subsequence, for each index $i$ we will find the maximum $p$-towering subsequence such that the "left" part of that subsequence is in prefix $i$ and its right part is in suffix $i$. 673 674 Let's focus only on prefixes, as the suffixes can be done similarly. So, for each prefix $i$ we want to find the maximum "increasing" $p$-towering subsequence. To do it, we will traverse the array from left to right and maintain the currently found maximum subsequence. The key idea here is that as you move from left to right you only need to add new elements to the "increasing" subsequence and never delete any (or, formally speaking, if we denote the set of indexes that correspond to maximum "increasing" $p$-towering subsequence on prefix $i$ as $S_i$, then for any $i \lt n$: $S_i \subseteq S_{i + 1}$ (the proof is left to the reader). 675 676 **Elaboration** 677 678 Before moving to the details of implementation, let's elaborate a bit on the previous paragraph. Consider the fifth test case from the sample; suppose the current $p = 7$; and we have just arrived at the tenth element (denoted with star $^*$). Before this position, the maximum "increasing" $p$-towering subsequence consists of the first, third, and fifth elements (denoted with underlines): 679 680 $[\underline{6}, 3, \underline{8}, 5, \underline{8}, 3, 2, 1, 2, 7^*, 1]$. 681 682 Now we need to check if we can increase the size of the subsequence. Since $p = 7$, then we certainly can add the tenth element with value $7$ to the subsequence. However, since we add a new number to the subsequence, two numbers become available: the second one with value $3$ and the forth one with value $5$. Thus, after processing the tenth element, the maximum "increasing" $p$-towering subsequence will look like this: 683 684 $[\underline{6}, \color{red}{\underline{3}}, \underline{8}, \color{red}{\underline{5}}, \underline{8}, 3, 2, 1, 2, \color{red}{\underline{7}}^*, 1]$. 685 686 So we need some way to find such "new" numbers that appear when we add some elements to the subsequence (like when the element with value $5$ becomes available from the example). To resolve this we first assign $a_i := p - a_i$ for each $i$. To find the positions that are becoming available, we can search for the rightmost non-positive element on the current prefix. Once found (suppose its index is $j$), decrease all elements on the prefix $j$ by one and assign $a_j := \infty$ (to avoid this position in the future). All these operations can be performed with the help of a segment tree. 687 688 This concludes the asymptotic complexity: $O(n \log{C} \log{n})$. 689 690 **Code** 691 692 ``` 693 #include <bits/stdc++.h> 694 695 #define len(a) (int)a.size() 696 #define all(a) a.begin(), a.end() 697 698 using namespace std; 699 const int MAXI = 1e9 + 1e7; 700 701 const int MAXN = 2e5 + 100; 702 struct Node { 703 int min_on_subtree = 0, push_addition = 0; 704 }; 705 Node t[MAXN * 4]; 706 int a[MAXN], pref[MAXN], suf[MAXN]; 707 708 class Segtree { 709 private: 710 int n; 711 void add_on_subtree(int u, int val) { 712 t[u].push_addition += val; 713 t[u].min_on_subtree += val; 714 } 715 void push(int u) { 716 if (t[u].push_addition) { 717 add_on_subtree(u * 2 + 1, t[u].push_addition); 718 add_on_subtree(u * 2 + 2, t[u].push_addition); 719 t[u].push_addition = 0; 720 } 721 } 722 void recalc(int u) { 723 t[u].min_on_subtree = min(t[u * 2 + 1].min_on_subtree, t[u * 2 + 2].min_on_subtree); 724 } 725 void update(int u, int l, int r, int pos, int val) { 726 if (l == r) { 727 t[u].min_on_subtree = val; 728 } else { 729 push(u); 730 int mid = (l + r) / 2; 731 if (pos <= mid) 732 update(u * 2 + 1, l, mid, pos, val); 733 else 734 update(u * 2 + 2, mid + 1, r, pos, val); 735 recalc(u); 736 } 737 } 738 void add_on_segment(int u, int l, int r, int ql, int qr, int val) { 739 if (ql <= l && r <= qr) 740 add_on_subtree(u, val); 741 else { 742 push(u); 743 int mid = (l + r) / 2; 744 if (ql <= mid) 745 add_on_segment(u * 2 + 1, l, mid, ql, qr, val); 746 if (qr > mid) 747 add_on_segment(u * 2 + 2, mid + 1, r, ql, qr, val); 748 recalc(u); 749 } 750 } 751 int find_prev_non_pos_put_inf(int u, int l, int r, int pos) { 752 if (t[u].min_on_subtree > 0) 753 return -1; 754 if (l == r) { 755 t[u].min_on_subtree = MAXI; 756 return l; 757 } 758 push(u); 759 int mid = (l + r) / 2, res = -1; 760 if (pos > mid) 761 res = find_prev_non_pos_put_inf(u * 2 + 2, mid + 1, r, pos); 762 if (res == -1) 763 res = find_prev_non_pos_put_inf(u * 2 + 1, l, mid, pos); 764 recalc(u); 765 return res; 766 } 767 public: 768 explicit Segtree(int n): n(n) { 769 fill(t, t + 4 * n, Node{MAXI, 0}); 770 }; 771 772 void update(int pos, int val) { 773 update(0, 0, n - 1, pos, val); 774 } 775 void add_on_segment(int ql, int qr, int val) { 776 add_on_segment(0, 0, n - 1, ql, qr, val); 777 } 778 int find_prev_non_pos_put_inf(int pos) { 779 return find_prev_non_pos_put_inf(0, 0, n - 1, pos); 780 } 781 }; 782 783 void f(int n, int p, int *res) { 784 Segtree tree(n); 785 int cur_sz = 0; 786 for (int i = 0; i < n; i++) { 787 tree.update(i, p - a[i]); 788 int pos = i; 789 while ((pos = tree.find_prev_non_pos_put_inf(pos)) != -1) { 790 cur_sz++; 791 tree.add_on_segment(0, pos, -1); 792 } 793 res[i] = cur_sz; 794 } 795 } 796 797 int32_t main() { 798 ios_base::sync_with_stdio(false); 799 cin.tie(0); 800 #ifndef ONLINE_JUDGE 801 freopen("input.txt", "r", stdin); 802 freopen("output.txt", "w", stdout); 803 #endif 804 int testcases; 805 cin >> testcases; 806 while (testcases--) { 807 int n, k; 808 cin >> n >> k; 809 int max_a = -1; 810 for (int i = 0; i < n; i++) { 811 cin >> a[i]; 812 max_a = max(max_a, a[i]); 813 } 814 int l = 0, r = max_a + 1; 815 while (l + 1 < r) { 816 int mid = (l + r) / 2; 817 f(n, mid, pref); 818 reverse(a, a + n); 819 f(n, mid, suf); 820 reverse(a, a + n); 821 reverse(suf, suf + n); 822 int mx = -1; 823 for (int i = 0; i < n; i++) { 824 if (a[i] >= mid) 825 mx = max(mx, pref[i] + suf[i] - 1); 826 } 827 if (n - mx <= k) 828 l = mid; 829 else 830 r = mid; 831 } 832 cout << l << '\n'; 833 } 834 } 835 ``` 836 837 **Rate the Problem** 838 839 * Amazing problem: 840 * Good problem: 841 * Average problem: 842 * Bad problem: 843 * Didn't solve: