codeforces-scrape

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

1630.md (44326B)


      1 Source: https://codeforces.com/blog/entry/99384
      2 
      3 ### [1631A - Min Max Swap](/contest/1631/problem/A "Codeforces Round 768 (Div. 2)")
      4 
      5 Author: [humbertoyusta](/profile/humbertoyusta "Master humbertoyusta")
      6 
      7 **Hint 1**
      8 
      9 Think about how $max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$ will contribute to the answer.
     10 
     11 **Hint 2**
     12 
     13 The maximum of one array is always $max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$. How should you minimize then?
     14 
     15 **Solution**
     16 
     17 Let $m_1 = \max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$. The answer will always be $m_1 \cdot m_2$ where $m_2$ is the maximum of the array that does not contain $m_1$.
     18 
     19 Since $m_1$ is fixed, the problem can be reduced to minimize $m_2$, that is, minimize the maximum of the array that does not contain the global maximum.
     20 
     21 WLOG assume that the global maximum will be in the array $b$, we can swap elements at each index $x$ such that $a_x \gt b_x$, ending with $a_i \leq b_i$ for all $i$. It can be shown that the maximum of array $a$ is minimized in this way.
     22 
     23 Time complexity: $O(n)$
     24 
     25 **Code**
     26 
     27 ```
     28 #include<bits/stdc++.h>
     29 using namespace std;
     30  
     31 int calc_max(vector<int> a){
     32     int res = 0;
     33     for( auto i : a )
     34         res = max( res , i );
     35     return res;
     36 }
     37  
     38 int main(){
     39     int tc;
     40     cin >> tc;
     41     while( tc-- ){
     42         int n;
     43         cin >> n;
     44  
     45         vector<int> a(n), b(n);
     46         for( auto &i : a )
     47             cin >> i;
     48         for( auto &i : b )
     49             cin >> i;
     50  
     51         for(int i=0; i<n; i++)
     52             if( a[i] > b[i] )
     53                 swap( a[i] , b[i] );
     54  
     55         cout << calc_max(a) * calc_max(b) << '\n';
     56     }
     57 }
     58 ```
     59 
     60 ### [1631B - Fun with Even Subarrays](/contest/1631/problem/B "Codeforces Round 768 (Div. 2)")
     61 
     62 Author: [humbertoyusta](/profile/humbertoyusta "Master humbertoyusta")
     63 
     64 **Hint 1**
     65 
     66 It is not possible to modify $a_n$ using the given operation.
     67 
     68 **Hint 2**
     69 
     70 Think about the leftmost $x$ such that $a_x \neq a_n$.
     71 
     72 **Solution**
     73 
     74 For simplicity, let $b_1, b_2, ..., b_n = a_n, a_{n-1}, ..., a_1$ (let $b$ be $a$ reversed). The operation transforms to select a subarray $[l, r]$ of length $2\cdot{k}$, so $k = \frac{r-l+1}{2}$, then for all $i$ such that $0 \leq i \lt k$, set $b_{l+k+i} = b_{l+i}$.
     75 
     76 $b_1$ can not be changed with the given operation. That reduces the problem to make all elements equal to $b_1$.
     77 
     78 Let $x$ be the rightmost index such that for all $1 \leq i \leq x$, $b_i = b_1$ holds.
     79 
     80 The problem will be solved when $x = n$.
     81 
     82 If an operation is applied with $l + k \gt x + 1$, $b_{x+1}$ will not change and $x$ will remain the same.
     83 
     84 The largest range with $l + k \leq x + 1$ is $[1, 2\cdot{x}]$, applying an operation to it will lead to $b_{x+1}, b_{x+2}, ..., b_{2\cdot{x}} = b_1, b_2, ..., b_x$, so $x$ will become at least $2\cdot{x}$ and there is not any other range that will lead to a bigger value of $x$.
     85 
     86 If $2\cdot{x} \gt n$, it is possible to apply the operation on $[x-(n-x)+1,n]$, after applying it $b_{x+1}, ..., b_n = b_{x-(n-x)+1}, ..., b_x$ and all elements will become equal.
     87 
     88 The problem can now be solved by repeatedly finding $x$ and applying the operation on $[1, 2\cdot{x}]$ or on $[x-(n-x)+1,n]$ if $2\cdot{x} \gt n$.
     89 
     90 Since $x$ will become at least $2\cdot{x}$ in each operation but the last one, the naive implementation will take $O(n\log{n})$, however, it is easy to implement it in $O(n)$.
     91 
     92 **Code O(nlogn)**
     93 
     94 ```
     95 #include<bits/stdc++.h>
     96 using namespace std;
     97 
     98 int find_rightmost_x(vector<int> &b){
     99     int n = (int)b.size() - 1;
    100 
    101     int x = 1;
    102     while( x + 1 <= n && b[x+1] == b[1] )
    103         x ++;
    104 
    105     return x;
    106 }
    107 
    108 void apply(vector<int> &b,int l,int r){
    109     int k = ( r - l + 1 ) / 2;
    110     for(int i=0; i<k; i++)
    111         b[l+k+i] = b[l+i];
    112 }
    113 
    114 int main(){
    115 
    116     int tc;
    117     cin >> tc;
    118     while( tc-- ){
    119 
    120         int n;
    121         cin >> n;
    122 
    123         vector<int> a(n+1);
    124         for(int i=1; i<=n; i++)
    125             cin >> a[i];
    126 
    127         vector<int> b = a;
    128         reverse(b.begin()+1,b.end());
    129 
    130         int ans = 0;
    131         while( find_rightmost_x(b) != n ){
    132             int x = find_rightmost_x(b);
    133             if( 2 * x > n ){
    134                 apply(b,x-(n-x)+1,n);
    135                 ans ++;
    136             }
    137             else{
    138                 apply(b,1,2*x);
    139                 ans ++;
    140             }
    141         }
    142         cout << ans << '\n';
    143     }
    144 
    145     return 0;
    146 }
    147 ```
    148 
    149 **Code O(n)**
    150 
    151 ```
    152 #include <bits/stdc++.h>
    153 using namespace std;
    154 
    155 int main()
    156 {
    157     int tc;
    158     cin >> tc;
    159     while(tc--)
    160     {
    161         int n;
    162         cin >> n;
    163 
    164         vector<int> a(n+1);
    165         for(int i=1; i<=n; i++)
    166             cin >> a[i];
    167 
    168         vector<int> b = a;
    169         reverse(b.begin()+1,b.end());
    170 
    171         int ans = 0, x = 1;
    172 
    173         while( x < n )
    174         {
    175             if( b[x+1] == b[1] ){
    176                 x ++;
    177                 continue;
    178             }
    179             ans ++;
    180             x *= 2;
    181         }
    182 
    183         cout << ans << '\n';
    184     }
    185 
    186     return 0;
    187 }
    188 ```
    189 
    190 ### [1630A - And Matching](/contest/1630/problem/A "Codeforces Round 768 (Div. 1)")
    191 
    192 Author: [humbertoyusta](/profile/humbertoyusta "Master humbertoyusta")
    193 
    194 **Hint 1**
    195 
    196 Try to find a pairing such that $\sum\limits_1^{n/2}{a_i\&{b_i}}=0$
    197 
    198 **Hint 2**
    199 
    200 Try to find a pairing for $k \gt 0$ by changing only a few elements from the previous pairing.
    201 
    202 **Solution**
    203 
    204 **Constructive approach (easier)**
    205 
    206 Let's define $c(x)$, the compliment of $x$, as the number $x$ after changing all bits 0 to 1 and vice versa, for example $c(110010_2) = 001101_2$.
    207 
    208 It can be shown that $c(x) = x\oplus{(n-1)}$. Remember that $n-1 = 11...11_2$ since $n$ is a power of $2$.
    209 
    210 We will separate the problem into three cases.
    211 
    212 * **Case $k = 0$:**
    213 
    214   In this case it is possible to pair $x$ with $c(x)$ for $0\leq{x} \lt {\frac{n}{2}}$, getting $\sum\limits_{x=0}^{\frac{n}{2}-1} {x\&{c(x)}} = 0$.
    215 * **Case $0 \lt k \lt n-1$:**
    216 
    217   In this case it is possible to pair each element with its compliment except $0$, $k$, $c(k)$ and $n-1$, and then pair $0$ with $c(k)$ and $k$ with $n-1$, $0\& c(k) = 0$ and $k\& (n-1) = k$.
    218 * **Case $k = n-1$:**
    219 
    220   There are many constructions that work in this case, if $n=4$ there is no solution, if $n \geq8$ it is possible to construct the answer in the following way:
    221 
    222   It is possible to pair $n-1$ with $n-2$, $n-3$ with $1$, $0$ with $2$ and all other elements with their compliments.
    223 
    224   + $(n-1)\&{(n-2)}=n-2$, for example $1111_2\&{1110_2}=1110_2$
    225   + $(n-3)\&{1}=1$, for example $1101_2\&{0001_2}=0001_2$
    226   + $0\&{2}=0$, for example $0000_2\&{0010_2}=0000_2$
    227   + All other elements can be paired with their complements and $x\&{c(x)}=0$
    228 
    229   Note that $(n-2)+1+0+0+ ... +0=n-1$.
    230 
    231 Each case can be implemented in $O(n)$.
    232 
    233 **Code**
    234 
    235 ```
    236 #include<bits/stdc++.h>
    237 using namespace std;
    238 
    239 int c(int x,int n){
    240     return ( x ^ ( n - 1 ) );
    241 }
    242 
    243 int main(){
    244 
    245     int tc;
    246     cin >> tc;
    247     while( tc-- ){
    248 
    249         int n, k;
    250         cin >> n >> k;
    251 
    252         vector<int> a(n/2), b(n/2);
    253 
    254         if( k == 0 ){
    255             for(int i=0; i<n/2; i++){
    256                 a[i] = i;
    257                 b[i] = c(i,n);
    258             }
    259         }
    260 
    261         if( k > 0 && k < n - 1 ){
    262             int small_k = min( k , c(k,n) );
    263             for(int i=0; i<n/2; i++){
    264                 if( i != 0 && i != small_k ){
    265                     a[i] = i;
    266                     b[i] = c(i,n);
    267                 }
    268             }
    269 
    270             a[0] = 0;
    271             b[0] = c(k,n);
    272 
    273             a[small_k] = k;
    274             b[small_k] = n - 1;
    275         }
    276 
    277         if( k == n - 1 ){
    278 
    279             if( n == 4 ){
    280                 cout << -1 << '\n';
    281                 continue;
    282             }
    283 
    284             a[0] = n - 2;
    285             b[0] = n - 1;
    286 
    287             a[1] = 1;
    288             b[1] = n - 3;
    289 
    290             a[2] = 0;
    291             b[2] = 2;
    292 
    293             for(int i=3; i<n/2; i++){
    294                 a[i] = i;
    295                 b[i] = c(i,n);
    296             }
    297         }
    298 
    299         for(int i=0; i<n/2; i++){
    300             cout << a[i] << ' ' << b[i] << '\n';
    301         }
    302     }
    303 
    304     return 0;
    305 }
    306 ```
    307 
    308 **Greedy approach (harder)**
    309 
    310 Let's define $a$ such that $a_i = i-1$ for $1\le i \le \frac{n}{2}$ and $b$ such that $b_i = c(a_i)$ for $1\le i \le \frac{n}{2}$.
    311 
    312 For example, for $n = 16$ they are:
    313 
    314 $a = [0000_2, 0001_2, 0010_2, 0011_2, 0100_2, 0101_2, 0110_2, 0111_2]$ $b = [1111_2, 1110_2, 1101_2, 1100_2, 1011_2, 1010_2, 1001_2, 1000_2]$
    315 
    316 | 1st element to swap | 2nd element to swap | $\sum\limits_{i=1}^{n/2}{ a_i\&{b_i}}$ after swap |
    317 | --- | --- | --- |
    318 | none | none | $0$ |
    319 | $b_1$ | $b_2$ | $1$ |
    320 | $b_2$ | $b_3$ | $3$ |
    321 | $b_3$ | $b_4$ | $1$ |
    322 | $b_4$ | $b_5$ | $7$ |
    323 | $b_5$ | $b_6$ | $1$ |
    324 | $b_6$ | $b_7$ | $3$ |
    325 | $b_7$ | $b_8$ | $1$ |
    326 
    327 All swaps are independent and are applied to the original $a$ and $b$.
    328 
    329 After swapping two adjacent elements of $b$ (that have not been swapped) the sum will change in $2^x-1$ for some positive integer $x$.
    330 
    331 Then it is possible to solve the problem by repeatedly swapping the pair that maximizes $\sum\limits_{i=1}^{n/2}{ a_i\&{b_i}}$ after the swap such that $\sum\limits_{i=1}^{n/2}{ a_i\&{b_i}} \leq k$ is held and none of its elements have been swapped yet.
    332 
    333 However, this only works for all values of $k$ if $n \geq 32$, the case $n \leq 16$ can be handled with brute force.
    334 
    335 **Randomized approach (harder)**
    336 
    337 Please read the previous solution. Arrays $a$ and $b$ from it will also be used here.
    338 
    339 It is possible to start with $a$ and $b$ and repeatedly select and index $x$ randomly and swap $b_x$ with $b_{x+1}$ if $\sum\limits_{i=1}^{n/2}{a_i\&b_i} \leq k$ holds until $\sum\limits_{i=1}^{n/2}{a_i\&b_i} = k$.
    340 
    341 We have no proof of this solution but it was stressed against each possible input to the problem and it worked quickly for $n \geq 16$, the case $n \leq 8$ can be handled with brute force.
    342 
    343 ### [1630B - Range and Partition](/contest/1630/problem/B "Codeforces Round 768 (Div. 1)")
    344 
    345 Author: [humbertoyusta](/profile/humbertoyusta "Master humbertoyusta")
    346 
    347 **Hint 1**
    348 
    349 Focus on how to solve the problem for a fixed interval $[x,y]$
    350 
    351 **Hint 2**
    352 
    353 Think about the numbers inside the interval as $+1$, and the other numbers as $-1$
    354 
    355 **Hint 3**
    356 
    357 Try to relate a partition into valid subarrays with an increasing sequence of the prefix sums array
    358 
    359 **Hint 4**
    360 
    361 Note that if some value $x$ ($x \gt 0$) appears on the prefix sums array, $x-1$ appears before since the absolute value of the elements is $1$ (+1 and -1)
    362 
    363 **Solution**
    364 
    365 Focus on how to solve the problem for a fixed interval $[x,y]$:
    366 
    367 Let us define an array $b$ such that $b_i = 1$ if $x \le a_i \le y$ or $b_i = -1$ otherwise, for all $1\le i\le n$.
    368 
    369 Let's define $psum_i$ as $b_1 + b_2 + ... + b_i$.
    370 
    371 We need to find a partition on $k$ subarrays with positive sum of $b_i$.
    372 
    373 The sum of a subarray $[l,r]$ is $b_l+b_{l+1}+...+b_r = psum_r-psum_{l-1}$. Then a subarray is valid if $psum_r \gt psum_{l-1}$.
    374 
    375 We need to find an increasing sequence of $psum$ of length $k+1$ starting at $0$ and ending at $n$.
    376 
    377 Let's define $firstocc_x$ to be the first occurrence of the integer $x$ in $psum$.
    378 
    379 If $psum_n \lt k$ there will be no valid sequence, otherwise the sequence $0, firstocc_1, firstocc_2, ..., firstocc_{k-1}, n$ will satisfy all constraints.
    380 
    381 Note that, since $|psum_i-psum_{i-1}| = 1$, for $i \gt 0$, then $firstocc_v$ exists and $firstocc_v \lt firstocc_{v+1}$ for $0\leq v \leq psum_n$.
    382 
    383 This solves the problem for a fixed interval.
    384 
    385 It remains to find the smallest interval $[x,y]$ such that $psum_n \geq k$.
    386 
    387 For a given interval $[x,y]$, since $psum_n = b_1 + b_2 + ... + b_n$, $psum_n$ will be equal to the number of elements of $a$ inside the interval minus the number of elements outside.
    388 
    389 Then for each $x$, it is possible to find the smallest $y$ such that $psum_n \geq k$ using binary search or two pointers.
    390 
    391 It is also possible to note that:
    392 
    393 $psum_n \geq k$ $\sum\limits_{i=1}^n b_i \geq k$ $\sum\limits_{i=1}^n (-1 + 2\cdot [x\le a_i\le y]) \geq k$ $\sum\limits_{i=1}^n [x\le a_i\le y] \geq \lceil{\frac{k+n}{2}}\rceil$
    394 
    395 We need to find the smallest interval with at least $\lceil{\frac{k+n}{2}}\rceil$ inside, let $A$ be the array $a$ sorted, the answer is the minimum interval among all intervals $[A_i, A_{i+\lceil{\frac{k+n}{2}}\rceil-1}]$ for $1 \leq i \leq n - \lceil{\frac{k+n}{2}}\rceil+1$.
    396 
    397 Complexity: $O(n\log{n})$ if solved with the previous formula or binary search, or $O(n)$ is solved with two pointers.
    398 
    399 **Code (with the previous formula)**
    400 
    401 ```
    402 #include<bits/stdc++.h>
    403 using namespace std;
    404  
    405 int main() {
    406  
    407     int tc;
    408     cin >> tc;
    409     while( tc-- ){
    410  
    411         int n, k;
    412         cin >> n >> k;
    413  
    414         vector<int> a(n), sorted_a(n);
    415         for(int i=0; i<n; i++){
    416             cin >> a[i];
    417             sorted_a[i] = a[i];
    418         }
    419  
    420         sort(sorted_a.begin(),sorted_a.end());
    421  
    422         int req_sum = ( n + k + 1 ) / 2;
    423  
    424         pair<int,pair<int,int>> ans = { n + 1 , { -1 , -1 } };
    425  
    426         for(int i=0; i+req_sum-1<n; i++)
    427             ans = min( ans , { sorted_a[i+req_sum-1] - sorted_a[i] , { sorted_a[i] , sorted_a[i+req_sum-1] } } );
    428  
    429         cout << ans.second.first << ' ' << ans.second.second << '\n';
    430  
    431         int subarrays_found = 0, curr_sum = 0;
    432         int last_uncovered = 1;
    433  
    434         for(int i=0; i<n; i++){
    435  
    436             if( a[i] >= ans.second.first && a[i] <= ans.second.second ) curr_sum ++;
    437                 else curr_sum --;
    438  
    439             if( curr_sum > 0 && subarrays_found + 1 < k ){
    440  
    441                 cout << last_uncovered << ' ' << ( i + 1 ) << '\n';
    442                 last_uncovered = i + 2;
    443  
    444                 subarrays_found ++;
    445                 curr_sum = 0;
    446             }
    447         }
    448  
    449         subarrays_found ++;
    450         cout << last_uncovered << ' ' << n << '\n';
    451  
    452     }
    453  
    454     return 0;
    455 }
    456 ```
    457 
    458 ### [1630C - Paint the Middle](/contest/1630/problem/C "Codeforces Round 768 (Div. 1)")
    459 
    460 Author: [humbertoyusta](/profile/humbertoyusta "Master humbertoyusta")
    461 
    462 **Hint 1**
    463 
    464 Think about all occurrences of some element, what occurrences are important?
    465 
    466 **Hint 2**
    467 
    468 Think about the first and last occurrence of each element as a segment.
    469 
    470 **Hint 3**
    471 
    472 Think about the segments that at least one of its endpoints will end up with $c_i = 0$.
    473 
    474 **Solution**
    475 
    476 For each $x$ such that all the elements $a_1, a_2, ..., a_x$ are different from $a_{x+1}, a_{x+2}, ..., a_n$ it is impossible to apply an operation with some indices from the first part, and some other from the second one.
    477 
    478 Then it is possible to split the array in subarrays for each $x$ such that the previous condition holds, and sum the answers from all of them.
    479 
    480 Let's solve the problem independently for one of those subarrays, let's denote its length as $m$, the values of its elements as $a_1, ..., a_m$ and their colors as $c_1, ..., c_m$:
    481 
    482 For every tuple $(x, y, z)$ such that $1 \le x \lt y \lt z \le m$ and $a_x = a_y = a_z$ it is possible to apply an operation with indices $x, y$ and $z$. Then only the first and last occurrences of each element are important.
    483 
    484 For all pairs $(x, y)$ such that $1 \le x \lt y \le m$, $a_x = a_y$, $a_x$ is the first occurrence and $a_y$ the last occurrence of that value, a segment $[x, y]$ will be created.
    485 
    486 Let's denote the left border of a segment $i$ as $l_i$ and the right border as $r_i$.
    487 
    488 Let's say that a set of segments $S$ is connected if the union of its segments is the segment $[\min(l_i, \forall i\in{S}), \max(r_i, \forall i\in{S})]$.
    489 
    490 Instead of maximizing $\sum\limits_{i=1}^m{c_i}$, it is possible to focus on minimizing $\sum\limits_{i=1}^m{[c_i=0]}$.
    491 
    492 **Lemma 1:** If we have a connected set $S$, it is possible to apply some operations to its induced array to end up with at most $|S|+1$ elements with $c_i = 0$.
    493 
    494 **Proof**
    495 
    496 For each segment $x$ in $S$ if there exists a segment $y$ such that $l_y \lt l_x \lt r_x \lt r_y$, it is possible to apply the operation with indices $l_y, l_x, r_y$ and with $l_y, r_x, r_y$. Otherwise, add this segment to a set $T$.
    497 
    498 Then is possible to repeatedly select the leftmost segment of $T$ that have not been selected yet, and set the color of its right border to $1$, this will be always possible until we select the rightmost segment since $T$ is connected.
    499 
    500 In the end, all the left borders of the segments of $T$ will have $c_i = 0$, the same holds for the right border of the rightmost segment of $T$, which leads to a total of $|T|+1$ elements with $c_i = 0$, and $|T| \le |S|$.
    501 
    502 Let $X$ be a subarray that can be obtained by applying the given operation to the initial subarray any number of times.
    503 
    504 Let $S(X)$ be the set of segments that includes all segments $i$ such that $c[l_i] = 0$ or $c[r_i] = 0$ (or both), where $c[i]$ is the color of the $i$-th segment of the subarray $X$.
    505 
    506 **Lemma 2:** There is always an optimal solution in which $S(X)$ is connected.
    507 
    508 **Proof**
    509 
    510 Suppose $S(X)$ is not connected, if there are only two components of segments $A$ and $B$, there will always be a segment from $A$ to $B$ due to the way the subarray was formed.
    511 
    512 If $A$ or $B$ have some segment $x$ such that there exists a segment $y$ such that $l_y \lt l_x \lt r_x \lt r_y$ you can erase it by applying the operation with indices $l_y, l_x, r_y$ and with $l_y, r_x, r_y$. Then we can assume that $\sum\limits_{i\in A}{([c[l_i]=0]+[c[r_i]=0])} = |A|+1$ and similarly for $B$.
    513 
    514 The solution to $A$ before merging is $|A|+1$, the solution to $B$ is $|B|+1$, if we merge $A$ and $B$ with a segment we get a component $C$ of size $|A|+|B|+1$, and its answer will be $|A|+|B|+1+1$ (using \bf{lemma 1}), the case with more than two components is similar, then we can always merge the components without making the answer worse.
    515 
    516 Finally, the problem in each subarray can be reduced to find the smallest set (in number of segments), such that the union of its segments is the whole subarray. This can be computed with dp or sweep line.
    517 
    518 **DP solution**
    519 
    520 Let $dp[x]$ be the minimum size of a set such that the union of its segments is the segment $[1,x]$.
    521 
    522 To compute $dp$, process all the segments in increasing order of $r_i$, and compute the value of $dp[r_i] = \min(dp[l_i+1], dp[l_i+2], ..., dp[r_i-1]) + 1$.
    523 
    524 Then the solution to the subarray is $dp[m] + 1$, this $dp$ can be computed in $O(m\log{m})$ with segment tree.
    525 
    526 It is possible to compute a similar $dp$ to solve the problem for the whole array without splitting the array, the time complexity is $O(n\log{n})$.
    527 
    528 **Code**
    529 
    530 ```
    531 #include<bits/stdc++.h>
    532 using namespace std;
    533  
    534 template <typename Tnode,typename Tup>
    535 struct ST{
    536     vector<Tnode> st;
    537     int sz;
    538  
    539     ST(int n){
    540         sz = n;
    541         st.resize(4*n);
    542     }
    543  
    544     Tnode merge_(Tnode a, Tnode b){
    545         Tnode c;
    546         /// Merge a and b into c
    547         c = min( a , b );
    548         return c;
    549     }
    550  
    551     void update_node(int nod,Tup v){
    552         /// how v affects to st[nod]
    553         st[nod] = v;
    554     }
    555  
    556     void build(vector<Tnode> &arr){ build(1,0,sz-1,arr); }
    557  
    558     void build(int nod,int l,int r,vector<Tnode> &arr){
    559         if( l == r ){
    560             st[nod] = arr[l];
    561             return;
    562         }
    563         int mi = ( l + r ) >> 1;
    564             build((nod<<1),l,mi,arr);
    565             build((nod<<1)+1,mi+1,r,arr);
    566         st[nod] = merge_( st[(nod<<1)] , st[(nod<<1)+1] );
    567     }
    568  
    569     void update(int id,Tup v){ update(1,0,sz-1,id,v); }
    570  
    571     void update(int nod,int l,int r,int id,Tup v){
    572         if( l == r ){
    573             update_node(nod,v);
    574             return;
    575         }
    576         int mi = ( l + r ) >> 1;
    577         if( id <= mi ) update((nod<<1),l,mi,id,v);
    578             else update((nod<<1)+1,mi+1,r,id,v);
    579         st[nod] = merge_( st[(nod<<1)] , st[(nod<<1)+1] );
    580     }
    581  
    582     Tnode query(int l,int r){ return query(1,0,sz-1,l,r); }
    583  
    584     Tnode query(int nod,int l,int r,int x,int y){
    585  
    586         if( l >= x && r <= y ) return st[nod];
    587  
    588         int mi = ( l + r ) >> 1;
    589  
    590         if( y <= mi ) return query((nod<<1),l,mi,x,y);
    591  
    592         if( x > mi ) return query((nod<<1)+1,mi+1,r,x,y);
    593  
    594         return merge_( query((nod<<1),l,mi,x,y), query((nod<<1)+1,mi+1,r,x,y) );
    595     }
    596 };
    597  
    598 int main(){
    599  
    600     int n;
    601     cin >> n;
    602  
    603     vector<int> a(n), fst(n,-1), lst(n,-1);
    604     for(int i=0; i<n; i++){
    605         cin >> a[i];
    606         a[i] --;
    607         if( fst[a[i]] == -1 )
    608             fst[a[i]] = i;
    609         lst[a[i]] = i;
    610     }
    611  
    612     vector<pair<int,int>> segments;
    613     for(int i=0; i<n; i++)
    614         if( fst[i] != -1 )
    615             segments.push_back({lst[i]+1,fst[i]+1});
    616     sort(segments.begin(),segments.end());
    617  
    618     vector<int> dp(n+1,1000000007);
    619     dp[0] = 0;
    620  
    621     ST<int,int> st(n+1);
    622     st.build(dp);
    623     for( auto i : segments ){
    624         dp[i.first] = min( dp[i.first] , dp[i.second-1] + 1 + ( i.first != i.second ) );
    625         if( i.second + 1 <= i.first - 1 )
    626             dp[i.first] = min( dp[i.first] , st.query(i.second+1,i.first-1) + 1 );
    627         st.update(i.first,dp[i.first]);
    628     }
    629     cout << n - dp[n] << '\n';
    630  
    631     return 0;
    632 }
    633 ```
    634 
    635 **Sweep line solution**
    636 
    637 It is possible to create an event where a segment starts and an event where a segment ends.
    638 
    639 Then process the events in order and each time a segment ends, if it is the rightmost segment added, add to the solution the segment with maximum $r_i$ among the segments that $l_i$ is already processed.
    640 
    641 It is possible to modify the sweep line to solve the problem for the whole array without splitting the array, the time complexity is $O(n)$ or $O(n\log{n})$ depending on the implementation.
    642 
    643 ### [1630D - Flipping Range](/contest/1630/problem/D "Codeforces Round 768 (Div. 1)")
    644 
    645 Author: [humbertoyusta](/profile/humbertoyusta "Master humbertoyusta")
    646 
    647 **Hint 1**
    648 
    649 What is the size of the smallest subarray that it is possible to multiply by $-1$ using some operations?
    650 
    651 **Hint 2**
    652 
    653 Let $s$ be a string such that $s_i=0$ if that element is multiplied by $-1$ or $s_i=1$ otherwise, what such $s$ are reachable?
    654 
    655 **Hint 3**
    656 
    657 Think about the parity of the sum of all $s_i$ such that $i\mod{g}=constant$, where $g$ is the size of the smallest subarray that it is possible to multiply by $-1$ using some operations
    658 
    659 **Solution**
    660 
    661 If we have $x, y \in B$ (assume $x \gt y$), since all elements of $B$ are at most $\lfloor\frac{n}{2}\rfloor$, it is possible to multiply all intervals of size $x-y$ by either multiplying an interval of size $x$ that starts at the position of the interval of size $x-y$, and an interval of size $y$ that ends at the same position as the interval $x$, or multiply an interval of size $x$ that ends at the same position as the interval of size $x-y$ and another interval of size $y$ that starts at the same position as the interval of size $x$.
    662 
    663 For two elements $x, y \in B$ ($x \gt y$), it is possible to add $x-y$ to $B$, repeatedly doing this it is possible to get $\gcd(x, y)$.
    664 
    665 Let $g = \gcd(b_1, b_2, ..., b_m : b_i \in B)$, by applying the previous reduction $g$ is the smallest element that can be obtained, and all other elements will be its multiples, then the problem is reduced to, multiplying intervals of size $g$ by $-1$ any number of times, maximize $\sum\limits_{i=1}^n{a_i}$.
    666 
    667 Let's define the string $s = 000...00$ of size $n$ (0-indexed) such that $s_i = 0$ if the $i$-th element is not multiplied by $-1$ or $s_i = 1$ otherwise. The operation flips all values of $s$ in a substring of size $g$.
    668 
    669 Let's define $f_x$ as the [xor](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) over all values $s_i$ such that $i\mod g = x$, note that $f_x$ is defined for the values $0 \le x \le g-1$.
    670 
    671 In any operation, all values of $f$ change simultaneously, since they are all $0$ at the beginning only the states of $s$ such that all $f_i$ are equal are reachable.
    672 
    673 To prove that all states of $s$ with all $f_i$ equal are reachable, let's start with any state of $s$ such that $f = 000...00$ and repeatedly select the rightmost $i$ such that $s_i=1$ and $i\geq g-1$ and flip the substring that ends in that position, after doing that as many times as possible, $s_i = 0$ for $g-1\leq i\leq n-1$. If $s_i=1$ for any $0\leq i \lt g$, then $f_i = 1$ which is a contradiction since $f_{g-1} = 0$ and all $f_i$ change simultaneously, then $s = 000...00$. The case with all values of $f$ equal to $1$ is similar.
    674 
    675 After this, it is possible to solve the problem with $dp$.
    676 
    677 Let $dp_{i,0}$ be the maximum sum of $a_i, a_{i-g}, a_{i-2\cdot{g}}, ..., a_{i-k\cdot{g}}$ such that $i-k\cdot{g}\equiv{i}(\mod{g})$ and $\bigoplus\limits_{k\geq 0, i-k\cdot g\geq 0} f_{i-k \cdot g}=0$ and $dp_{i,1}$ be the same such that $\bigoplus\limits_{k\geq 0, i-k\cdot g\geq 0} f_{i-k \cdot g}=1$.
    678 
    679 The answer to the problem is $\max(\sum\limits_{i=n-g}^{n-1}{dp_{i,0}}, \sum\limits_{i=n-g}^{n-1}{dp_{i,1}} )$ (0-indexed).
    680 
    681 This $dp$ can be computed in $O(n)$.
    682 
    683 **Code**
    684 
    685 ```
    686 #include <bits/stdc++.h>
    687 using namespace std;
    688 typedef long long ll;
    689 
    690 int main()
    691 {
    692     ios_base::sync_with_stdio(0);
    693     cin.tie(0);
    694 
    695     int T;
    696     cin >> T;
    697 
    698     while(T--)
    699     {
    700         int n,m;
    701         cin >> n >> m;
    702         vector<int> a(n),b(m);
    703         for(int i=0;i<n;i++)
    704             cin >> a[i];
    705 
    706         int g=0;
    707         for(int i=0;i<m;i++)
    708         {
    709             cin >> b[i];
    710             g=__gcd(g,b[i]);
    711         }
    712 
    713         vector<vector<ll>> dp(g,vector<ll>(2));
    714         for(int i=0;i<g;i++)
    715             dp[i][1]=-2e9;
    716         for(int i=0;i<n;i++)
    717         {
    718             int rem=i%g;
    719             ll v0=max(dp[rem][0]+a[i],dp[rem][1]-a[i]);
    720             ll v1=max(dp[rem][0]-a[i],dp[rem][1]+a[i]);
    721             dp[rem][0]=v0;
    722             dp[rem][1]=v1;
    723         }
    724 
    725         ll sum0=0,sum1=0;
    726         for(int i=0;i<g;i++)
    727         {
    728             sum0+=dp[i][0];
    729             sum1+=dp[i][1];
    730         }
    731 
    732         cout << max(sum0,sum1) << '\n';
    733     }
    734 
    735     return 0;
    736 }
    737 ```
    738 
    739 ### [1630E - Expected Components](/contest/1630/problem/E "Codeforces Round 768 (Div. 1)")
    740 
    741 Author: [BrayanD](/profile/BrayanD "Master BrayanD")
    742 
    743 **Hint 1**
    744 
    745 [Burnside's lemma](https://cp-algorithms.com/combinatorics/burnside.html)
    746 
    747 **Hint 2**
    748 
    749 Think about an easy way to count the number of components in a cyclic array.
    750 
    751 **Hint 3**
    752 
    753 The number of components in a cyclic array is equal to the number of adjacent positions with different values.
    754 
    755 **Solution**
    756 
    757 The problem can be solved by applying [Burnside's lemma](https://cp-algorithms.com/combinatorics/burnside.html).
    758 
    759 The number of different permutations of the cyclic array $a$ is equal to the sum of number of fixed points for each permutation function divided by the number of permutations functions.
    760 
    761 Let's focus on two parts.
    762 
    763 First part (find the number of different permutations of $a$):
    764 
    765 Let's define a permutation function $F_x(arr)$ as the function that cyclically shifts the array $arr$ by $x$ positions.
    766 
    767 In this problem for an array of size $n$ we have $n$ possible permutations functions and we would need to find the sum of the number of fixed points for each permutation function.
    768 
    769 To find the number of fixed points for a permutation function $F_x()$ we have that $arr_i$ must be equal to $arr_{(i+x)\%n}$, if we add an edge $(i,(i+x)\%n)$ for each position $i$ then by number theory we would obtain that $gcd(n,x)$ cycles would be formed and each one of size $\frac{n}{gcd(n,x)}$, then we can note that each position $i$ will belong to the $(i\%gcd(n,x))$-th cycle, so we can say that the problem can be transformed into counting the number of permutations with repetition in an array of size $gcd(n,x)$.
    770 
    771 Let us denote $cnt[v]$ as the number of values equal to $v$ in array $a$, when we are processing the function $F_x()$ and we reduce the problem to an array of size $gcd(n,x)$ we should also decrease $cnt[v]$ to $\frac{cnt[v]}{n/gcd(n,x)}$ since each component is made up of $\frac{n}{gcd(n,x)}$ values, also we must observe that for solving a problem for an array of size $x$, then $\frac{n}{x}$ should be a divisor of $gcd(cnt[1],cnt[2],\ldots,cnt[n])$.
    772 
    773 Let us denote $cnt_x[v] = \frac{cnt[v]}{n/gcd(n,x)}$
    774 
    775 So to count the number of permutations with repetition for $F_x()$ that can be formed with the frequency array $cnt_x$ we can use the formula $\frac{n!}{x_1! \cdot x_2! \cdot \ldots \cdot x_n!}$
    776 
    777 Let us denote $G_{all} = gcd(cnt[1],cnt[2],\ldots,cnt[n])$
    778 
    779 Let us denote $fdiv(val)$ as the number of divisors of $val$.
    780 
    781 Let us denote $tot_{sz}$ as the number of permutations with repetition for an array of size $sz$, from what has been said before we have that $\frac{n}{sz}$ must be divisible by $G_{all}$ so we only need to calculate the permutations with repetition for $fdiv(G_{all})$ arrays.
    782 
    783 Now suppose that the number of different values of array $a$ is $k$ then $G_{all}$ must be at most $\frac{n}{k}$ because the gcd of several numbers is always less than or equal to the smallest of them.
    784 
    785 Now to calculate the permutations with repetition for a $cnt_x$ we do it in $O(k)$, for that we need to precalculate some factorials and modular inverses before, and since we need to calculate them $fdiv(G_{all})$ times, then we have that in total the complexity would be $O(fdiv(G_{all})\cdot k)$ but since $G_{all}$ is at most $\frac{n}{k}$ and $fdiv(\frac{n}{k})$ is at most $\frac{n}{k}$, substituting it would be $O(\frac{n}{k}\cdot k)$ equal to $O(n)$
    786 
    787 So to find the sum of the number of fixed points we need the sum of $tot_{gcd(n,x)}$ for $1 \le x \le n$ and $\frac{n}{gcd(n,x)}$ divides to $G_{all}$, at the end of all we divide the sum of the number of fixed points by $n$ and we would obtain the number of different permutations of $a$.
    788 
    789 To find the $gcd(n,x)$ for $1 \le x \le n$ we do it with the Euclid's algorithm in complexity $O(n\cdot log)$ so in total the complexity is $O(n\cdot log)$
    790 
    791 Second part (find the expected value of components of different permutations of $a$):
    792 
    793 Here we will use the Linear Expectation property and we will focus on calculating the contribution of each component separately, the first thing is to realize that the number of components is equal to the number of different adjacent values, so we only need to focus on two adjacent values, except if it is a single component, this would be a special case. If we have $k$ different values we can use each different pair of them that in total would be $k\cdot(k-1)$ pairs, we can realize that when we put a pair its contribution would be equal to the number of ways to permute the remaining values, which if we are in an array of size $\frac{n}{x}$ and we use the values $val_1$ and $val_2$ it would be equal to:
    794 
    795 $tot_{n/x} \cdot \frac{1}{(n/x)\cdot(n/x-1)} \cdot cnt_x[val_1] \cdot cnt_x[val_2]$
    796 
    797 because we removing a value $val_1$ and another value $val_2$ from the set, so if we have the formula:
    798 
    799 $\frac{n!}{x_1! \cdot x_2! \cdot \ldots \cdot x_n!}$
    800 
    801 and $val_1$ and $val_2$ are the first two elements then it would be:
    802 
    803 $\frac{(n-2)!}{(x_1-1)! \cdot (x_2-1)! \cdot \ldots \cdot x_n!}$
    804 
    805 which would be equivalent to:
    806 
    807 $\frac{n!}{x_1! \cdot x_2! \cdot \ldots \cdot x_n!} \cdot \frac{1}{n \cdot (n-1)} \cdot x_1 \cdot x_2$
    808 
    809 Now to calculate the contribution of the $k\cdot(k-1)$ pairs we can realize that taking common factor $tot_{n/x} \cdot \frac{1}{(n/x)\cdot(n/x-1)}$ in the previous expression it only remains to find the sum of $cnt_x[i]\cdot cnt_x[j]$ for all $i \neq j$, this can be found in $O(k)$ easily by keeping the prefix sum and doing some multiplication. Then at the end we multiply by $n$ since there are $n$ possible pairs of adjacent elements in the general array.
    810 
    811 Let us define $sum_{sz}$ as the contribution of components of the permutations with repetition for an array of size $sz$, then:
    812 
    813 $sum_{n/x} = tot_{n/x} \cdot \frac{1}{(n/x)\cdot(n/x-1)} \cdot (sum~of~(cnt_x[i]\cdot cnt_x[j])~for~i \neq j) \cdot n$
    814 
    815 Now for each possible permutation with repetition we have by the Burnside's lemma that in the end we divide it by $n$, so we should also divide by $n$ the contribution of each component.
    816 
    817 Let's define $tot'_x = \frac{tot_x}{n}$ and $sum'_x = \frac{sum_x}{n}$
    818 
    819 Let's define $tot_{all}$ as the sum of $tot'_{gcd(n,x)}$ for $1 \le x \le n$ and $\frac{n}{gcd(n,x)}$ divide to $G_{all}$.
    820 
    821 Let's define $sum_{all}$ as the sum of $sum'_{gcd(n,x)}$ for $1 \le x \le n$ and $\frac{n}{gcd(n,x)}$ divide to $G_{all}$.
    822 
    823 The final answer would be:
    824 
    825 $res = \frac{sum_{all}}{tot_{all}}$
    826 
    827 The final complexity then is $O(n\cdot log)$
    828 
    829 **Code**
    830 
    831 ```
    832 #include <bits/stdc++.h>
    833 
    834 using namespace std;
    835 
    836 const int MAXN = 1e6 + 100;
    837 
    838 const int MOD = 998244353;
    839 
    840 long long fact[MAXN];
    841 
    842 long long F[MAXN];
    843 
    844 long long qpow(long long a, long long b)
    845 {
    846     long long res = 1;
    847     while(b)
    848     {
    849         if(b&1)res = res*a%MOD;
    850         a = a*a%MOD;
    851         b /= 2;
    852     }
    853     return res;
    854 }
    855 
    856 long long inv(long long x)
    857 {
    858     return qpow(x,MOD-2);
    859 }
    860 
    861 int32_t main()
    862 {
    863     ios_base::sync_with_stdio(0);
    864     cin.tie(0);
    865 
    866     fact[0] = 1;
    867 
    868     for(int i = 1 ; i < MAXN ; i++)
    869     {
    870         fact[i] = fact[i-1]*i%MOD;
    871     }
    872 
    873     int T;
    874     cin >> T;
    875 
    876     while(T--)
    877     {
    878         int N;
    879         cin >> N;
    880 
    881         for(int i = 1 ; i <= N ; i++)
    882         {
    883             F[i] = 0;
    884         }
    885 
    886         for(int i = 1 ; i <= N ; i++)
    887         {
    888             int n;
    889             cin >> n;
    890             F[n]++;
    891         }
    892 
    893         vector<long long> vvv;
    894 
    895         for(int i = 1 ; i <= N ; i++)
    896         {
    897             if(F[i])vvv.push_back(F[i]);
    898         }
    899 
    900         int G = 0;
    901 
    902         for(auto x : vvv)
    903         {
    904             G = __gcd(G,x);
    905         }
    906 
    907         if(G == N)
    908         {
    909             cout << 1 << '\n';
    910             continue;
    911         }
    912 
    913         vector<long long> arr(N+1);
    914         vector<long long> arr2(N+1);
    915 
    916         for(int i = 1 ; i <= G ; i++)
    917         {
    918             if(G%i == 0)
    919             {
    920                 long long tot = inv(fact[N/i-2]), acum = 0, sum = 0;
    921 
    922                 for(auto x : vvv)
    923                 {
    924                     tot = tot*fact[x/i]%MOD;
    925                     sum = (sum + acum*(x/i)*2)%MOD;
    926                     acum = (acum + (x/i))%MOD;
    927                 }
    928 
    929                 tot = inv(tot);
    930 
    931                 arr2[i] = tot*(N/i-1)%MOD*(N/i)%MOD;
    932 
    933                 tot = tot*sum%MOD*N%MOD;
    934 
    935                 arr[i] = tot;
    936             }
    937         }
    938 
    939         long long res = 0;
    940         long long cont = 0;
    941 
    942         for(int i = 1 ; i <= N ; i++)
    943         {
    944             long long ggg = N/__gcd(N,i);
    945 
    946             if(G%ggg == 0)
    947             {
    948                 res = (res + arr[ggg])%MOD;
    949                 cont = (cont + arr2[ggg])%MOD;
    950             }
    951         }
    952 
    953         cout << res*inv(cont)%MOD << '\n';
    954     }
    955 
    956     return 0;
    957 }
    958 ```
    959 
    960 ### [1630F - Making It Bipartite](/contest/1630/problem/F "Codeforces Round 768 (Div. 1)")
    961 
    962 Author: [BrayanD](/profile/BrayanD "Master BrayanD")
    963 
    964 **Hint 1**
    965 
    966 Think about the directed graph where there is an directed edge from $a$ to $b$ if and only if $b|a$
    967 
    968 **Hint 2**
    969 
    970 Let us define the above graph as $G$, make a duplicate graph $G'$ from $G$, and then add directed edges $(x', x)$ for each node $x'$ of the graph $G'$. What happens in this graph?
    971 
    972 **Hint 3**
    973 
    974 Maximum [Antichain](https://en.wikipedia.org/wiki/Antichain)
    975 
    976 **Solution**
    977 
    978 First of all, let's analyze what happens when there are $3$ vertices $x$, $y$ and $z$ such that $a_x|a_y$, $a_x|a_z$ and $a_y|a_z$, if this happens then the graph cannot be bipartite because there would be a cycle of size $3$, therefore there cannot be such a triple ($x$, $y$, $z$), this condition, besides to being necessary, is sufficient since we can separate the graph into two sets, set $A$: vertices that have edges towards multiples, set $B$: vertices that have edges towards divisors, keep in mind that a vertex cannot exist in two sets at the same time if the condition is fulfilled, now note that there are no edges between elements of the same set because if this happens it would mean that they belong to different sets and it would be a contradiction, then the problem is to find the minimum number of vertices to remove such that in the remaining vertices there is no such triple of numbers ($x$, $y$, $z$). Now instead of minimizing the number of vertices to remove, let's try to maximize the number of vertices that will remain in the graph.
    979 
    980 Let us define the directed graph $G$ as the graph formed by $n$ vertices, and directed edges ($u$, $v$) such that $a_v|a_u$, now the problem is reduced to finding the maximum number of vertices such that in the graph formed among them, no vertex has ingoing edges and outgoing edges at the same time, formally for each vertex $x$ the following property must be kept $indegree_x = 0$ or $outdegree_x = 0$, in this way we guarantee that there is no triple ($x$, $y$, $z$) such that $a_x|a_y$, $a_x|a_z$ and $a_y|a_z$.
    981 
    982 Now let's define the graph $G'$ as a copy of the graph $G$. Formally for each directed edge ($u$, $v$) in the graph $G$ there is an directed edge ($u'$, $v'$) in the graph $G'$. On the other hand, let's define the graph $H = G + G'$ and we will also add new directed edges ($u'$, $u$), this graph $H$ is a $DAG$, it is easy to see that the edges always go from a vertex $u$ to a vertex $v$ only if $a_u \gt a_v$, except for the edges ($u'$, $u$), which in this case $a_{u'} = a_u$, these edges are the ones that connect $G'$ to $G$, but since they always go in one direction pointing towards $G$, the property of $DAG$ is still fulfilled.
    983 
    984 Now the only thing we have to do is find the largest antichain in the graph $H$, this can be done using the Dilworth's Theorem, modeling the problem as a bipartite matching, we can use some flow algorithm such as Dinic's Algorithm, or Hopcroft Karp's Algorithm, which is specific to find the maximum bipartite matching.
    985 
    986 #### Proof:
    987 
    988 First of all we realize that the graph $G$ is a special graph since if there is an indirect path from a vertex $u$ to a vertex $v$ then there is always a direct edge between them, this is true because if we have $3$ vertices $x$, $y$ and $z$ such that $a_x|a_y$ and $a_y|a_z$ then always $a_x|a_z$. With this we can say that two elements are not reachable with each other if and only if there are no edges between them. Now let's say that all the vertices in the graph $G$ are white and all the vertices in the graph $G'$ are black, let us denote $f(x)$ a function such that $f(u') = u$, where the vertex $u$ from the graph $G$ is the projection of the vertex $u'$ from the graph $G'$. Now let's divide the proof into two parts.
    989 
    990 #### First part:
    991 
    992 **Lemma 1:** Every antichain of $H$ can be transformed into a valid set of vertices such that they form a bipartite graph.
    993 
    994 Proof of Lemma 1: Let's divide the antichain of $H$ into two sets, white vertices and black vertices, Let us define the set of white vertices as $W$ and the set of all black vertices as $B$, now we will create a set $S$ = {$f(x)$ | $x \in B$}. It is easy to see that no element in $S$ belongs to $W$ since if this happens it would mean that there is an element $x$ such that $x$ belongs to $B$ and $f(x)$ belongs to $W$ and by the concept of antichain that would not be possible. It is also easy to see that the elements of the set $S$ are an antichain since the set $S$ is a projection of vertices from the set $B$ of the graph $G'$ on $G$. Now we have that there are no edges between the vertices of the set $S$ and there are no edges between the vertices of the set $W$, with this it is proved that the graph is bipartite.
    995 
    996 #### Second part:
    997 
    998 **Lemma 2:** Every valid set of vertices such that they form a bipartite graph can be transformed into an antichain of $H$.
    999 
   1000 Proof of Lemma 2: Let us denote $f^{-1}(x)$ a function such that $f^{-1}(u) = u'$, where vertex $u$ from graph $G$ is the projection of vertex $u'$ from graph $G'$. Let us denote the set $A$ as all vertices that have $indegree$ greater than $0$ and $B$ to all vertices that have $outdegree$ greater than $0$, now we will create a set $C$ = {$f^{-1}(x)$ | $x \in A$}, It is easy to see that set $B$ is an antichain since if one vertex has an edge to another vertex then some of them would have $indegree$ greater than $0$ and would contradict the definition of set $B$, we can also see that the elements in set $A$ are an antichain since all the elements have $outdegree = 0$ so no vertex point towards any other vertex, with this we can define that all the elements in $C$ are an antichain since they are a projection of vertices of the set $A$ from the graph $G$ on $G'$, Now we want to proof that the union of set $B$ and $C$ is an antichain, this is very simple to see since the vertices of set $B$ belong to $G$ and the vertices of $C$ belong to $G'$, therefore there is no edge from any vertex in $B$ to a vertex in $C$ since there are no edges from $G$ to $G'$. Now it only remains to proof that from set $C$ no vertex of set $B$ can be reached, this is proved taking into account that the vertices reachable from the set $C$ in the graph $G$ are the same that the vertices reachable from the set $A$ in the graph $G$, and as no vertex of $A$ has edges towards $B$, this cannot happen. Therefore the union of the sets $B$ and $C$ is an antichain of $H$.
   1001 
   1002 Then we can say that the two problems are equivalent and it is shown that finding the maximum antichain we obtain the largest bipartite graph.
   1003 
   1004 The graph $G$ contains $n$ vertices and around $n\cdot log(n)$ edges (since the numbers $a_x$ are different and the sum of the divisors from $1$ to $n$ is around $n\cdot log(n)$). The graph $G'$ is a duplicate of $G$ then we would have $n\cdot log(n)\cdot2 + n$ edges and $2\cdot n$ vertices, if we use the Hopcroft Karp algorithm we would obtain a time complexity of $O(n\cdot log(n)\cdot sqrt(n))$ and a space complexity of $O(n\cdot log(n))$.
   1005 
   1006 **Code**
   1007 
   1008 ```
   1009 #include <bits/stdc++.h>
   1010 
   1011 using namespace std;
   1012 
   1013 struct HOPCROFT_KARP
   1014 {
   1015     int n, m;
   1016     vector<vector<int>> adj;
   1017     vector<int> mu, mv, level, que;
   1018 
   1019     HOPCROFT_KARP(int n, int m) : n(n), m(m), adj(n), mu(n, -1), mv(m, -1), level(n), que(n) {}
   1020 
   1021     void add_edge(int u, int v)
   1022     {
   1023         adj[u].push_back(v);
   1024     }
   1025 
   1026     void bfs()
   1027     {
   1028         int qf = 0, qt = 0;
   1029         for(int u = 0 ; u < n ; ++u)
   1030         {
   1031             if(mu[u] == -1)que[qt++] = u, level[u] = 0;
   1032             else level[u] = -1;
   1033         }
   1034         for( ; qf < qt ; ++qf)
   1035         {
   1036             int u = que[qf];
   1037             for(auto w : adj[u])
   1038             {
   1039                 int v = mv[w];
   1040                 if(v != -1 && level[v] == -1)
   1041                     que[qt++] = v, level[v] = level[u] + 1;
   1042             }
   1043         }
   1044     }
   1045 
   1046     bool dfs(int u)
   1047     {
   1048         for(auto w : adj[u])
   1049         {
   1050             int v = mv[w];
   1051             if(v == -1 || (level[v] == level[u] + 1 && dfs(v)))
   1052                 return mu[u] = w, mv[w] = u, true;
   1053         }
   1054         return false;
   1055     }
   1056 
   1057     int max_matching()
   1058     {
   1059         int match = 0;
   1060         for(int c = 1 ; bfs(), c ; match += c)
   1061             for(int u = c = 0 ; u < n ; ++u)
   1062                 if(mu[u] == -1)
   1063                     c += dfs(u);
   1064         return match;
   1065     }
   1066 
   1067     pair<vector<int>, vector<int>> min_vertex_cover()
   1068     {
   1069         max_matching();
   1070         vector<int> L, R, inR(m);
   1071         for(int u = 0 ; u < n ; ++u)
   1072         {
   1073             if(level[u] == -1)L.push_back(u);
   1074             else if(mu[u] != -1)inR[mu[u]] = true;
   1075         }
   1076         for(int v = 0 ; v < m ; ++v)
   1077             if(inR[v])R.push_back(v);
   1078         return { L, R };
   1079     }
   1080 };
   1081 
   1082 const int MAXN = 5e4 + 100;
   1083 
   1084 int arr[MAXN];
   1085 vector<int> dv[MAXN];
   1086 
   1087 int main()
   1088 {
   1089     ios_base::sync_with_stdio(0);
   1090     cin.tie(0);
   1091 
   1092     for(int i = 1 ; i < MAXN ; i++)
   1093     {
   1094         for(int j = i*2 ; j < MAXN ; j+=i)
   1095         {
   1096             dv[j].push_back(i);
   1097         }
   1098     }
   1099 
   1100     for(int i = 0 ; i < MAXN ; i++)
   1101     {
   1102         arr[i] = -1;
   1103     }
   1104 
   1105     int T;
   1106     cin >> T;
   1107 
   1108     while(T--)
   1109     {
   1110         int N;
   1111         cin >> N;
   1112 
   1113         vector<int> vect;
   1114 
   1115         for(int i = 0 ; i < N ; i++)
   1116         {
   1117             int n;
   1118             cin >> n;
   1119             vect.push_back(n);
   1120             arr[n] = i;
   1121         }
   1122 
   1123         vector<pair<int,int>> edge;
   1124 
   1125         for(int i = 0 ; i < N ; i++)
   1126         {
   1127             for(auto x : dv[vect[i]])
   1128             {
   1129                 if(arr[x] != -1)
   1130                 {
   1131                     edge.push_back({i, arr[x]});
   1132                 }
   1133             }
   1134         }
   1135 
   1136         for(auto x : vect)
   1137         {
   1138             arr[x] = -1;
   1139         }
   1140 
   1141         HOPCROFT_KARP HK(2*N,2*N);
   1142 
   1143         for(auto x : edge)
   1144         {
   1145             int i = x.first;
   1146             int j = x.second;
   1147             HK.add_edge(i,j);
   1148             HK.add_edge(i+N,j+N);
   1149         }
   1150 
   1151         for(int i = 0 ; i < N ; i++)
   1152         {
   1153             HK.add_edge(i+N,i);
   1154         }
   1155 
   1156         cout << HK.max_matching()-N << '\n';
   1157     }
   1158 
   1159     return 0;
   1160 }
   1161 ```