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 ```