codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![Image for observation](/predownloaded/2e/59/2e59e89f73fcc9aed8c2cdc05fca8b1421765a8e.png)
    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 ![Image for observation](/predownloaded/2e/59/2e59e89f73fcc9aed8c2cdc05fca8b1421765a8e.png)
    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 ```