codeforces-scrape

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

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