codeforces-scrape

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

1711.md (21470B)


      1 Source: https://codeforces.com/blog/entry/105232
      2 
      3 Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask.
      4 
      5 [1711A - Perfect Permutation](/contest/1711/problem/A "Codeforces Round 810 (Div. 2)")
      6 
      7 **hint1.**
      8 
      9 The minimal weight is at least $1$ since $1$ divides any integer (so $1$ divides $p_1$).
     10 
     11 **solution**
     12 
     13 Since $k+1$ does not divide $k$, a permutation with weight equal to $1$ is: $[n,1,2,\cdots,n-1]$.
     14 
     15 **code**
     16 
     17 ```
     18 #include <bits/stdc++.h>
     19 
     20 using namespace std;
     21 
     22 void work()
     23 {
     24 	int n;
     25 	cin>>n;
     26 	cout<<n<<' ';
     27 	for (int i=1;i<n;i++)
     28 		cout<<i<<' ';
     29 	cout<<endl;
     30 }
     31 
     32 int main()
     33 {
     34 	int casenum=1;
     35 	cin>>casenum;
     36 	for (int testcase=1;testcase<=casenum;testcase++)
     37 		work();
     38 	return 0;
     39 }
     40 ```
     41 
     42 [1711B - Party](/contest/1711/problem/B "Codeforces Round 810 (Div. 2)")
     43 
     44 **hint1.**
     45 
     46 See the party as a graph.
     47 
     48 **hint2.**
     49 
     50 Divide the vertices into two categories according to their degrees' parity.
     51 
     52 **solution**
     53 
     54 Let's consider the case where $m$ is odd only, since if $m$ is even the answer is $0$.
     55 
     56 Assume that you delete $x$ vertices with even degrees and $y$ vertices with odd degrees.
     57 
     58 If $y \geq 1$, then only deleting one vertex with an odd degree would lead to a not worse answer, so you do not need to consider it except for $(x,y)=(0,1)$.
     59 
     60 If $y=0$, then the parity of the edges at the end is determined only by the number of edges whose both endpoints are deleted. In particular, there must be at least two adjacent vertices deleted with even degrees. So you do not need to consider it except for $(x,y)=(2,0)$ and they are neighbours.
     61 
     62 Thus, an optimal solution either has $(x, y) = (0, 1)$ or $(x, y) = (2, 0)$ and the two vertices are adjacent.
     63 
     64 One can iterate over all possible solutions with such a structure and take the optimal one.
     65 
     66 Total time complexity: $O(n+m)$.
     67 
     68 **code**
     69 
     70 ```
     71 #include <bits/stdc++.h>
     72 using namespace std;
     73 #define MAXN 100010
     74 int x[MAXN],y[MAXN],a[MAXN],degree[MAXN];
     75 int n,m;
     76 void work()
     77 {
     78 	cin>>n>>m;
     79 	for (int i=1;i<=n;i++)
     80 	{
     81 		degree[i]=0;
     82 		cin>>a[i];
     83 	}
     84 	for (int i=1;i<=m;i++)
     85 	{
     86 		cin>>x[i]>>y[i];
     87 		degree[x[i]]++;
     88 		degree[y[i]]++;
     89 	}
     90 	int ans=INT_MAX;
     91 	if (m%2==0)
     92 		ans=0;
     93 	for (int i=1;i<=n;i++)
     94 		if (degree[i]%2==1)
     95 			ans=min(ans,a[i]);
     96 	for (int i=1;i<=m;i++)
     97 		if (degree[x[i]]%2==0 && degree[y[i]]%2==0)
     98 			ans=min(ans,a[x[i]]+a[y[i]]);
     99 	cout<<ans<<endl;
    100 }
    101 
    102 int main()
    103 {
    104 	int casenum=1;
    105 	cin>>casenum;
    106 	for (int testcase=1;testcase<=casenum;testcase++)
    107 		work();
    108 	return 0;
    109 }
    110 ```
    111 
    112 [1710A - Color the Picture](/contest/1710/problem/A "Codeforces Round 810 (Div. 1)")
    113 
    114 **hint1.**
    115 
    116 The picture must consist of some stripes with at least $2$ rows or at least $2$ columns.
    117 
    118 **hint2.**
    119 
    120 When $n$ is odd and all $\lfloor \frac{a_i}{m} \rfloor=2$, we cannot draw a beautiful picture using row stripes.
    121 
    122 **solution**
    123 
    124 Let's first prove hint1 first.
    125 
    126 If there is a pair of toroidal neighbors with different colors. For example, $col_{x,y}=a$ and $col_{x+1,y}=b(a\neq b)$. Then we will find $col_{x-1,y}=col_{x,y+1}=col_{x,y-1}=a$,$col_{x+2,y}=col_{x+1,y+1}=col_{x+1,y-1}=b$ must hold. Then we find another two pairs of toroidal neighbors $col_{x,y+1},col_{x+1,y+1}$ and $col_{x,y-1},col_{x+1,y-1}$. Repeat such process, we will find the boundary should be like:
    127 
    128 ![ ](/predownloaded/86/79/8679d62e53be2f9d3c6edecbda492a9bfd5bdbfa.png)
    129 
    130 Similar, the boundaries can be vertical lines, but horizontal lines and vertical lines can not exist in one picture.
    131 
    132 So the pattern should be row stripes all with at least $2$ rows or column stripes all with at least $2$ columns.
    133 
    134 Check if one can draw a beautiful picture with row stripes only or with column stripes only. We consider only the case of row stripes, the reasoning is analogous for column stripes.
    135 
    136 If it is possible, then $\sum_{a_i \geq 2m} \lfloor \frac{a_i}{m} \rfloor \geq n$ must hold.
    137 
    138 If $n$ is even, then such a condition is enough.
    139 
    140 If $n$ is odd, there must be some $\lfloor \frac{a_i}{m} \rfloor \geq 3$. In this case, you can draw a beautiful picture using such algorithm:
    141 
    142 * Sort $a_i$ from large to small.
    143 * Draw $2$ rows stripes of each color if possible.
    144 * If the picture still has some rows empty, insert new rows into each stripe.
    145 
    146 Total time complexity: $O(n)$.
    147 
    148 **code**
    149 
    150 ```
    151 #include <bits/stdc++.h>
    152 using namespace std;
    153 #define MAXN 100010
    154 int n,m,k;
    155 int a[MAXN];
    156 void work()
    157 {
    158 	cin>>n>>m>>k;
    159 	for (int i=1;i<=k;i++)
    160 		cin>>a[i];
    161 	bool flag;
    162 	long long tot=0;
    163 	flag=0;
    164 	tot=0;
    165 	for (int i=1;i<=k;i++)
    166 	{
    167 		if (a[i]/n>2)
    168 			flag=1;
    169 		if (a[i]/n>=2)
    170 			tot+=a[i]/n;
    171 	}
    172 	if (tot>=m && (flag || m%2==0))
    173 	{
    174 		cout<<"Yes"<<endl;
    175 		return ;
    176 	}
    177 	flag=0;
    178 	tot=0;
    179 	for (int i=1;i<=k;i++)
    180 	{
    181 		if (a[i]/m>2)
    182 			flag=1;
    183 		if (a[i]/m>=2)
    184 			tot+=a[i]/m;
    185 	}
    186 	if (tot>=n && (flag || n%2==0))
    187 	{
    188 		cout<<"Yes"<<endl;
    189 		return ;
    190 	}
    191 	cout<<"No"<<endl;
    192 
    193 }
    194 
    195 int main()
    196 {
    197 	int casenum=1;
    198 	cin>>casenum;
    199 	for (int testcase=1;testcase<=casenum;testcase++)
    200 		work();
    201 	return 0;
    202 }
    203 ```
    204 
    205 [1710B - Rain](/contest/1710/problem/B "Codeforces Round 810 (Div. 1)")
    206 
    207 **hint1.**
    208 
    209 The maximum can always be achieved in the center position of one day's rain.
    210 
    211 **hint2.**
    212 
    213 $a_i$ is a piecewise linear function and the slope of $a_i$ will only change for $O(n)$ times.
    214 
    215 **hint3.**
    216 
    217 Supposing you know an invalid position $j$ where $a_j \gt m$, what are the properties of a rain that, if erase, makes it valid?
    218 
    219 **solution**
    220 
    221 Let's call position $j$ a key position if it is the center position of a rain. i.e. there exists $i$ so that $x_i=j$.
    222 
    223 You can calculate $a_j$ for all key positions $j$ using the difference array.
    224 
    225 Let $d^{1}_{j}=a_{j}-a_{j-1}$, $d^{2}_{j}=d^{1}_{j}-d^{1}_{j-1}$, then the $i$-th day's rain will change it as follows:
    226 
    227 $d^{2}_{x_i-p_i+1} \leftarrow d^{2}_{x_i-p_i+1}+1$
    228 
    229 $d^{2}_{x_i+1} \leftarrow d^{2}_{x_i+1}-2$
    230 
    231 $d^{2}_{x_i+p_i+1} \leftarrow d^{2}_{x_i+p_i+1}+1$
    232 
    233 This can be calculated efficiently using prefix sums.
    234 
    235 We say that a position $j$ is valid if $a_j\le m$.
    236 
    237 Now, consider an invalid position $j$; erasing the $i$-th day's rain will make it valid if and only if $p_i-|x_i-j| \geq a_j-m$.
    238 
    239 One can check that the region of $(x, p)$ satisfying such an inequality is a quadrant rotated $45^\circ$ anticlockwise and translated. And in particular, even the intersections of two such regions have the same structure and can be computed easily (to avoid using floating point numbers, one can multiply all $x_i,p_i$ by $2$).
    240 
    241 In the end, for each $i$, you only need to check whether point $(x_i,p_i)$ belongs to such region.
    242 
    243 Total time complexity: $O(n\log n)$.
    244 
    245 **code**
    246 
    247 ```
    248 #include <bits/stdc++.h>
    249 #define MAXN 200100
    250 #define LL long long
    251 using namespace std;
    252 
    253 typedef pair<LL,LL> pll;
    254 LL n,m;
    255 LL x[MAXN],p[MAXN];
    256 vector<pll> diff;
    257 pll key;
    258 
    259 pll getIntersection(pll p1,pll p2)
    260 {
    261 	LL tx=max(p1.first+p1.second,p2.first+p2.second);
    262 	LL ty=max(p1.second-p1.first,p2.second-p2.first);
    263 	return {(tx-ty)/2,(tx+ty)/2};
    264 }
    265 
    266 void work()
    267 {
    268 	diff.clear();
    269 	key={0,-0x3f3f3f3f3f3f3f3f};
    270 	cin>>n>>m;
    271 	m*=2;
    272 	for (int i=1;i<=n;i++)
    273 	{
    274 		cin>>x[i]>>p[i];
    275 		x[i]*=2;
    276 		p[i]*=2;
    277 		diff.push_back({x[i]-p[i],1});
    278 		diff.push_back({x[i],-2});
    279 		diff.push_back({x[i]+p[i],1});
    280 	}
    281 	sort(diff.begin(), diff.end());
    282 	LL a=0,d=0;
    283 	LL lst=0;
    284 	for (auto p:diff)
    285 	{
    286 		if (p.first!=lst)
    287 		{
    288 			a=a+(p.first-lst)*d;
    289 			lst=p.first;
    290 			if (a>m)
    291 				key=getIntersection(key,{p.first,a-m});
    292 		}
    293 		d+=p.second;
    294 	}
    295 	for (int i=1;i<=n;i++)
    296 		if (getIntersection(key,{x[i],p[i]})==pll(x[i],p[i]))
    297 			cout<<'1';
    298 		else
    299 			cout<<'0';
    300 	cout<<endl;
    301 }
    302 
    303 int main()
    304 {
    305 	int casenum=1;
    306 	cin>>casenum;
    307 	for (int testcase=1;testcase<=casenum;testcase++)
    308 		work();
    309 	return 0;
    310 }
    311 ```
    312 
    313 [1710C - XOR Triangle](/contest/1710/problem/C "Codeforces Round 810 (Div. 1)")
    314 
    315 **hint1.**
    316 
    317 Consider the same bit of three integers at the same time.
    318 
    319 **hint2.**
    320 
    321 $a\bigoplus b \leq a+b$
    322 
    323 **solution**
    324 
    325 Define $cnt_{i_1 i_2 i_3}$ as:
    326 
    327 $j$th bit of $cnt_{i_1 i_2 i_3}$ is $1$ iif $i_1=a_j,i_2=b_j,i_3=c_j$
    328 
    329 e.g. $a=(10)_2,b=(11)_2,c=(01)_2$ then $cnt_{110}=(10)_2,cnt_{011}=(01)_2$, other $cnt$ is 0.
    330 
    331 $a=cnt_{100}+cnt_{101}+cnt_{110}+cnt_{111}$
    332 
    333 $b=cnt_{010}+cnt_{011}+cnt_{110}+cnt_{111}$
    334 
    335 $c=cnt_{001}+cnt_{011}+cnt_{101}+cnt_{111}$
    336 
    337 $a\bigoplus b = cnt_{010}+cnt_{011}+cnt_{100}+cnt_{101}$
    338 
    339 $a\bigoplus c = cnt_{001}+cnt_{011}+cnt_{100}+cnt_{110}$
    340 
    341 $b\bigoplus c = cnt_{001}+cnt_{010}+cnt_{101}+cnt_{110}$
    342 
    343 $a\bigoplus b + a\bigoplus c \gt b \bigoplus c \iff cnt_{011}+cnt_{100} \gt 0$
    344 
    345 similar:
    346 
    347 $cnt_{101}+cnt_{010} \gt 0$
    348 
    349 $cnt_{110}+cnt_{001} \gt 0$
    350 
    351 then we use digit dp: $dp[n][i][j]$ means when we consider first $n$ bits, state of reaching the upper bound is $i$, state of conditions is $j$.
    352 
    353 Enumerate $a_j b_j c_j$ for $j$ from $|n|-1$ to $0$ and make transition.
    354 
    355 Time complexity is $O(2^9 |n|)$ where $|n|$ is the length of input.
    356 
    357 **code**
    358 
    359 ```
    360 #include <bits/stdc++.h>
    361 #define MAXN 200100
    362 #define LL long long
    363 #define MOD 998244353
    364 using namespace std;
    365 
    366 LL dp[MAXN][8][8];
    367 string s;
    368 int main()
    369 {
    370 	cin>>s;
    371 	dp[0][0][0]=1;
    372 	for (int i=0;i<s.size();i++)
    373 		for (int mask1=0;mask1<8;mask1++)
    374 			for (int mask2=0;mask2<8;mask2++)
    375 			{
    376 				dp[i][mask1][mask2]%=MOD;
    377 				for (int m=0;m<8;m++)
    378 				{
    379 					bool flag=false;
    380 					for (int j=0;j<3;j++)
    381 						if (s[i]=='0' && (mask2>>j)%2==0 && (m>>j)%2==1)
    382 						{
    383 							flag=true;
    384 							break;
    385 						}
    386 					if (flag)
    387 						continue;
    388 					int tmpmask1=mask1;
    389 					int tmpmask2=mask2;
    390 					for (int j=0;j<3;j++)
    391 						if (s[i]-'0'!=((m>>j)&1))
    392 							tmpmask2|=(1<<j);
    393 					for (int j=0;j<3;j++)
    394 						if (m==(1<<j) || m==7-(1<<j))
    395 							tmpmask1|=(1<<j);
    396 					dp[i+1][tmpmask1][tmpmask2]+=dp[i][mask1][mask2];
    397 				}
    398 			}
    399 	LL ans=0;
    400 	for (int i=0;i<8;i++)
    401 		ans+=dp[s.size()][7][i];
    402 	cout<<ans%MOD<<endl;
    403 	return 0;
    404 }
    405 ```
    406 
    407 [1710D - Recover the Tree](/contest/1710/problem/D "Codeforces Round 810 (Div. 1)")
    408 
    409 Thank [dario2994](/profile/dario2994 "International Grandmaster dario2994"), the key part of the proof is from him.
    410 
    411 **hint1**
    412 
    413 If interval $A,B$ are all good and $A \cap B \neq \emptyset$, then $A \cap B$ is good, too.
    414 
    415 **hint2**
    416 
    417 If interval $A,B$ are all good and $A \cap B \neq \emptyset$, then $A \cup B$ is good, too.
    418 
    419 **hint3**
    420 
    421 Consider enumerating good intervals according to their length.
    422 
    423 **solution**
    424 
    425 Let's consider the interval in the order of its length (small to large) and add the edge one by one.
    426 
    427 Initially, the graph has no edge. There are $n$ connected components each consisting of exactly one vertex. Note our algorithm will guarantee that at every moment every connected component's indices compose an interval. Let $[L_i,R_i]$ be the connected component vertex $i$ in.
    428 
    429 If $[x,y]$ is good and $x$ and $y$ are not in the same connected component, we can merge $[L_x,R_y]$ into a larger connected component.
    430 
    431 Supposing $[L_x,R_y]$ consist of $k+2$ connected components now, let's call them $[l_0,r_0],[l_1,r_1],\cdots,[l_{k+1},r_{k+1}](x\in [l_0,r_0],y\in [l_{k+1},r_{k+1}])$, you can link edges like:
    432 
    433 $ \cdots-l_4-l_2-x-y-l_1-l_3-\cdots$
    434 
    435 If $[x,y]$ is good and $x$ and $y$ are in the same connected component, then we do nothing.
    436 
    437 Finally, you will get a valid tree.
    438 
    439 Total time complexity: $O(n^2)$.
    440 
    441 **proof**
    442 
    443 Let $ans[x][y]$ be if interval $[x,y]$ is good as the input data demands.
    444 
    445 Let $res[x][y]$ be if interval $[x,y]$ is good in our answer tree.
    446 
    447 Assume that the intervals we have considered are consistent with the input and we are considering $[x,y]$. Let's first prove if $ans[x][y]=1$ then $res[x][y]=1$.
    448 
    449 **proof1**
    450 
    451 If interval $x,y$ are in different connected components when $[x,y]$ is enumerated.
    452 
    453 The edge-link method will ensure $[x,y]$ is good in our answer tree.
    454 
    455 If interval $x,y$ are in the same connected components when $[x,y]$ is enumerated.
    456 
    457 Since $[x,y]$ has been merged into a larger connected component, then there must be a series of good intervals:
    458 
    459 $I_1,I_2,\cdots,I_k,I_{i+1} \cap I_i \neq \emptyset,I_i \cap [x,y] \neq \emptyset, [x,y] \subset \cup I_i$
    460 
    461 Let $J_i=I_i \cap [x,y]$
    462 
    463 Then according to hint1, all $J_i$ is good. $J_{i+1} \cap J_i \neq \emptyset, \cup J_i =[x,y]$
    464 
    465 Then we know $[x,y]$ is good in our tree, too.
    466 
    467 Let's then prove if $ans[x][y]=0$ then $res[x][y]=0$.
    468 
    469 **proof2**
    470 
    471 Assume that we are processing the interval $[x, y]$ and up to now we did not create an invalid interval. I will prove that even after "connecting" $[x, y]$ it still remains true that bad intervals are not connected.
    472 
    473 Let $I=[a,b]$ not be connected before performing the operation on $[x, y]$ and become connected later. Let CC be "connected component".
    474 
    475 Case1: $I$ does not contain $x$ or does not contain $y$, and at least one of $a,b$ is in $(R_x,L_y)$.
    476 
    477 When $a,b$ are in different CC, $I$ does not contain both of $x$ and $y$ while they are the key vertices to walk from CC $i$ to CC $i+1$.
    478 
    479 When $a,b$ are in the same CC, the link will have no influence on its connectivity.
    480 
    481 Case2: $I$ contains $[x,y]$.
    482 
    483 If $[a,b]$ becomes connected after the linking, since we only add edges in $[x,y]$, $[a,x]$ and $[y,b]$ must be connected.
    484 
    485 Since $[a,x],[x,y],[y,b]$ are all good, $[a,b]$ is good and we are happy.
    486 
    487 case3: $b \leq R_x$ or $a \geq L_y$.
    488 
    489 $I$'s connectivity will not be influenced.
    490 
    491 The proof is rather long and hard, and if you have some better ideas please share them.
    492 
    493 **code**
    494 
    495 ```
    496 #include <bits/stdc++.h>
    497 using namespace std;
    498 #define MAXN 5100
    499 typedef pair<int,int> pii;
    500 int n;
    501 char good[MAXN][MAXN];
    502 int lv[MAXN],rv[MAXN];
    503 vector<pii> ans;
    504 
    505 void work()
    506 {
    507 	ans.clear();
    508 	cin>>n;
    509 	for (int i=1;i<=n;i++)
    510 	{
    511 		lv[i]=rv[i]=i;
    512 		cin>>(good[i]+i);
    513 	}
    514 	for (int len=2;len<=n;len++)
    515 		for (int l=1;l<=n+1-len;l++)
    516 		{
    517 			int r=l+len-1;
    518 			if (good[l][r]=='1' && lv[l]!=lv[r] && rv[l]!=rv[r])
    519 			{
    520 				ans.push_back({l,r});
    521 				vector<int> tmp[2];
    522 				int id=1;
    523 				tmp[0].push_back({l});
    524 				tmp[1].push_back({r});
    525 				for (int i=rv[l]+1;i<lv[r];i++)
    526 					if (lv[i]==i)
    527 					{
    528 						ans.push_back({tmp[id].back(),i});
    529 						tmp[id].push_back(i);
    530 						id^=1;
    531 					}
    532 				int lm=lv[l];
    533 				int rm=rv[r];
    534 				for (int i=lm;i<=rm;i++)
    535 				{
    536 					lv[i]=lm;
    537 					rv[i]=rm;
    538 				}
    539 			}
    540 		}
    541 	for (auto p:ans)
    542 		cout<<p.first<<' '<<p.second<<endl;
    543 }
    544 
    545 int main()
    546 {
    547 	int casenum=1;
    548 	cin>>casenum;
    549 	for (int testcase=1;testcase<=casenum;testcase++)
    550 		work();
    551 	return 0;
    552 }
    553 ```
    554 
    555 [1710E - Two Arrays](/contest/1710/problem/E "Codeforces Round 810 (Div. 1)")
    556 
    557 **hint1.**
    558 
    559 Since they are very smart, they know the result of the game at the beginning.
    560 
    561 **hint2.**
    562 
    563 If the result is $x$, then Alice will end the game when Bob moves to a cell with score less than $x$, and something analogous holds for Bob.
    564 
    565 **hint3.**
    566 
    567 Thus, Alice can only move to a certain subset of cells, and the same holds for Bob.
    568 
    569 **solution**
    570 
    571 Knowing the above facts, it is clear that we can apply binary search on the answer $Z$, which is less than $a_1+b_1$, or Alice can end the game immediately to get $a_1+b_1$.
    572 
    573 Let's color white all the cells with $a_r+b_c \leq Z$, and black all the cells with $a_r+b_c \gt Z$.
    574 
    575 Then we shall add edges between cells in the same row or same column with different colors. These edges and cells form a bipartite graph.
    576 
    577 Consider the game on the bipartite graph. Initially, we are at cell $(1,1)$. Alice moves first, then they take turns to move. Each player can only move the cell to another place with an edge connecting them, or the other player will end the game immediately.
    578 
    579 Each cell can be visited at most $1000$ times, whoever cannot move loses.
    580 
    581 If Alice wins, then the answer is no greater than $Z$, otherwise, the answer is greater than $Z$.
    582 
    583 The version of this game where each vertex can be visited exactly once is known. If both players play optimally, the first player wins iff the starting vertex belongs to all possible maximum matchings. I'll explain why at the end of the editorial.
    584 
    585 It turns out that the condition is exactly the same even if each vertex can be visited at most $1000$ times. Let us show why.
    586 
    587 First, calculate the maximum matching. Then we erase the starting vertex and calculate the maximum matching in the new graph. If two matchings have the same size, the vertex does not belong to all maximum matchings and vice versa.
    588 
    589 Now, we know that if we copy a cell $1000$ times and copy the edges as well, this problem is exactly the same as the model mentioned above. If we consider the initial bipartite graph, it's easy to see that we only need to check whether $(1,1)$ is in all maximum matchings of the initial graph, because the maximum matching remains unchanged in the other $999$ parts.
    590 
    591 So, we have shifted the problem to see if the initial cell belongs to all matchings.
    592 
    593 According to [Kőnig's theorem in graph theory](<https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory))>, the size of the maximum matching is equal to the size of the minimum vertex cover. And if you erase all vertices in the minimum vertex cover, you get an independent set, which is the maximum independent set.
    594 
    595 Using $M$ to refer to the maximum matching, $I$ to refer to the maximum independent set, $V$ to refer to the set of vertices, we know that $|M|+|I|=|V|$
    596 
    597 So, if we erase one vertex and $|M|$ remains unchanged, then $|I|$ must be changed and vice versa.
    598 
    599 Now our issue is to calculate the maximum independent set in this graph, with or without the initial cell.
    600 
    601 Let us sort $a_i$ and $b_i$ (notice that reordering rows and columns do not change the game at all). Now the white cells form a "decreasing histogram". We can still find the starting cell $(va,vb)$.
    602 
    603 First, let's compute the maximum independent set with the initial cell.
    604 
    605 Before that, consider the following constraints:
    606 
    607 It's obvious that one column has at most one color of its cells in the independent set(we shall call it $I$), so does a row. Let's call a column white if only white cells of it are in $I$, otherwise, we shall call it black.
    608 
    609 What is the maximum size of $I$, when we must have $i$ white columns and $j$ white rows? The answer is simple. We shall select the first $i$ columns to be white and the first $j$ rows to be white, the rest of the columns and rows to be black. Then the independent set consists of black cells on black rows and black columns, and white cells on white columns and white rows. It's easy to prove this greedy strategy is correct.
    610 
    611 Now we fix the number of white columns as $i$, and try to find a $j$ that maximizes $|I|$. If we make an array $da[i]$ satisfying $a_i+b_{da[i]}\leq Z$ and $a_i + b_{da[i]+1} \gt Z$, and a similar array $db[j]$, we can easily calculate the change of $|I|$ when we turn row $j$ from black to white and vice versa, which is $n-max(i,db[j])-min(i,db[j])$, $-min(i,db[j])$ means remove the white part from $I$, $+n-max(i,db[j])$ means add the black part to $I$. For a fixed $i$, it's easy to see that the change increases with $j$.
    612 
    613 So you can maintain all positive changes of $|I|$, just decrease the $j$ with $i$ decreasing. Now you can calculate the maximum of $|I|$ in $O(n+m)$ time.
    614 
    615 It's easy to see that $da[i]$ and $db[i]$ are non-increasing, so they can be calculated in $O(n+m)$ time.
    616 
    617 For the maximum independent set without the initial cell, you just need to remove it when it is in $I$. Since the cell is always black, it is quite easy.
    618 
    619 Using binary search on the answer, you can solve the whole problem in $O((n+m)\log A+n\log n+m\log m)$, where $A$ is the maximum value of the arrays $a$ and $b$.
    620 
    621 Let us conclude with the idea of the known game on bipartite graphs.
    622 
    623 \textbf{Lemma}: The first player can win if and only if all possible maximum matchings include the initial vertex $H$.
    624 
    625 Let's prove it when $H$ satisfies the constraint.
    626 
    627 The first player can just choose any matching $M$ and move to the vertex $P$ matching with current vertex, then any unvisited neighbor of $P$ still matches with other unvisited vertices. If $P$ has a neighbor unmatched in a certain matching $M$, we find an augmenting path and a matching $M'$ that doesn't include $H$, which is in conflict with the constraint. So no matter how the second player chooses to move, the first player always has a vertex to go after that.
    628 
    629 Otherwise, we add a vertex $P$ with the only edge $(P,H)$, move the initial cell to $P$, swap the two players, then it turns into the situation above.
    630 
    631 **code**
    632 
    633 ```
    634 #include <bits/stdc++.h>
    635 
    636 using ll=long long;
    637 using std::cin;
    638 using std::cerr;
    639 using std::cout;
    640 using std::min;
    641 using std::max;
    642 
    643 template<class T>
    644 void ckmx(T &A,T B){
    645 	A<B?A=B:B;
    646 }
    647 
    648 const int N=2e5+7;
    649 
    650 int n,m,va,vb;
    651 int a[N],b[N];
    652 int da[N],db[N];
    653 
    654 bool check(int x){
    655 	ll sm=0,f1=0,f2=0;
    656 	for(int j=m,i=0;j>=1;--j){
    657 		while(i<n&&a[i+1]+b[j]<=x)
    658 			++i;
    659 		db[j]=i;
    660 		sm+=db[j];
    661 	}
    662 	for(int i=n,j=0;i>=1;--i){
    663 		while(j<m&&a[i]+b[j+1]<=x)
    664 			++j;
    665 		da[i]=j;
    666 	}
    667 	f1=f2=sm;
    668 	for(int i=n,j=m;i>=1;--i){
    669 		sm-=min(j,da[i]);
    670 		sm+=m-max(j,da[i]);
    671 		ckmx(f1,sm);
    672 		ckmx(f2,sm-(i<=va&&j<vb));
    673 		while(j&&min(db[j],i-1)<=n-max(db[j],i-1)){
    674 			sm-=min(db[j],i-1);
    675 			sm+=n-max(db[j],i-1);
    676 			--j;
    677 			ckmx(f1,sm);
    678 			ckmx(f2,sm-(i<=va&&j<vb));
    679 		}
    680 	}return f1==f2;
    681 }
    682 
    683 void Main(){
    684 	cin>>n>>m;
    685 	for(int i=1;i<=n;++i)
    686 		cin>>a[i];
    687 	for(int j=1;j<=m;++j)
    688 		cin>>b[j];
    689 	va=a[1],vb=b[1];
    690 	std::sort(a+1,a+n+1);
    691 	std::sort(b+1,b+m+1);
    692 	int l=a[1]+b[1],r=va+vb;
    693 	va=std::lower_bound(a+1,a+n+1,va)-a;
    694 	vb=std::lower_bound(b+1,b+m+1,vb)-b;
    695 	while(l<r){
    696 		int mid=(l+r)>>1;
    697 		if(check(mid))
    698 			r=mid;
    699 		else 
    700 			l=mid+1;
    701 	}cout<<l<<"\n";
    702 }
    703 
    704 inline void File(){
    705 	cin.tie(nullptr)->sync_with_stdio(false);
    706 #ifdef zxyoi
    707 	freopen("my.in","r",stdin);
    708 #endif
    709 }signed main(){File();Main();return 0;}
    710 ```