1668.md (25455B)
1 Source: https://codeforces.com/blog/entry/102013 2 3 Hope you enjoyed the problems. 4 5 **Direction Change** 6 7 [1668A - Direction Change](/contest/1668/problem/A "Codeforces Round 783 (Div. 2)") 8 9 **Solution** 10 11 The moves are symmetrical, so we can assume that $n≥m$. There is no solution if $m=1$ and $n≥3$, because one can only move up and down, but two consecutive down moves is required to reach $(n, 1)$. 12 13 Otherwise, there is a solution. 14 15 One should move downwards at least $n-1$ times, and it is forbidden to do that twice in a row, so another $n-2$ move is necessary ($1$ between each pair). So at least $n-1+n-2=2 \cdot n-3$ moves required. If $n+m$ is even, then one more, because the parity of $a+b$ changes after every move, and the parity is even before the first and after the last move, so the total number of moves should be even. 16 17 There is a construction for that lower bound: 18 19 Move alternately down and right. After reaching the $m$-th column, repeat the following sequence of moves: down, left, down, right. With this $4$ move long sequence, one can move down two times. 20 21 So we will reach $(n-1, m)$, then one more move is required, or we will reach $(n, m)$. If we add all of these moves, we get the formula: if $n+m$ is even then: $2 \cdot (m-1)+4 \cdot (n-m)/2=2 \cdot n-2$,and if $n+m$ is odd then: $2 \cdot (m-1)+4 \cdot (n-m-1)/2+1=2 \cdot n-3$. 22 23 **Implementation** 24 25 ``` 26 #include <bits/stdc++.h> 27 28 using namespace std; 29 int t, n, m; 30 int main() 31 { 32 ios_base::sync_with_stdio(false); 33 cin >> t; 34 while (t--) { 35 cin >> n >> m; 36 if (n<m) { 37 swap(n, m); 38 } 39 if (m==1 && n>=3) { 40 cout << -1 << "\n"; 41 } else { 42 cout << 2*n-2-(n+m)%2 << "\n"; 43 } 44 } 45 return 0; 46 } 47 ``` 48 49 **feedback** 50 51 Good problem: 52 53 Average problem: 54 55 Bad problem: 56 57 Did not solve: 58 59 **Social Distance** 60 61 [1668B - Social Distance](/contest/1668/problem/B "Codeforces Round 783 (Div. 2)") 62 63 **Solution** 64 65 If there is no one between the $i$-th and $j$-th person then $max(a_i, a_j)$ free chairs should be between them. 66 67 So we should find a permutation $p$ of the array $a$, when $max(p_1, p_2)+max(p_2, p_3) ... +max(p_{n-1}, p_n)+max(p_n, p_1)$ is minimal. 68 69 We can assume that the array is non-decreasing ($a_i \leq a_{i+1}$). For each $i$ ($1≤i \lt n$) the $i$ largest elements from $a$ ($a_{n-i+1}$ ... $a_n$) will appear in the formula at least $i+1$ times. Every element occurs in two segments, and we only can count $i-1$ segments twice. So we get a lower bound for the number of free chairs: $a_2+a_3+...+a_{n-1}+2 \cdot a_n$. 70 71 This lower bound is reachable for the empty chairs if the permutation of $p$ is sorted. Because $max(p_1, p_2)=p_2$, $max(p_2, p_3)=p_3$, ... $max(p_{n-1}, p_n)=p_n$, and $max(p_n, p_1)=p_n$. 72 73 They also sit on $n$ chairs. If we add all of these, we get that the answer is `YES` if: $n+ \sum_{i=1}^{n}(a_i)-min(a_i)+max(a_i)≤m$. ($a_i$={$a_1, a_2, ... a_n$}) 74 75 **Implementation (C++)** 76 77 ``` 78 #include <bits/stdc++.h> 79 80 using namespace std; 81 82 int main() 83 { 84 ios_base::sync_with_stdio(false); 85 int t; 86 cin >> t; 87 while (t--) { 88 long long n, m; 89 cin >> n >> m; 90 long long sum=0, min_val=1e9, max_val=0; 91 for (int i=1; i<=n; i++) { 92 long long x; 93 cin >> x; 94 sum+=x, min_val=min(min_val, x), max_val=max(max_val, x); 95 } 96 cout << (n+sum-min_val+max_val<=m ? "YES" : "NO") << "\n"; 97 } 98 return 0; 99 } 100 ``` 101 102 **feedback** 103 104 Good problem: 105 106 Average problem: 107 108 Bad problem: 109 110 Did not solve: 111 112 **Make it Increasing** 113 114 [1668C - Make it Increasing](/contest/1668/problem/C "Codeforces Round 783 (Div. 2)") 115 116 **Solution** 117 118 If the final array, is $b_1$, $b_2$ ... $b_n$, than the solution is surely unoptimal if there is an $2≤i≤n$, when $b_i \gt 0$, and $b_i-a_i \gt b_{i-1}$, or $b_1 \gt 0$. Because there was one unnecessary move on $b_i$ or on $b_1$. 119 120 Similarly it is unoptimal, if $b_i \lt 0$ and $b_i+a_i \lt b_{i+1}$ or $b_n \lt 0$. 121 122 We can see, that there will be a $0$ in the final array. If we fix the position of the $0$ element, than we can set the other values greadily: find the smallest value for each element, which is bigger than the previous one, and similarly before that element. 123 124 We can fix each element, and calculate the answer for that in $O(n)$ time. The minimum of these values will be the final answer. So the final complexity is $O(n^2)$. 125 126 **Implementation (C++)** 127 128 ``` 129 #include <bits/stdc++.h> 130 131 using namespace std; 132 long long n, a[5005], ans=1e18; 133 int main() 134 { 135 cin >> n; 136 for (int i=1; i<=n; i++) { 137 cin >> a[i]; 138 } 139 for (int pos=1; pos<=n; pos++) { 140 long long prev=0, sum=0; 141 for (int i=pos-1; i>=1; i--) { 142 prev+=a[i]-prev%a[i]; 143 sum+=prev/a[i]; 144 } 145 prev=0; 146 for (int i=pos+1; i<=n; i++) { 147 prev+=a[i]-prev%a[i]; 148 sum+=prev/a[i]; 149 } 150 ans=min(ans, sum); 151 } 152 cout << ans << "\n"; 153 return 0; 154 } 155 ``` 156 157 **feedback** 158 159 Good problem: 160 161 Average problem: 162 163 Bad problem: 164 165 Did not solve: 166 167 **Optimal Partition** 168 169 [1668D - Optimal Partition](/contest/1668/problem/D "Codeforces Round 783 (Div. 2)") 170 171 **Solution** 172 173 Let $dp_i$ be the answer for the first $i$ elements, and $v_{(i, j)}$ the value of the subarray $[i, j]$. With prefix sums it is easy to calculate $v_{(i, j)}$ quickly. With this we can get a $n^2$ solution: $dp_i=max(dp_j+v_{(j+1, i)})$ for $j \lt i$. 174 175 Lets call a segment winning, drawing, or losing, if the value of it is positive, $0$, or negative respectively. There is an optimal solution if the length of the drawing and losing segments are $1$. (The task is solvable without this observation, but it is harder to implement.) Proof: For a losing segment in the worst case we can get two losing segments with the same total length (the same value). 176 177 For a drawing segment with length $k$ if $k$ is even than the answer is the same if we split it into two segments with length $k/2$. For odd $k$ if the sum in the first $(k-1)/2$ or last $(k-1)/2$ elements is negative, than it is possible to increase the answer, otherwise one can split the segment into $(k-1)/2$, $1$, and $(k-1)/2$ long segments, and the answer for the new partition can't lessen. 178 179 So there is an optimal solution when only winning segments might be longer than $1$. It is easy to handle the $1$ long segments. For each $i$ ($1≤i≤n$) we have to find $j$, $0 \lt =j \lt i$, where $v_{(j+1, i)} \gt 0$, and $dp_j+v_{(j+1, i)}$ is maximal ($dp_0=0$). 180 181 If we store the prefix sums, and assign a permutation according to the prefix sums, than we can get all the positions $1≤j \lt i$, where $v_{(j+1, i)} \gt 0$. 182 183 Than $v_{(j+1, i)}=i-j$. 184 185 So when we calculate $dp_i$, we should update with $dp_i-i$. This way, finding the optimal $j$ for each $i$ is just a prefix maximum. One can solve the problem with Fenwick tree or segment tree. 186 187 Final complexity is $O(n \cdot log(n))$. 188 189 **Implementation (C++)** 190 191 ``` 192 #include <bits/stdc++.h> 193 194 using namespace std; 195 const int max_n=500005, inf=10000000; 196 int t, n, a[max_n], dp[max_n], ord[max_n], fen[max_n]; 197 long long pref[max_n]; 198 199 // Fenwick tree with prefix maximum 200 int lsb(int a) { 201 return (a & -a); 202 } 203 void add(int pos, int val) { 204 while (pos<=n) { 205 fen[pos]=max(fen[pos], val); 206 pos+=lsb(pos); 207 } 208 } 209 int ask(int pos) { 210 int val=-inf; 211 while (pos) { 212 val=max(fen[pos], val); 213 pos-=lsb(pos); 214 } 215 return val; 216 } 217 int main() 218 { 219 ios_base::sync_with_stdio(false); 220 cin.tie(0); 221 cin >> t; 222 while (t--) { 223 cin >> n; 224 vector<pair<long long, int> > v; 225 for (int i=1; i<=n; i++) { 226 cin >> a[i]; 227 pref[i]=pref[i-1]+a[i]; 228 v.push_back({pref[i], -i}); 229 } 230 sort(v.begin(), v.end()); 231 for (int i=0; i<n; i++) { 232 ord[-v[i].second]=i+1; 233 } 234 // smaller prefix sum, smaller ord[i] 235 // if j<i they have equal prefix sums, than ord[i]<ord[j], this way we cannot count [j+1, ... i] as a winning segment 236 237 for (int i=1; i<=n; i++) { 238 fen[i]=-inf; 239 } 240 241 for (int i=1; i<=n; i++) { 242 dp[i]=(dp[i-1]+(a[i]<0 ? -1 : a[i]>0 ? 1 : 0)); 243 // The last segment is 1 long. 244 245 dp[i]=max(dp[i], ask(ord[i])+i); 246 if (pref[i]>0) dp[i]=i; 247 // Segment [1, ... i] is winning, so dp[i]=i; 248 249 add(ord[i], dp[i]-i); 250 } 251 cout << dp[n] << "\n"; 252 253 for (int i=0; i<=n; i++) { 254 a[i]=0, dp[i]=0, ord[i]=0, fen[i]=0, pref[i]=0; 255 } 256 } 257 return 0; 258 } 259 ``` 260 261 **feedback** 262 263 Good problem: 264 265 Average problem: 266 267 Bad problem: 268 269 Did not solve: 270 271 **Half Queen Cover** 272 273 [1668E - Half Queen Cover](/contest/1668/problem/E "Codeforces Round 783 (Div. 2)") 274 275 **Solution** 276 277 Let's assume that there is a solution for $k$ half-queens. There are at least $n-k$ rows, and columns, which contains no half-queen. 278 279 If the uncovered rows are $r_1, r_2, ... r_a$, and the columns are $c_1, c_2, ... c_b$, (in increasing order), each diagonal (when the difference is a constant) contains at most one of the following $a+b-1$ squares: $(r_a, c_1), (r_a-1, c_1), ... (r_1, c_1), (r_1, c_2), ... (r_1, c_b)$. So a different half-queen attacks these cells. 280 281 We know that: $a+b-1≤k, n-k≤a, n-k≤b$, so $2 \cdot n≤3 \cdot k+1$. We have a lower bound for $k$. It turns out, that there is a consturction, for this $k$. 282 283 For $n=3 \cdot x+2$, $k=2 \cdot x+1$, and we can place $x+1$ in the top left corner, diagonally, and $x$ half queens in the bottom right corner diagonally. 284 285 For $n=8$ an optimal construction could be: $(1, 3)$, $(2, 2)$, $(3, 1)$, $(7, 8)$, $(8, 7)$. 286 287 If $n=3 \cdot x$, or $n=3 \cdot x+1$ we can put one or two half-queens, in the bottom right corner, and use the previous construction. 288 289 **Implementation (C++)** 290 291 ``` 292 #include <bits/stdc++.h> 293 294 using namespace std; 295 296 int main() 297 { 298 int n; 299 cin >> n; 300 cout << n/3+(n+2)/3 << "\n"; 301 if (n==1) { 302 cout << 1 << " " << 1 << "\n"; 303 return 0; 304 } 305 while (n%3!=2) { 306 cout << n << " " << n << "\n"; 307 n--; 308 } 309 int a=(n+1)/3; 310 for (int i=1; i<=a; i++) { 311 cout << i << " " << a+1-i << "\n"; 312 } 313 for (int i=1; i<a; i++) { 314 cout << n-a+i+1 << " " << n-i+1 << "\n"; 315 } 316 return 0; 317 } 318 ``` 319 320 **feedback** 321 322 Good problem: 323 324 Average problem: 325 326 Bad problem: 327 328 Did not solve: 329 330 **Edge Elimination** 331 332 [1668F - Edge Elimination](/contest/1668/problem/F "Codeforces Round 783 (Div. 2)") 333 334 **Solution** 335 336 When an edge is removed, the two neighbouring vertex have the same parity of edges. We say that an edge is odd, if the parity is odd, and the edge is even otherwise. 337 338 One can see, that a vertex with even degree will have the same amount of odd and even edges. For a vertex with odd degree, there will be one more odd edge. 339 340 Starting from the leaves, we can decide the parity of each edge (an edge connected to a leaf is odd). 341 342 If there is a contradiction somewhere than the answer is `NO`. 343 344 Otherwise, there is a construction. 345 346 In each vertex decide the removal order of the outgoing edges. Any order is good, when it always changes parity, and ends with an odd edge. Consider the directed graph with these conditions. One can see, that this graph is acyclic, so there is a topological order of that graph which will satisfy all the conditions. 347 348 Also, it is possible to solve it recursively. 349 350 **Implementation (C++)** 351 352 ``` 353 #include <bits/stdc++.h> 354 355 using namespace std; 356 const int c=200005; 357 int t, n, up[c]; 358 bool parity[c], vis[c], no_sol; 359 vector<int> edges[c]; 360 void dfs(int a) { 361 vis[a]=true; 362 int cnt[2]={0, 0}; 363 for (auto x:edges[a]) { 364 if (!vis[x]) { 365 up[x]=a; 366 dfs(x); 367 cnt[parity[x]]++; 368 } 369 } 370 if (a!=1) { 371 if (parity[a]=(cnt[0]>=cnt[1])); 372 cnt[parity[a]]++; 373 } 374 if (cnt[1]-cnt[0]<0 || cnt[1]-cnt[0]>1) { 375 no_sol=1; 376 } 377 } 378 void solve(int a) { 379 vector<int> p[2]; 380 for (auto x:edges[a]) { 381 if (x!=up[a]) { 382 p[parity[x]].push_back(x); 383 } else { 384 p[parity[a]].push_back(a); 385 } 386 } 387 int si=edges[a].size(), id=si%2; 388 for (int i=0; i<si; i++) { 389 int val=p[id].back(); 390 if (val==a) { 391 cout << a << " " << up[a] << "\n"; 392 } else { 393 solve(val); 394 } 395 p[id].pop_back(); 396 id=1-id; 397 } 398 399 } 400 int main() 401 { 402 ios_base::sync_with_stdio(false); 403 cin >> t; 404 for (int test=0; test<t; test++) { 405 cin >> n; 406 for (int i=1; i<n; i++) { 407 int a, b; 408 cin >> a >> b; 409 edges[a].push_back(b), edges[b].push_back(a); 410 } 411 dfs(1); 412 if (no_sol) { 413 cout << "NO\n"; 414 } else { 415 cout << "YES\n"; 416 solve(1); 417 } 418 419 for (int i=1; i<=n; i++) { 420 parity[i]=0, up[i]=0, vis[i]=0; 421 edges[i].clear(); 422 } 423 no_sol=0; 424 } 425 return 0; 426 } 427 ``` 428 429 **feedback** 430 431 Good problem: 432 433 Average problem: 434 435 Bad problem: 436 437 Did not solve: 438 439 **Centroid Probabilities** 440 441 [1667E - Centroid Probabilities](/contest/1667/problem/E "Codeforces Round 783 (Div. 1)") 442 443 **Solution** 444 445 Let $S=\frac{n+1}{2}$, $binom_{i, j}=\frac{i!}{j! \cdot (i-j)!}$, $dp_i$ the result of some precalculation (see below) and $ans_i$ the final answer for the $i$-th vertex. 446 447 Root the tree in vertex $1$. It is easy to see that in the possible trees the parent of vertex $2≤i≤n$ is smaller than $i$. The cetroid will be the largest vertex, where the size of its subtree is at least $S$. 448 449 For each $i$ first calculate: how many times the subtree of vertex $i$ will be at least $S$ ($dp_i$). 450 451 If $i=1$, then $dp_i=(n-1)!$. If $i \gt S$ then the $dp_i=0$. Otherwise ($2≤i≤S$) $dp_i = \sum_{j=S-1}^{n-i} binom_{n-i, j} \cdot j! \cdot (n-j-2)! \cdot (i-1)$ 452 453 Proof: Let's assume that the size of the subtree is $j+1$. Color the subtree of vertex $i$ except $i$ red. Color every other vertex except the first and the $i$-th one to blue. We have $binom_{n-i, j}$ differnt colorings, because we have to choose $j$ values between $i+1$ and $n$. ($binom_{n-i, j}$) 454 455 There are $k$ possibilities for the parent of the $k$-th smallest blue or the $k$-th smallest red vertex. ($j! \cdot (n-j-2)!$) 456 457 The parent of the $i$-th vertex can be anything. ($i-1$) 458 459 If we multiply all of these, we get the described formula. 460 461 Then $ans_i=dp_i-\sum_{j=i+1}^{n} \frac{ans_j}{i}$ 462 463 Proof: if the subtree of $i$ is at least $S$, and the centroid is not $i$, than the centroid is in the subtree of $i$. If $j$ is the centroid, there is exactly $\frac{1}{i}$ chance, that the path from $j$ to $1$ will cross vertex $i$. So we have to subract $\frac{ans_j}{i}$ for each $j \gt i$. 464 465 This gives us an $O(n^2)$ solution, which is slow because of the two sum formulas. 466 467 $\sum_{j=S-1}^{n-i} binom_{n-i, j} \cdot j! \cdot (n-j-2)! \cdot (i-1) = \sum_{j=S-1}^{n-i} \frac {(n-i)! \cdot j! \cdot (n-j-1)! \cdot (i-1)}{j! \cdot (n-i-j)!} = \sum_{j=S-1}^{n-i} \frac {(n-i)! \cdot (n-j-2)! \cdot (i-1)}{(n-i-j)!}$ 468 469 $(n-i)! \cdot (i-1)$ is a constant (for fixed $i$), and the difference between $n-j-2$ and $n-i-j$ is $i-2$, is also a constant for fixed $i$. If we reverse the inv array, then we can calculate $\sum_{j=S-1}^{n-i} \frac{(n-j-2)!}{(n-i-j)!}$ in $n \cdot log(n)$ time for $2≤i≤S$ with ntt. 470 471 We can do the calculation of $ans_i$ in linear time if we store the suffix sums of the latter values. 472 473 This gives us the final complexity: $O(n \cdot log(n))$. 474 475 **Implementation (C++)** 476 477 ``` 478 #include <bits/stdc++.h> 479 480 using namespace std; 481 482 483 484 // ntt - this code is not mine 485 const int _ = 1 << 20 , mod = 998244353 , G = 3; 486 int upd(int x) { 487 return x + (x >> 31 & mod); 488 } 489 int add(int x , int y) { 490 return upd(x + y - mod); 491 } 492 int sub (int x , int y){ 493 return upd(x - y); 494 } 495 int mul (int a, int b) { 496 return 1ll*a*b%mod; 497 } 498 int poww(long long a , int b) { 499 int tms = 1; 500 while (b) { 501 if(b & 1) tms = tms * a % mod; 502 a = a * a % mod; b >>= 1;} 503 return tms; 504 } 505 506 int dir[_] , need , invnd , w[_]; 507 void init(int len){ 508 static int L = 1; need = 1; 509 while (need < len) need <<= 1; 510 invnd = poww(need , mod - 2); 511 for (int i = 1 ; i < need ; ++i) dir[i] = (dir[i >> 1] >> 1) | (i & 1 ? need >> 1 : 0); 512 for (int &i = L ; i < need ; i <<= 1) { 513 w[i] = 1; 514 int wn = poww(G , mod / i / 2); 515 for(int j = 1 ; j < i ; ++j) w[i + j] = 1ll * w[i + j - 1] * wn % mod; 516 } 517 } 518 519 void dft(vector < int > &arr , int tmod){ 520 arr.resize(need); 521 for (int i = 1 ; i < need ; ++i) { 522 if (i < dir[i]) swap(arr[i] , arr[dir[i]]); 523 } 524 for(int i = 1 ; i < need ; i <<= 1) { 525 for (int j = 0 ; j < need ; j += i << 1) { 526 for (int k = 0 ; k < i ; ++k) { 527 int x = arr[j + k] , y = 1ll * arr[i + j + k] * w[i + k] % mod; 528 arr[j + k] = add(x , y); arr[i + j + k] = sub(x , y); 529 } 530 } 531 } 532 if(tmod == -1) { 533 reverse(arr.begin() + 1 , arr.end()); 534 for(auto &t : arr) { 535 t = 1ll * t * invnd % mod; 536 } 537 } 538 } 539 540 vector<int> multiply(vector<int> const& a, vector<int> const& b) { 541 init(a.size()+b.size()); 542 vector<int> fa(a.begin(), a.end()), fb(b.begin(), b.end()); 543 544 dft(fa, 1); 545 dft(fb, 1); 546 for (int i = 0; i < need; i++) { 547 fa[i] = 1ll * fa[i] * fb[i] % mod; 548 } 549 dft(fa, -1); 550 return fa; 551 } 552 553 const int max_n=200005; 554 long long n, fact[max_n], inv[max_n], dp[max_n], ans[max_n], suf, s; 555 vector<int> v1, v2, v3; 556 long long po(long long a, long long b) { 557 long long res=1; 558 while (b) { 559 if (b%2) res=res*a%mod; 560 a=a*a%mod; 561 b/=2; 562 } 563 return res; 564 } 565 566 567 int main() 568 { 569 cin >> n; 570 s=(n+1)/2; 571 fact[0]=1, inv[0]=1; 572 for (int i=1; i<=n; i++) { 573 fact[i]=fact[i-1]*i%mod; 574 inv[i]=po(fact[i], mod-2); 575 } 576 577 for (int i=0; i<s-1; i++) { 578 v1.push_back(fact[i]); 579 v2.push_back(inv[i]); 580 } 581 reverse(v2.begin(), v2.end()); 582 v3=multiply(v1, v2); 583 584 dp[1]=fact[n-1]; 585 for (int i=2; i<=s; i++) { 586 dp[i]=fact[n-i]*v3[i+s-4]%mod*(i-1)%mod; 587 } 588 589 for (int i=s; i>=1; i--) { 590 ans[i]=(dp[i]-suf*po(i, mod-2)%mod+mod)%mod; 591 suf=(suf+ans[i])%mod; 592 } 593 594 for (int i=1; i<=n; i++) { 595 cout << ans[i] << " "; 596 } 597 cout << "\n"; 598 return 0; 599 } 600 ``` 601 602 **feedback** 603 604 Good problem: 605 606 Average problem: 607 608 Bad problem: 609 610 Did not solve: 611 612 **Yin Yang** 613 614 [1667F - Yin Yang](/contest/1667/problem/F "Codeforces Round 783 (Div. 1)") 615 616 **Solution** 617 618 Border: cells in the first or last row or first or last column. One can see that on the border both the black and the white part is connected. So there is no solution if there is a `BWBW` subsequence on the border. 619 620 Otherwise there is a solution. 621 622 Solve an easier task first. Assume that there is no colored cell on the border. 623 624 Then there is a nice construction. Color white all cells in the first column, and in the $4*k+2$-nd and $4*k+3$-rd row, which is not in the last column. 625 626 One can see that the stripes (2 consequtive white rows) are connected, because no two initially colored cell shares a corner. Also different stripes are connected to each other because of the left column. If there is a white cell in the middle of a black stripe, then it must be orthogonally adjacent to a white stripe. 627 628 Similarly the black cells will be connected too. 629 630 If there are colored cells on the border, than it is impossible to do exactly this. But the most of the cells might be the same: the white stripes, and the white column on the left side. In this way, the white part is connected. For the black part, there might be $3$ issues: the border is not connected to the black stripes, there are isolated black cells in the $2$-nd or $n-1$-th row, and different black stripes might be unconnected. All of these issues is solvable locally with changing the color of some cells from white to black and vice versa. 631 632 **Implementation** 633 634 ``` 635 #include <bits/stdc++.h> 636 637 using namespace std; 638 const int c=505; 639 int t, n, m, fix[c][c], ans[c][c], rotcnt, change, old_cl, new_cl; 640 int fix2[c][c], ans2[c][c]; 641 void color_boundary() { 642 for (int cnt=1; cnt<=2; cnt++) { 643 for (int j=2; j<=m; j++) { 644 if (!ans[1][j]) ans[1][j]=ans[1][j-1]; 645 if (ans[1][j]!=ans[1][j-1]) change++; 646 } 647 for (int i=2; i<=n; i++) { 648 if (!ans[i][m]) ans[i][m]=ans[i-1][m]; 649 if (ans[i][m]!=ans[i-1][m]) change++; 650 } 651 for (int j=m-1; j>=1; j--) { 652 if (!ans[n][j]) ans[n][j]=ans[n][j+1]; 653 if (ans[n][j]!=ans[n][j+1]) change++; 654 } 655 for (int i=n-1; i>=1; i--) { 656 if (!ans[i][1]) ans[i][1]=ans[i+1][1]; 657 if (ans[i][1]!=ans[i+1][1]) change++; 658 } 659 if (!ans[1][1]) ans[1][1]=1; 660 if (cnt==1) change=0; 661 } 662 } 663 void rotate_90() { 664 rotcnt++; 665 for (int i=1; i<=n; i++) { 666 for (int j=1; j<=m; j++) { 667 ans2[i][j]=ans[i][j], fix2[i][j]=fix[i][j]; 668 } 669 } 670 for (int i=1; i<=n; i++) { 671 for (int j=1; j<=m; j++) { 672 ans[j][n+1-i]=ans2[i][j]; 673 fix[j][n+1-i]=fix2[i][j]; 674 } 675 } 676 swap(n, m); 677 } 678 void good_rotation() { 679 for (int cnt=1; cnt<=4; cnt++) { 680 bool same=1, opposite=0; 681 for (int i=1; i<=n; i++) { 682 if (ans[i][1]!=ans[1][1]) same=0; 683 if (1<i && i<n && ans[1][1]!=ans[i][m]) opposite=1; 684 } 685 if (!same || !opposite) rotate_90(); 686 } 687 } 688 void color_the_stripes() { 689 for (int i=2; i<n; i++) { 690 for (int j=2; j<m; j++) { 691 if (!fix[i][j]) { 692 if (i%4==2 || i%4==3) ans[i][j]=old_cl; 693 else ans[i][j]=new_cl; 694 } 695 } 696 } 697 } 698 void avoid_touching() { 699 for (int i=1; i<n; i++) { 700 if (ans[i][m-1]==ans[i+1][m] && ans[i+1][m-1]==ans[i][m] && ans[i][m]!=ans[i+1][m]) { 701 if (!fix[i][m]) ans[i][m]=3-ans[i][m]; 702 else ans[i+1][m]=3-ans[i+1][m]; 703 } 704 } 705 } 706 void boundary_stripe_connection() { 707 int first=0, last=0; 708 for (int i=1; i<=n; i++) { 709 if (ans[i][m]==new_cl) { 710 if (!first) first=i; 711 last=i; 712 } 713 } 714 if (first==0 || (last>3 && first<n-2)) return; 715 if (last<=3 && fix[4][m-1]==old_cl) { 716 for (int i=3; i<=5; i++) { 717 ans[i][m]=new_cl; 718 } 719 return; 720 } 721 if (first>=n-2 && fix[n-3][m-1]==old_cl) { 722 for (int i=n-4; i<=n-2; i++) { 723 ans[i][m]=new_cl; 724 } 725 return; 726 } 727 int x=(last<=3 ? 2 : n-2); 728 for (int i=x; i<=x+1; i++) { 729 for (int j=m-1; j<=m; j++) { 730 if (!fix[i][j]) ans[i][j]=new_cl; 731 } 732 } 733 } 734 void connect_isolated_point(int x, int y) { 735 if (ans[x-1][y]==new_cl || ans[x+1][y]==new_cl || ans[x][y+1]==new_cl) return; 736 int x1=(x==2 ? 1 : n), x2=(x==2 ? 2 : n-1), x3=(x==2 ? 3 : n-2), x4=(x==2 ? 4 : n-3); 737 if (y<=m-2 && ans[x1][y+2]==new_cl) { 738 ans[x1][y]=new_cl; 739 ans[x1][y+1]=new_cl; 740 return; 741 } 742 if (y<=m-2 && ans[x2][y+2]==new_cl) { 743 ans[x2][y+1]=new_cl; 744 return; 745 } 746 if (fix[x4][y]!=old_cl) { 747 ans[x3][y]=new_cl; 748 } else { 749 int y2=(y+1<m ? y+1 : y-1); 750 ans[x2][y2]=new_cl; 751 ans[x3][y2]=new_cl; 752 } 753 } 754 void bridge_through_the_stripe(int x) { 755 for (int j=2; j<=4; j++) { 756 bool good=1; 757 for (int i=x-1; i<=x+2; i++) { 758 if (fix[i][j]==old_cl) good=0; 759 } 760 if (good) { 761 ans[x][j]=new_cl; 762 ans[x+1][j]=new_cl; 763 return; 764 } 765 } 766 for (int i=x-1; i<=x+2; i++) { 767 if (!fix[i][3]) ans[i][3]=new_cl; 768 } 769 if (fix[x-1][3]) { 770 ans[x-1][2]=old_cl; 771 ans[x][4]=new_cl; 772 } 773 if (fix[x+2][3]) { 774 ans[x+2][2]=old_cl; 775 ans[x+1][4]=new_cl; 776 } 777 if (fix[x][3] || fix[x+1][3]) { 778 ans[x][2]=new_cl; 779 ans[x+1][2]=new_cl; 780 } 781 } 782 int main() 783 { 784 cin >> t; 785 for (int tc=1; tc<=t; tc++) { 786 cin >> n >> m; 787 for (int i=1; i<=n; i++) { 788 for (int j=1; j<=m; j++) { 789 char c; 790 cin >> c; 791 fix[i][j]=(c=='B' ? 1 : c=='W' ? 2 : 0); 792 ans[i][j]=fix[i][j]; 793 } 794 } 795 color_boundary(); 796 if (change>=4) { 797 cout << "NO\n"; 798 } else { 799 good_rotation(); 800 old_cl=ans[1][1], new_cl=3-ans[1][1]; 801 color_the_stripes(); 802 avoid_touching(); 803 boundary_stripe_connection(); 804 for (int j=2; j<m; j++) { 805 if (fix[2][j]==new_cl) connect_isolated_point(2, j); 806 if (fix[n-1][j]==new_cl) connect_isolated_point(n-1, j); 807 } 808 for (int i=6; i<=n-6; i+=4) { 809 if (ans[1][1]==ans[i][m] || ans[1][1]==ans[i+1][m]) bridge_through_the_stripe(i); 810 } 811 while (rotcnt<4) rotate_90(); 812 cout << "YES\n"; 813 for (int i=1; i<=n; i++) { 814 for (int j=1; j<=m; j++) { 815 cout << (ans[i][j]==1 ? "B" : "W"); 816 } 817 cout << "\n"; 818 } 819 } 820 rotcnt=0, change=0; 821 for (int i=1; i<=n; i++) { 822 for (int j=1; j<=m; j++) { 823 fix[i][j]=0, ans[i][j]=0; 824 fix[j][i]=0, ans[j][i]=0; 825 } 826 } 827 } 828 return 0; 829 } 830 ```