1920.md (29550B)
1 Source: https://codeforces.com/blog/entry/122560 2 3 ## Information about the round 4 5 **Rating predictions (inspired by BucketPotato's editorial)** 6 7 | Person | A | B | C | D | E | F1 | F2 | 8 | --- | --- | --- | --- | --- | --- | --- | --- | 9 | [sum](/profile/sum "Master sum") | 800 | 1300 | 1500 | 1900 | 2000 | 2200 | 2900 | 10 | [oursaco](/profile/oursaco "Grandmaster oursaco") | 800 | 1100 | 1300 | 1600 | 1800 | 2100 | 3100 | 11 | [omeganot](/profile/omeganot "Master omeganot") | 900 | 1000 | 1400 | 1700 | 1900 | 2200 | 2800 | 12 | [SriniV](/profile/SriniV "Candidate Master SriniV") | | | | 1900 | 2000 | 1900 | | 13 | [Apple_Method](/profile/Apple_Method "Grandmaster Apple_Method") | 1000 | 1200 | 1400 | 1900 | 1600 | | | 14 | [awesomeguy856](/profile/awesomeguy856 "Master awesomeguy856") | 800 | 1100 | 1400 | 1800 | 1900 | 2000 | 2800 | 15 | [nonrice](/profile/nonrice "Expert nonrice") | 900 | 1000 | 1400 | 1750 | | | | 16 | [null_awe](/profile/null_awe "Grandmaster null_awe") | 800 | 1100 | 1300 | 1700 | 1900 | 2000 | 2600 | 17 | [htetgm](/profile/htetgm "Candidate Master htetgm") | 900 | 1000 | 1200 | 1700 | 2000 | | | 18 | [thehunterjames](/profile/thehunterjames "Candidate Master thehunterjames") | 900 | 1300 | 1600 | 1900 | | | | 19 | [Yam](/profile/Yam "Grandmaster Yam") | 800 | 1100 | 1500 | 1800 | 2000 | 2100 | | 20 | [GusterGoose27](/profile/GusterGoose27 "Grandmaster GusterGoose27") | | | | | | | 3000 | 21 22 | | A | B | C | D | E | F1 | F2 | 23 | --- | --- | --- | --- | --- | --- | --- | --- | 24 | Average | 860 | 1120 | 1400 | 1786 | 1900 | 2071 | 2867 | 25 | Actual | 800 | 1100 | 1500 | 1800 | 2100 | 2500 | 3000 | 26 27 **Who did what** 28 29 We would like to thank [Artyom123](/profile/Artyom123 "Grandmaster Artyom123") for feedback on every problem and immense help with problem preparation. We would also like to thank all the testers for their valuable feedback which greatly improved the round. The editorial was prepared by [sum](/profile/sum "Master sum") and [omeganot](/profile/omeganot "Master omeganot"). 30 31 | | Problem | Preparation | 32 | --- | --- | --- | 33 | A | [sum](/profile/sum "Master sum") | [sum](/profile/sum "Master sum") | 34 | B | [sum](/profile/sum "Master sum") | [sum](/profile/sum "Master sum") | 35 | C | [omeganot](/profile/omeganot "Master omeganot") | [omeganot](/profile/omeganot "Master omeganot") | 36 | D | [sum](/profile/sum "Master sum") | [sum](/profile/sum "Master sum"), [omeganot](/profile/omeganot "Master omeganot") | 37 | E | [sum](/profile/sum "Master sum") | [sum](/profile/sum "Master sum") | 38 | F1 & F2 | [sum](/profile/sum "Master sum") | [sum](/profile/sum "Master sum"), [omeganot](/profile/omeganot "Master omeganot") | 39 40 ## Solutions 41 42 ##### [1920A - Satisfying Constraints](/contest/1920/problem/A "Codeforces Round 919 (Div. 2)") 43 44 **Hint 1** 45 46 Suppose there are no $\neq$ constraints. How would you solve the problem? How would you then factor in the $\neq$ constraints into your solution? 47 48 **Solution** 49 50 Let's first only consider the $\geq$ and $\leq$ constraints. The integers satisfying those two constraints will be some contiguous interval $[l, r]$. To find $[l,r]$, for each $\geq x$ constraint, we do $l := \max{(l, x)}$ and for each $\leq x$ constraint, we do $r := \min{(r, x)}$. 51 52 Now, for each, $\neq x$ constraint, we check if $x$ is in $[l, r]$. If so, we subtract one from the answer (remember that there are no duplicate constraints). Let the total number of times we subtract be $s$. Then our answer is $\max{(r-l+1-s,0)}$. The time complexity of this solution is $O(n)$. 53 54 **Code** 55 56 ``` 57 #include <bits/stdc++.h> 58 using namespace std; 59 60 void solve(){ 61 int n; 62 cin >> n; 63 64 int l = 1; 65 int r = 1e9; 66 int s = 0; 67 68 vector<int> neq; 69 70 for (int i = 0; i < n; i++){ 71 int a, x; 72 cin >> a >> x; 73 74 if (a == 1) 75 l = max(l, x); 76 if (a == 2) 77 r = min(r, x); 78 if (a == 3) 79 neq.push_back(x); 80 } 81 for (int x : neq) 82 if (x >= l and x <= r) 83 s++; 84 85 cout<<max(r - l + 1 - s, 0)<<"\n"; 86 } 87 88 int main(){ 89 ios_base::sync_with_stdio(0); cin.tie(0); 90 int tc; 91 cin >> tc; 92 93 while (tc--) 94 solve(); 95 } 96 ``` 97 98 ##### [1920B - Summation Game](/contest/1920/problem/B "Codeforces Round 919 (Div. 2)") 99 100 **Hint 1** 101 102 What is the optimal strategy for Bob? 103 104 **Hint 2** 105 106 It is optimal for Bob to negate the $x$ largest elements of the array. So what should Alice do? 107 108 **Solution** 109 110 It is optimal for Bob to negate the $x$ largest elements of the array. So in order to minimize the damage Bob will do, Alice should always remove some number of largest elements. 111 112 To solve the problem, we can sort the array and iterate over $i$ ($0 \leq i \leq k$) where $i$ is the number of elements Alice removes. For each $i$, we know that Alice will remove the $i$ largest elements of the array and Bob will then negate the $x$ largest remaining elements. So the sum at the end can be calculated quickly with prefix sums. The time complexity is $O(n \log n)$ because of sorting. 113 114 **Code** 115 116 ``` 117 #include <bits/stdc++.h> 118 using namespace std; 119 120 void solve(){ 121 int n, k, x; 122 cin >> n >> k >> x; 123 124 int A[n + 1] = {}; 125 for (int i = 1; i <= n; i++) 126 cin >> A[i]; 127 128 sort(A + 1, A + n + 1, greater<int>()); 129 130 for (int i = 1; i <= n; i++) 131 A[i] += A[i - 1]; 132 133 int ans = -1e9; 134 for (int i = 0; i <= k; i++) 135 ans = max(ans, A[n] - 2 * A[min(i + x, n)] + A[i]); 136 137 cout<<ans<<"\n"; 138 } 139 140 int main(){ 141 ios_base::sync_with_stdio(0); cin.tie(0); 142 int tc; 143 cin >> tc; 144 145 while (tc--) 146 solve(); 147 } 148 ``` 149 150 ##### [1920C - Partitioning the Array](/contest/1920/problem/C "Codeforces Round 919 (Div. 2)") 151 152 **Hint 1** 153 154 Try to solve the problem for just two integers $x$ and $y$. Under what $m$ are they equal (modulo $m$)? 155 156 **Hint 2** 157 158 How can we use the previous hint and gcd to solve the problem? 159 160 **Solution** 161 162 For some $x$ and $y$, let's try to find all $m$ such that $x \bmod m \equiv y \bmod m$. We can rearrange the equation into $(x-y) \equiv 0 \pmod m$. Thus, if $m$ is a factor of $|x-y|$, then $x$ and $y$ will be equal modulo $m$. 163 164 Let's solve for some $k$. A valid partition exists if there exists some $m \gt 1$ such that the following is true: 165 166 * $a_1 \equiv a_{1+k} \pmod m$ 167 * $a_2 \equiv a_{2+k} \pmod m$ 168 * ... 169 * $a_{n-k} \equiv a_{n} \pmod m$ 170 171 The first condition $a_1 \equiv a_{1+k} \pmod m$ is satisfied if $m$ is a factor of $|a_1-a_{1+k}|$. The second condition $a_2 \equiv a_{2+k} \pmod m$ is satisfied if $m$ is a factor of $|a_2-a_{2+k}|$. And so on... 172 173 Thus, all conditions are satisfied if $m$ is a factor of: 174 175 $|a_1-a_{1+k}|, |a_2-a_{2+k}|,...,|a_{n-k}-a_n|$ 176 177 In other words, all conditions are satisfied if $m$ is a factor of: 178 179 $\gcd(|a_1-a_{1+k}|, |a_2-a_{2+k}|,...,|a_{n-k}-a_n|)$ 180 181 So a valid $m$ exists for some $k$ if the aforementioned $\gcd$ is greater than $1$. 182 183 We can iterate over all possible $k$ (remember that $k$ is a divisor of $n$) and solve for each $k$ to get our answer. The time complexity of this will be $O((n + \log n) \cdot \text{max divisors of n})$. Note that each pass through the array takes $n + \log n$ time because of how the gcd will either be halved or stay the same at each point. 184 185 **Code** 186 187 ``` 188 #include <bits/stdc++.h> 189 using namespace std; 190 191 void solve(){ 192 int n; 193 cin >> n; 194 195 int A[n]; 196 for (int &i : A) 197 cin >> i; 198 199 int ans = 0; 200 for (int k = 1; k <= n; k++){ 201 if (n % k == 0){ 202 int g = 0; 203 for (int i = 0; i + k < n; i++) 204 g = __gcd(g, abs(A[i + k] - A[i])); 205 ans += (g != 1); 206 } 207 } 208 cout<<ans<<"\n"; 209 } 210 211 int main(){ 212 ios_base::sync_with_stdio(0); cin.tie(0); 213 int tc; 214 cin >> tc; 215 216 while (tc--) 217 solve(); 218 } 219 ``` 220 221 ##### [1920D - Array Repetition](/contest/1920/problem/D "Codeforces Round 919 (Div. 2)") 222 223 **Hint 1** 224 225 For some query try to trace your way back to where the $k$-th number was added. 226 227 **Hint 2** 228 229 Here's an example of tracing back: 230 231 $ \underbrace{[l_1, l_2,...l_{x}]}_{\text{length } x} \underbrace{[l_1, l_2,...l_{x}]}_{\text{length } x} \underbrace{[l_1, l_2,...l_{x}]}_{\text{length } x} ... \underbrace{[l_1, \textbf{l_2},...l_{x}]}_{\text{length } x} $ 232 233 Suppose the $k$-th element is the bolded $l_2$. Finding the $k$-th element is equivalent to finding the ($k \bmod x$)-th element (unless if $k \bmod x$ is $0$). 234 235 **Solution** 236 237 First, let's precalculate some things: 238 239 $lst_i=\text{last element after performing the first $i$ operations}$ $dp_i=\text{number of elements after the first i operations}$ 240 241 Now, let's try answering some query $k$. If we have some $dp_i=k$ then the answer is $lst_i$. 242 243 Otherwise, let's find the first $i$ such that $dp_i \gt k$. This $i$ will be a repeat operation and our answer will lie within one of the repetitions. Our list at this point will look like: 244 245 $ \underbrace{[l_1, l_2,...l_{dp_{i-1}}]}_{\text{length } dp_{i-1}} \underbrace{[l_1, l_2,...l_{dp_{i-1}}]}_{\text{length } dp_{i-1}} \underbrace{[l_1, l_2,...l_{dp_{i-1}}]}_{\text{length } dp_{i-1}} ... \underbrace{[l_1, \textbf{l_2},...l_{dp_{i-1}}]}_{\text{length } dp_{i-1}} $ 246 247 Let the $k$-th element be the bolded $l_2$ of the final repetition. As you can see, finding the $k$-the element is equivalent to finding the $(k \bmod dp_{i-1})$-th element. Thus, we should do $k:=k \bmod dp_{i-1}$ and repeat! But there is one more case! If $k \equiv 0 \pmod {dp_{i-1}}$ then the answer is $lst_{i-1}$. 248 249 At this point there are 2 ways we can go about solving this: 250 251 **Way 1** 252 253 Notice that after $\log{(\max{k})}$ operations of the second type, the number of elements will exceed $\max{k}$. So we only care about the first $\log{(\max{k})}$ operations of the second type. Thus, iterate through the $\log{(\max{k})}$ operations of the second type backwards and perform the casework described above. This leads to a $O(n+q\log{(\max{k})})$ solution or a $O(n+q(\log{(\max{k})}+\log n))$ solution depending on implementation details. 254 255 **Way 2** 256 257 Observe that $k:=k \bmod dp_{i-1}$ will reduce $k$ by at least half. If we repeatedly binary search for the first $i$ such that $dp_i \geq k$, and then do $k:=k \bmod dp_{i-1}$ (or stop if it's one of the other cases), then each query will take $O(\log n\log k)$ time so the total time complexity will be $O(n+q\log n\log {(\max{k})})$. 258 259 **Code (iterating over second type operations)** 260 261 ``` 262 #include <bits/stdc++.h> 263 using namespace std; 264 265 #define ll long long 266 267 void solve(){ 268 int n, q; 269 cin >> n >> q; 270 271 ll dp[n + 1] = {}; 272 int lstAdd[n + 1] = {}; 273 vector<int> pos; 274 275 for (int i = 1, doAdd = true; i <= n; i++){ 276 int a, v; 277 cin >> a >> v; 278 279 if (a == 1){ 280 lstAdd[i] = v; 281 dp[i] = dp[i - 1] + 1; 282 } 283 else{ 284 lstAdd[i] = lstAdd[i - 1]; 285 dp[i] = ((v + 1) > 2e18 / dp[i - 1]) ? (ll)2e18 : dp[i - 1] * (v + 1); 286 287 if (doAdd) 288 pos.push_back(i); 289 } 290 // No need to consider any more repetitions after this point 291 if (dp[i] == 2e18) 292 doAdd = false; 293 } 294 while (q--){ 295 ll k; 296 cin >> k; 297 298 for (int i = pos.size() - 1; ~i; i--){ 299 int idx = pos[i]; 300 301 if (dp[idx] > k and dp[idx - 1] < k){ 302 if (k % dp[idx - 1] == 0){ 303 k = dp[idx - 1]; 304 break; 305 } 306 k %= dp[idx - 1]; 307 } 308 } 309 cout<<lstAdd[lower_bound(dp + 1, dp + n + 1, k) - dp]<<" \n"[q == 0]; 310 } 311 } 312 313 int main(){ 314 ios_base::sync_with_stdio(0); cin.tie(0); 315 int tc; 316 cin >> tc; 317 318 while (tc--) 319 solve(); 320 } 321 ``` 322 323 **Code (repeated binary searches)** 324 325 ``` 326 #include <bits/stdc++.h> 327 using namespace std; 328 329 #define ll long long 330 331 void solve(){ 332 int n, q; 333 cin >> n >> q; 334 335 ll dp[n + 1] = {}; 336 int lstAdd[n + 1] = {}; 337 338 for (int i = 1; i <= n; i++){ 339 int a, v; 340 cin >> a >> v; 341 342 if (a == 1){ 343 lstAdd[i] = v; 344 dp[i] = dp[i - 1] + 1; 345 } 346 else{ 347 lstAdd[i] = lstAdd[i - 1]; 348 dp[i] = ((v + 1) > 2e18 / dp[i - 1]) ? (ll)2e18 : dp[i - 1] * (v + 1); 349 } 350 } 351 while (q--){ 352 ll k; 353 cin >> k; 354 355 while (true){ 356 int pos = lower_bound(dp + 1, dp + n + 1, k) - dp; 357 358 if (dp[pos] == k){ 359 cout<<lstAdd[pos]<<" \n"[q == 0]; 360 break; 361 } 362 if (k % dp[pos - 1] == 0){ 363 cout<<lstAdd[pos - 1]<<" \n"[q == 0]; 364 break; 365 } 366 k %= dp[pos - 1]; 367 } 368 } 369 } 370 371 int main(){ 372 ios_base::sync_with_stdio(0); cin.tie(0); 373 int tc; 374 cin >> tc; 375 376 while (tc--) 377 solve(); 378 } 379 ``` 380 381 ##### [1920E - Counting Binary Strings](/contest/1920/problem/E "Codeforces Round 919 (Div. 2)") 382 383 **Hint 1** 384 385 How do you count the number of good substrings in a string? 386 387 **Hint 2** 388 389 We can count the number of good substrings in a string with the counting contribution technique. Now try to solve this problem with dynamic programming. 390 391 **Hint 3** 392 393 $\frac{n}{1} + \frac{n}{2} + \cdots + \frac{n}{n} = O(n\log n)$ 394 395 **Solution** 396 397 Let's first solve the problem where we are given some string $s$ and must count the number of good substrings. To do this we use the technique of counting contributions. For every $1$ in $s$, we find the number of good substrings containing that $1$. Consider the following example: 398 399 $ \underbrace{00001}_{a_1} \! \! \! \, \underbrace{ \; \, \! 0001}_{a_2} \! \! \! \, \underbrace{ \; \, \! 00000001}_{a_3} \! \! \! \, \underbrace{ \; \, \! 0001}_{a_4} \! \! \! \, \underbrace{ \; \, \! 000}_{a_5} $ 400 401 The number of good substrings in this example is $a_1 a_2 + a_2 a_3 + a_3 a_4 + a_4 a_5$. We can create such array for any string $s$ and the number of good substrings of $s$ is the sum of the products of adjacent elements of the array. 402 403 This motivates us to reformulate the problem. Instead, we count the number of arrays $a_1,a_2,...,a_m$ such that every element is positive and the sum of the products of adjacent elements is exactly equal to $n$. Furthermore, every pair of adjacent elements should have sum minus $1$ be less than or equal to $k$. We can solve this with dynamic programming. 404 405 $ dp_{i,j} = \text{number of arrays with sum $i$ and last element $j$} $ $ \displaystyle dp_{i, j} = \sum_{p=1}^{\min({\lfloor \frac{i}{j} \rfloor},\, k-j+1)}{dp_{i - j \cdot p,p}} $ 406 407 The key observation is that we only have to iterate $p$ up to $\lfloor \frac{i}{j} \rfloor$ (since if $p$ is any greater, $j \cdot p$ will exceed $i$). At $j=1$, we will iterate over at most $\lfloor \frac{i}{1} \rfloor$ values of $p$. At $j=2$, we will iterate over at most $\lfloor \frac{i}{2} \rfloor$ values of $p$. In total, at each $i$, we will iterate over at most $\lfloor \frac{i}{1} \rfloor + \lfloor \frac{i}{2} \rfloor +\cdots + \lfloor \frac{i}{i} \rfloor \approx i \log i$ values of $p$. Thus, the time complexity of our solution is $O(nk\log n)$. 408 409 **Code** 410 411 ``` 412 #include <bits/stdc++.h> 413 using namespace std; 414 415 const int md = 998244353; 416 417 void solve(){ 418 int n, k; 419 cin >> n >> k; 420 421 int dp[n + 1][k + 1] = {}; 422 int ans = 0; 423 424 fill(dp[0] + 1, dp[0] + k + 1, 1); 425 426 for (int sum = 1; sum <= n; sum++){ 427 for (int cur = 1; cur <= k; cur++){ 428 for (int prv = 1; cur * prv <= sum and cur + prv - 1 <= k; prv++) 429 dp[sum][cur] = (dp[sum][cur] + dp[sum - cur * prv][prv]) % md; 430 431 if (sum == n) 432 ans = (ans + dp[sum][cur]) % md; 433 } 434 } 435 cout<<ans<<"\n"; 436 } 437 438 int main(){ 439 ios_base::sync_with_stdio(0); cin.tie(0); 440 int tc; 441 cin >> tc; 442 443 while (tc--) 444 solve(); 445 } 446 ``` 447 448 ##### [1920F1 - Smooth Sailing (Easy Version)](/contest/1920/problem/F1 "Codeforces Round 919 (Div. 2)") 449 450 **Hint 1** 451 452 Use the fact that a good some path $p$ fully encircles the island if it is impossible to go from an island cell to a cell on the border by only travelling to adjacent or diagonal cells without touching a cell on path $p$. 453 454 **Hint 2** 455 456 Binary search! 457 458 **Solution** 459 460 For each non-island cell $(i, j)$, let $d_{i,j}$ be the minimum Manhattan distance of cell $(i, j)$ to an underwater volcano. We can find all $d_{i,j}$ with a multisource BFS from all underwater volcanos. The danger of a round trip is the smallest value of $d_{u,v}$ over all $(u, v)$ in the path. 461 462 For each query, binary search on the answer $k$ — we can only visit cell ($i, j$) if $d_{i,j} \geq k$. Now, let's **mark** all cells ($i, j$) ($d_{i,j} \geq k$) **reachable** from ($x, y$). There exists a valid round trip if it is not possible to go from an island cell to a border cell without touching a **marked** cell. 463 464 The time complexity of this solution is $O(nm \log{(n+m)})$. 465 466 **Code** 467 468 ``` 469 #include <bits/stdc++.h> 470 using namespace std; 471 472 const int mx = 3e5 + 5; 473 const int diAdj[4] = {-1, 0, 1, 0}, djAdj[4] = {0, -1, 0, 1}; 474 const int diDiag[8] = {0, 0, -1, 1, -1, -1, 1, 1}, djDiag[8] = {-1, 1, 0, 0, -1, 1, 1, -1}; 475 476 int n, m, q, islandi, islandj; string A[mx]; vector<int> dist[mx]; vector<bool> reachable[mx], islandVis[mx]; queue<pair<int, int>> bfsQ; 477 478 bool inGrid(int i, int j){ 479 return i >= 0 and i < n and j >= 0 and j < m; 480 } 481 bool onBorder(int i, int j){ 482 return i == 0 or i == n - 1 or j == 0 or j == m - 1; 483 } 484 void getReach(int i, int j, int minVal){ 485 if (!inGrid(i, j) or reachable[i][j] or dist[i][j] < minVal or A[i][j] == '#') 486 return; 487 488 reachable[i][j] = true; 489 490 for (int dir = 0; dir < 4; dir++) 491 getReach(i + diAdj[dir], j + djAdj[dir], minVal); 492 } 493 bool reachBorder(int i, int j){ 494 if (!inGrid(i, j) or reachable[i][j] or islandVis[i][j]) 495 return false; 496 497 if (onBorder(i, j)) 498 return true; 499 500 islandVis[i][j] = true; 501 502 bool ok = false; 503 for (int dir = 0; dir < 8; dir++) 504 ok |= reachBorder(i + diDiag[dir], j + djDiag[dir]); 505 return ok; 506 } 507 bool existsRoundTrip(int x, int y, int minVal){ 508 // Reset 509 for (int i = 0; i < n; i++){ 510 reachable[i] = vector<bool>(m, false); 511 islandVis[i] = vector<bool>(m, false); 512 } 513 // Get all valid cells you can reach from (x, y) 514 getReach(x, y, minVal); 515 516 // Check if the valid cells you can reach from (x, y) blocks the island from the border 517 return !reachBorder(islandi, islandj); 518 } 519 520 int main(){ 521 ios_base::sync_with_stdio(0); cin.tie(0); 522 cin >> n >> m >> q; 523 524 for (int i = 0; i < n; i++){ 525 cin >> A[i]; 526 dist[i] = vector<int>(m, 1e9); 527 528 for (int j = 0; j < m; j++){ 529 if (A[i][j] == 'v'){ 530 dist[i][j] = 0; 531 bfsQ.push({i, j}); 532 } 533 if (A[i][j] == '#'){ 534 islandi = i; 535 islandj = j; 536 } 537 } 538 } 539 540 // Multisource BFS to find min distance to volcano 541 while (bfsQ.size()){ 542 auto [i, j] = bfsQ.front(); bfsQ.pop(); 543 544 for (int dir = 0; dir < 4; dir++){ 545 int ni = i + diAdj[dir], nj = j + djAdj[dir]; 546 547 if (inGrid(ni, nj) and dist[i][j] + 1 < dist[ni][nj]){ 548 dist[ni][nj] = dist[i][j] + 1; 549 bfsQ.push({ni, nj}); 550 } 551 } 552 } 553 while (q--){ 554 int x, y; 555 cin >> x >> y; 556 x--; y--; 557 558 int L = 0, H = n + m; 559 while (L < H){ 560 int M = (L + H + 1) / 2; 561 existsRoundTrip(x, y, M) ? L = M : H = M - 1; 562 } 563 cout<<L<<"\n"; 564 } 565 } 566 ``` 567 568 ##### [1920F2 - Smooth Sailing (Hard Version)](/contest/1920/problem/F2 "Codeforces Round 919 (Div. 2)") 569 570 **Hint 1** 571 572 How do we check if a point is inside a polygon using a ray? 573 574 **Hint 2** 575 576 If u draw line from island cell extending all the way right, an optimal round trip will cross this line an odd number of times. 577 578  579 580 **Hint 3** 581 582 What can your state be? How can we simplify this problem down into finding the path that maximizes the minimum node? How can we solve this classic problem? 583 584 **Solution** 585 586 For each non-island cell $(i, j)$, let $d_{i,j}$ be the minimum Manhattan distance of cell $(i, j)$ to an underwater volcano. We can find all $d_{i,j}$ with a multisource BFS from all underwater volcanos. The danger of a round trip is the smallest value of $d_{u,v}$ over all $(u, v)$ in the path. 587 588 Consider any island cell. We can take inspiration from how we check whether a point is in a polygon — if a point is inside the polygon then a ray starting from the point and going in any direction will intersect the polygon an odd number of times. Draw an imaginary line along the top border of the cell and extend it all the way to the right of the grid. 589 590  591 592 We can observe that **an optimal round trip will always cross the line an odd number of times.** 593 594 Using this observation, we can let our state be $(\text{row}, \, \text{column}, \, \text{parity of the number of times we crossed the line})$. Naively, we can binary search for our answer and BFS to check if $(x, y, 0)$ and $(x, y, 1)$ are connected. This solves the easy version of the problem. 595 596 To fully solve this problem, we can add states (and their corresponding edges to already added states) one at a time from highest $d$ to lowest $d$. For each query $(x, y)$, we want to find the first time when $(x, y, 0)$ and $(x, y, 1)$ become connected. This is a classic DSU with small to large merging problem. In short, we drop a token labeled with the index of the query at both $(x, y, 0)$ and $(x, y, 1)$. Each time we merge, we also merge the sets of tokens small to large and check if merging has caused two tokens of the same label to be in the same component. The time complexity of our solution is $O(nm \log{(nm)} + q\log^2 q)$ with the $\log{(nm)}$ coming from sorting the states or edges. Note that there exists a $O((nm \cdot \alpha{(nm)} + q) \cdot \log{(n+m)})$ parallel binary search solution as well as a $O(nm \log{(nm)} + q\log{(nm)})$ solution that uses LCA queries on the Kruskal's reconstruction tree or min path queries on the MSTs. In fact, with offline LCA queries, we can reduce the complexity to $O(nm \cdot \alpha{(nm)} + q)$. 597 598 **Code (small to large)** 599 600 ``` 601 #include <bits/stdc++.h> 602 using namespace std; 603 604 const int mx = 3e5 + 5, di[4] = {-1, 0, 1, 0}, dj[4] = {0, -1, 0, 1}; 605 606 int n, m, q, linei, linej, par[mx * 2], ans[mx]; string A[mx]; 607 queue<pair<int, int>> bfsQ; vector<int> dist[mx]; vector<array<int, 3>> edges; set<int> S[mx * 2]; 608 609 int enc(int i, int j, bool crossParity){ 610 return i * m + j + crossParity * n * m; 611 } 612 bool inGrid(int i, int j){ 613 return i >= 0 and i < n and j >= 0 and j < m; 614 } 615 int getR(int i){ 616 return i == par[i] ? i : par[i] = getR(par[i]); 617 } 618 void merge(int a, int b, int w){ 619 a = getR(a); b = getR(b); 620 621 if (a == b) 622 return; 623 624 if (S[a].size() > S[b].size()) 625 swap(S[a], S[b]); 626 627 for (int i : S[a]){ 628 if (S[b].count(i)){ 629 ans[i] = w; 630 S[b].erase(i); 631 } 632 else 633 S[b].insert(i); 634 } 635 par[a] = b; 636 } 637 638 int main(){ 639 ios_base::sync_with_stdio(0); cin.tie(0); 640 cin >> n >> m >> q; 641 642 for (int i = 0; i < n; i++){ 643 cin >> A[i]; 644 for (int j = 0; j < m; j++){ 645 dist[i].push_back(1e9); 646 647 if (A[i][j] == 'v'){ 648 dist[i][j] = 0; 649 bfsQ.push({i, j}); 650 } 651 if (A[i][j] == '#'){ 652 linei = i; 653 linej = j; 654 } 655 } 656 } 657 for (int i = 0; i < q; i++){ 658 int x, y; cin >> x >> y; 659 x--; y--; 660 S[enc(x, y, 0)].insert(i); 661 S[enc(x, y, 1)].insert(i); 662 } 663 664 // Multisource BFS to find min distance to volcano 665 while (bfsQ.size()){ 666 auto [i, j] = bfsQ.front(); bfsQ.pop(); 667 668 for (int dir = 0; dir < 4; dir++){ 669 int ni = i + di[dir], nj = j + dj[dir]; 670 671 if (inGrid(ni, nj) and dist[i][j] + 1 < dist[ni][nj]){ 672 dist[ni][nj] = dist[i][j] + 1; 673 bfsQ.push({ni, nj}); 674 } 675 } 676 } 677 678 // Get the edges 679 for (int i = 0; i < n; i++){ 680 for (int j = 0; j < m; j++){ 681 // Look at cells to the up and left (so dir = 0 and dir = 1) 682 for (int dir = 0; dir < 2; dir++){ 683 int ni = i + di[dir], nj = j + dj[dir]; 684 685 if (inGrid(ni, nj) and A[i][j] != '#' and A[ni][nj] != '#'){ 686 int w = min(dist[i][j], dist[ni][nj]); 687 688 // Crosses the line 689 if (i == linei and ni == linei - 1 and j > linej){ 690 edges.push_back({w, enc(i, j, 0), enc(ni, nj, 1)}); 691 edges.push_back({w, enc(i, j, 1), enc(ni, nj, 0)}); 692 } 693 // Doesn't cross the line 694 else{ 695 edges.push_back({w, enc(i, j, 0), enc(ni, nj, 0)}); 696 edges.push_back({w, enc(i, j, 1), enc(ni, nj, 1)}); 697 } 698 } 699 } 700 } 701 } 702 703 // Sort in reverse and merge to solve offline 704 sort(edges.begin(), edges.end(), greater<array<int, 3>>()); 705 706 // Init DSU stuff 707 iota(par, par + mx * 2, 0); 708 709 for (auto [w, u, v] : edges) 710 merge(u, v, w); 711 712 for (int i = 0; i < q; i++) 713 cout<<ans[i]<<"\n"; 714 } 715 ``` 716 717 **Code (LCA queries)** 718 719 ``` 720 #include <bits/stdc++.h> 721 using namespace std; 722 723 const int mx = 3e5 + 5, di[4] = {-1, 0, 1, 0}, dj[4] = {0, -1, 0, 1}; 724 725 int n, m, q, id, linei, linej, par[mx * 4], dep[mx], up[mx * 4][21], val[mx * 4]; 726 string A[mx]; queue<pair<int, int>> bfsQ; vector<int> dist[mx], adj[mx * 4]; vector<array<int, 3>> edges; 727 728 int enc(int i, int j, bool crossParity){ 729 // Note that nodes are 1 indexed 730 return 1 + i * m + j + crossParity * n * m; 731 } 732 bool inGrid(int i, int j){ 733 return i >= 0 and i < n and j >= 0 and j < m; 734 } 735 int getR(int i){ 736 return i == par[i] ? i : par[i] = getR(par[i]); 737 } 738 void merge(int a, int b, int w){ 739 a = getR(a); b = getR(b); 740 741 if (a == b) 742 return; 743 744 adj[id].push_back(a); 745 adj[id].push_back(b); 746 val[id] = w; 747 748 par[a] = par[b] = id; 749 id++; 750 } 751 void dfs(int i){ 752 for (int l = 1; l < 21; l++) 753 up[i][l] = up[up[i][l - 1]][l - 1]; 754 755 for (int to : adj[i]){ 756 if (to != up[i][0]){ 757 up[to][0] = i; 758 dep[to] = dep[i] + 1; 759 dfs(to); 760 } 761 } 762 } 763 int qry(int x, int y){ 764 if (dep[x] < dep[y]) 765 swap(x, y); 766 767 for (int l = 20, jmp = dep[x] - dep[y]; ~l; l--){ 768 if (jmp & (1 << l)){ 769 x = up[x][l]; 770 } 771 } 772 if (x == y) 773 return val[x]; 774 775 for (int l = 20; ~l; l--){ 776 if (up[x][l] != up[y][l]){ 777 x = up[x][l]; 778 y = up[y][l]; 779 } 780 } 781 return val[up[x][0]]; 782 } 783 784 int main(){ 785 ios_base::sync_with_stdio(0); cin.tie(0); 786 cin >> n >> m >> q; 787 788 for (int i = 0; i < n; i++){ 789 cin >> A[i]; 790 for (int j = 0; j < m; j++){ 791 dist[i].push_back(1e9); 792 793 if (A[i][j] == 'v'){ 794 dist[i][j] = 0; 795 bfsQ.push({i, j}); 796 } 797 if (A[i][j] == '#'){ 798 linei = i; 799 linej = j; 800 } 801 } 802 } 803 804 // Multisource BFS to find min distance to volcano 805 while (bfsQ.size()){ 806 auto [i, j] = bfsQ.front(); bfsQ.pop(); 807 808 for (int dir = 0; dir < 4; dir++){ 809 int ni = i + di[dir], nj = j + dj[dir]; 810 811 if (inGrid(ni, nj) and dist[i][j] + 1 < dist[ni][nj]){ 812 dist[ni][nj] = dist[i][j] + 1; 813 bfsQ.push({ni, nj}); 814 } 815 } 816 } 817 818 // Get the edges 819 for (int i = 0; i < n; i++){ 820 for (int j = 0; j < m; j++){ 821 // Look at cells to the up and left (so dir = 0 and dir = 1) 822 for (int dir = 0; dir < 2; dir++){ 823 int ni = i + di[dir], nj = j + dj[dir]; 824 825 if (inGrid(ni, nj) and A[i][j] != '#' and A[ni][nj] != '#'){ 826 int w = min(dist[i][j], dist[ni][nj]); 827 828 // Crosses the line 829 if (i == linei and ni == linei - 1 and j > linej){ 830 edges.push_back({w, enc(i, j, 0), enc(ni, nj, 1)}); 831 edges.push_back({w, enc(i, j, 1), enc(ni, nj, 0)}); 832 } 833 // Doesn't cross the line 834 else{ 835 edges.push_back({w, enc(i, j, 0), enc(ni, nj, 0)}); 836 edges.push_back({w, enc(i, j, 1), enc(ni, nj, 1)}); 837 } 838 } 839 } 840 } 841 } 842 843 // We merge from largest w to smallest 844 sort(edges.begin(), edges.end(), greater<array<int, 3>>()); 845 846 // Init DSU stuff 847 id = n * m * 2 + 1; 848 iota(par, par + mx * 4, 0); 849 850 // Merge 851 for (auto [w, u, v] : edges) 852 merge(u, v, w); 853 854 // DFS to construct the Kruskal's reconstruction trees 855 for (int i = n * m * 4; i; i--) 856 if (!up[i][0]) 857 dfs(i); 858 859 // Answer queries via LCA queries 860 for (int i = 0; i < q; i++){ 861 int x, y; cin >> x >> y; 862 x--; y--; 863 cout<<qry(enc(x, y, 0), enc(x, y, 1))<<"\n"; 864 } 865 } 866 ```