codeforces-scrape

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

1416.md (20410B)


      1 Source: https://codeforces.com/blog/entry/83036
      2 
      3 *Several unexpected Kuhn solutions passed for D1F. Could you please discuss your solutions in the comments and prove its correctness or provide any counter-examples. Author's solution uses flows with Dinic.*
      4 
      5 Editorial is not completed yet. Problem D1F will be added later. Hope you enjoyed the problemset!
      6 
      7 Editorial was/will be written by [bthero](/profile/bthero "Master bthero") and [BledDest](/profile/BledDest "International Grandmaster BledDest").
      8 
      9 Our tester [namanbansal013](/profile/namanbansal013 "Expert namanbansal013") has made amazing video-tutorials on YouTube for problems [D2D/D1B](https://youtu.be/LS51ijnR8jI) and [D2E/D1C](https://youtu.be/rBSuG-_R3Yo). Make sure to check them out and show him some love!
     10 
     11 Finally added the editorial for D1E. Currently it is very complicated and error-prone.
     12 
     13 Div2A by [bthero](/profile/bthero "Master bthero")
     14 
     15 **Editorial**
     16 
     17 Tutorial is loading...
     18 
     19 **Code in C++ (BThero)**
     20 
     21 ```
     22 // chrono::system_clock::now().time_since_epoch().count()
     23 #include<bits/stdc++.h>
     24 
     25 #define pb push_back
     26 #define eb emplace_back
     27 #define mp make_pair
     28 #define fi first
     29 #define se second
     30 #define all(x) (x).begin(), (x).end()
     31 #define debug(x) cerr << #x << " = " << x << endl;
     32 
     33 using namespace std;
     34 
     35 typedef long long ll;
     36 typedef pair<int, int> pii;
     37 
     38 const int MAXN = (int)1e3 + 5;
     39 
     40 int n, k;
     41 int arr[MAXN];
     42 
     43 void solve() {
     44   scanf("%d %d", &n, &k);
     45   
     46   for (int i = 1; i <= n; ++i) {
     47     scanf("%d", &arr[i]);
     48   }
     49   
     50   int mn = min_element(arr + 1, arr + n + 1) - arr;
     51   int ans = 0;
     52   
     53   for (int i = 1; i <= n; ++i) {
     54     if (i != mn) {
     55       while (arr[i] + arr[mn] <= k) {
     56         arr[i] += arr[mn];
     57         ++ans;
     58       }
     59     }
     60   }
     61   
     62   printf("%d\n", ans);
     63 }
     64 
     65 int main() {
     66   int tt;
     67   scanf("%d", &tt);
     68   
     69   while (tt--) {
     70     solve();
     71   }
     72 
     73   return 0;
     74 }
     75 ```
     76 
     77 Div2B by [nkamzabek](/profile/nkamzabek "Expert nkamzabek")
     78 
     79 **Editorial**
     80 
     81 Tutorial is loading...
     82 
     83 **Code in C++ (hugopm)**
     84 
     85 ```
     86 #include <bits/stdc++.h>
     87 #define len(v) ((int)((v).size()))
     88 #define all(v) (v).begin(), (v).end()
     89 #define rall(v) (v).rbegin(), (v).rend()
     90 #define chmax(x, v) x = max((x), (v))
     91 #define chmin(x, v) x = min((x), (v))
     92 using namespace std;
     93 using ll = long long;
     94 
     95 void solve() {
     96 	int n, tar;
     97 	cin >> n >> tar;
     98 	int curMid = 0;
     99 	for (int i = 0; i < n; ++i) {
    100 		int x; cin >> x;
    101 		int r;
    102 		if (tar % 2 == 0 && x == tar/2)
    103 			r = (curMid++) % 2;
    104 		else if (2*x < tar)
    105 			r = 0;
    106 		else
    107 			r = 1;
    108 		cout << r << " \n"[i==n-1];
    109 	}
    110 }
    111 
    112 int main() {
    113 	ios::sync_with_stdio(false), cin.tie(0);
    114 
    115 	int nbTests;
    116 	cin >> nbTests;
    117 	for (int iTest = 0; iTest < nbTests; ++iTest) {
    118 		solve();
    119 	}
    120 }
    121 ```
    122 
    123 Div2C/Div1A by [nkamzabek](/profile/nkamzabek "Expert nkamzabek")
    124 
    125 **Editorial**
    126 
    127 Tutorial is loading...
    128 
    129 **Code in C++ (BThero)**
    130 
    131 ```
    132 // chrono::system_clock::now().time_since_epoch().count()
    133 #include<bits/stdc++.h>
    134 
    135 #define pb push_back
    136 #define eb emplace_back
    137 #define mp make_pair
    138 #define fi first
    139 #define se second
    140 #define all(x) (x).begin(), (x).end()
    141 #define debug(x) cerr << #x << " = " << x << endl;
    142 
    143 using namespace std;
    144 
    145 typedef long long ll;
    146 typedef pair<int, int> pii;
    147 
    148 const int MAXN = (int)3e5 + 5;
    149 
    150 int f[MAXN], last[MAXN], arr[MAXN], ans[MAXN];
    151 int n;
    152 
    153 void solve() {
    154   scanf("%d", &n);
    155   
    156   for (int i = 1; i <= n; ++i) {
    157     f[i] = last[i] = 0;
    158     ans[i] = -1;
    159   }
    160   
    161   for (int i = 1; i <= n; ++i) {
    162     scanf("%d", &arr[i]);
    163   }
    164   
    165   for (int i = 1; i <= n; ++i) {
    166     int x = arr[i];
    167     f[x] = max(f[x], i - last[x]);
    168     last[x] = i;
    169   }
    170   
    171   for (int x = 1; x <= n; ++x) {
    172     f[x] = max(f[x], n - last[x] + 1);
    173     
    174     for (int i = f[x]; i <= n && ans[i] == -1; ++i) {
    175       ans[i] = x;
    176     }
    177   }
    178   
    179   for (int i = 1; i <= n; ++i) {
    180     printf("%d%c", ans[i], " \n"[i == n]);
    181   }
    182 }
    183 
    184 int main() {
    185   int tt;
    186   scanf("%d", &tt);
    187   
    188   while (tt--) {
    189     solve();
    190   }
    191 
    192   return 0;
    193 }
    194 ```
    195 
    196 Div2D/Div1B by [nkamzabek](/profile/nkamzabek "Expert nkamzabek")
    197 
    198 **Editorial**
    199 
    200 Tutorial is loading...
    201 
    202 **Code in C++ (BThero)**
    203 
    204 ```
    205 // chrono::system_clock::now().time_since_epoch().count()
    206 #include<bits/stdc++.h>
    207 
    208 #define pb push_back
    209 #define eb emplace_back
    210 #define mp make_pair
    211 #define fi first
    212 #define se second
    213 #define all(x) (x).begin(), (x).end()
    214 #define debug(x) cerr << #x << " = " << x << endl;
    215 
    216 using namespace std;
    217 
    218 typedef long long ll;
    219 typedef pair<int, int> pii;
    220 
    221 const int MAXN = (int)1e4 + 5;
    222 
    223 vector<array<int, 3>> ans;
    224 int arr[MAXN];
    225 int n;
    226 
    227 void go(int x, int y, int z) {
    228   arr[x] -= x * z;
    229   arr[y] += x * z;
    230   ans.pb({x, y, z});
    231 }
    232 
    233 void solve() {
    234   scanf("%d", &n);
    235   
    236   for (int i = 1; i <= n; ++i) {
    237     scanf("%d", &arr[i]);
    238   }
    239   
    240   ans.clear();
    241   int sum = accumulate(arr + 1, arr + n + 1, 0);
    242   
    243   if (sum % n) {
    244     printf("-1\n");
    245     return;
    246   }
    247   
    248   for (int i = 2; i <= n; ++i) {
    249     if (arr[i] % i) {
    250       go(1, i, i - arr[i] % i);
    251     }
    252     
    253     go(i, 1, arr[i] / i);
    254   }
    255   
    256   for (int i = 2; i <= n; ++i) {
    257     go(1, i, sum / n);
    258   }
    259   
    260   for (int i = 1; i <= n; ++i) {
    261     assert(arr[i] == sum / n);
    262   }
    263   
    264   assert((int)ans.size() <= 3 * n);
    265   printf("%d\n", (int)ans.size());
    266   
    267   for (auto &[x, y, z] : ans) {
    268     printf("%d %d %d\n", x, y, z);
    269   }
    270 }
    271 
    272 int main() {
    273   int tt;
    274   scanf("%d", &tt);
    275   
    276   while (tt--) {
    277     solve();
    278   }
    279 
    280   return 0;
    281 }
    282 ```
    283 
    284 Div2E/Div1C by [DimmyT](/profile/DimmyT "Master DimmyT")
    285 
    286 **Editorial**
    287 
    288 Tutorial is loading...
    289 
    290 **Code in C++ (RedDreamer)**
    291 
    292 ```
    293 #include <bits/stdc++.h>
    294  
    295 #define mp make_pair
    296 #define pb push_back
    297 #define f first
    298 #define s second
    299 #define ll long long
    300 #define forn(i, a, b) for(int i = (a); i <= (b); ++i)
    301 #define forev(i, b, a) for(int i = (b); i >= (a); --i)
    302 #define VAR(v, i) __typeof( i) v=(i)
    303 #define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
    304 #define all(x) (x).begin(), (x).end()
    305 #define sz(x) ((int)(x).size())
    306 #define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
    307  
    308 using namespace std;
    309  
    310 const int maxn = (int)5e6 + 100;
    311 const int maxm = (int)1e6 + 100;
    312 const int mod = (int)1e9 + 7;
    313 const int P = (int) 1e6 + 7; 
    314 const double pi = acos(-1.0);
    315  
    316 #define inf mod
    317  
    318 typedef long double ld;
    319 typedef pair<int, int> pii;
    320 typedef pair<ll, ll> pll;
    321 typedef vector<int> vi;   
    322 typedef vector<ll> Vll;               
    323 typedef vector<pair<int, int> > vpii;
    324 typedef vector<pair<ll, ll> > vpll;                        
    325 
    326 int n, t[2][maxn], id = 1;
    327 ll dp[2][30];
    328 vi g[maxn];
    329 
    330 void add(int x, int pos){
    331 	int v = 0;
    332 	forev(i, 29, 0){
    333 		int bit = ((x >> i) & 1);
    334 		if(!t[bit][v]) t[bit][v] = id++;
    335 		v = t[bit][v];
    336 		g[v].pb(pos);	
    337 	}
    338 }
    339 void go(int v, int b = 29){
    340 	int l = t[0][v], r = t[1][v];
    341 	if(l) go(l, b - 1);
    342 	if(r) go(r, b - 1);
    343 	if(!l || !r) return;
    344 	ll res = 0;
    345 	int ptr = 0;
    346 	for(auto x : g[l]){
    347 		while(ptr < sz(g[r]) && g[r][ptr] < x) ptr++;
    348 		res += ptr;
    349 	}
    350 	dp[0][b] += res;
    351 	dp[1][b] += sz(g[l]) * 1ll * sz(g[r]) - res;
    352 }
    353 void solve(){
    354 	scanf("%d", &n);
    355 	forn(i, 1, n){
    356 		int x;
    357 		scanf("%d", &x);
    358 		add(x, i);
    359 	}
    360 	go(0);
    361 	ll inv = 0;
    362 	int res = 0;
    363 	forn(i, 0, 29){
    364 		inv += min(dp[0][i], dp[1][i]);
    365 		if(dp[1][i] < dp[0][i])
    366 			res += (1 << i);
    367 	}
    368 	printf("%lld %d", inv, res);
    369 }
    370  
    371 int main () {
    372 	int t = 1;
    373 	//scanf("%d", &t);
    374 	while(t--) solve();
    375 }
    376 ```
    377 
    378 Div2F/Div1D by [DimmyT](/profile/DimmyT "Master DimmyT")
    379 
    380 **Editorial**
    381 
    382 Tutorial is loading...
    383 
    384 **Code in C++ (BThero)**
    385 
    386 ```
    387 // chrono::system_clock::now().time_since_epoch().count()
    388 #include<bits/stdc++.h>
    389 
    390 #define pb push_back
    391 #define eb emplace_back
    392 #define mp make_pair
    393 #define fi first
    394 #define se second
    395 #define all(x) (x).begin(), (x).end()
    396 #define debug(x) cerr << #x << " = " << x << endl;
    397 
    398 using namespace std;
    399 
    400 typedef long long ll;
    401 typedef pair<int, int> pii;
    402 
    403 const int MAXN = (int)5e5 + 5;
    404 const int MAXM = (int)3e5 + 5;
    405 const int MAXQ = (int)5e5 + 5;
    406 
    407 pii e[MAXM], que[MAXQ], t[MAXN << 2];
    408 vector<int> adj[MAXN];
    409 int tin[MAXN], tout[MAXN], timer;
    410 int par[MAXN], arr[MAXN];
    411 bool del[MAXM];
    412 int n, m, q;
    413 
    414 int getPar(int x) {
    415   if (x == par[x]) {
    416     return x;
    417   }
    418   
    419   return par[x] = getPar(par[x]);
    420 }
    421 
    422 void uni(int a, int b) {
    423   a = getPar(a);
    424   b = getPar(b);
    425   
    426   if (a == b) {
    427     return;
    428   }
    429   
    430   ++n;
    431   par[n] = n;
    432   par[a] = n;
    433   par[b] = n;
    434   adj[n].pb(a);
    435   adj[n].pb(b);
    436 }
    437 
    438 void dfs(int v) {
    439   tin[v] = ++timer;
    440   
    441   for (int to : adj[v]) {
    442     dfs(to);
    443   }
    444   
    445   tout[v] = timer;
    446 }
    447 
    448 pii segMax(int v, int tl, int tr, int l, int r) {
    449   if (l > r || tl > r || tr < l) {
    450     return mp(0, 0);
    451   }
    452   
    453   if (l <= tl && tr <= r) {
    454     return t[v];
    455   }
    456   
    457   int mid = (tl + tr) >> 1;
    458   int c1 = (v << 1), c2 = (c1 | 1);
    459   
    460   return max(segMax(c1, tl, mid, l, r), segMax(c2, mid + 1, tr, l, r));
    461 }
    462 
    463 void updPos(int v, int tl, int tr, int p, pii x) {
    464   if (tl == tr) {
    465     t[v] = x;
    466     return;
    467   }
    468   
    469   int mid = (tl + tr) >> 1;
    470   int c1 = (v << 1), c2 = (c1 | 1);
    471   
    472   if (p <= mid) {
    473     updPos(c1, tl, mid, p, x);
    474   }
    475   else {
    476     updPos(c2, mid + 1, tr, p, x);
    477   }
    478   
    479   t[v] = max(t[c1], t[c2]);
    480 }
    481 
    482 void solve() {
    483   scanf("%d %d %d", &n, &m, &q);
    484   
    485   for (int i = 1; i <= n; ++i) {
    486     scanf("%d", &arr[i]);
    487   }
    488   
    489   for (int i = 1; i <= m; ++i) {
    490     int u, v;
    491     scanf("%d %d", &u, &v);
    492     e[i] = mp(u, v);
    493   }
    494   
    495   for (int i = 1; i <= q; ++i) {
    496     int a, b;
    497     scanf("%d %d", &a, &b);
    498     que[i] = mp(a, b);
    499     
    500     if (a == 2) {
    501       del[b] = 1;
    502     }
    503   }
    504   
    505   for (int i = 1; i <= n; ++i) {
    506     par[i] = i;
    507   }
    508   
    509   for (int i = 1; i <= m; ++i) {
    510     if (!del[i]) {
    511       uni(e[i].fi, e[i].se);
    512     }
    513   }
    514   
    515   for (int i = q; i > 0; --i) {
    516     int tp = que[i].fi;
    517     
    518     if (tp == 2) {
    519       int id = que[i].se;
    520       uni(e[id].fi, e[id].se);
    521     }
    522     else {
    523       que[i].se = getPar(que[i].se);
    524     }
    525   }
    526   
    527   for (int i = 1; i <= n; ++i) {
    528     if (getPar(i) == i) {
    529       dfs(i);
    530     }
    531   }
    532   
    533   for (int i = 1; i <= n; ++i) {
    534     updPos(1, 1, n, tin[i], mp(arr[i], tin[i]));
    535   }
    536   
    537   for (int i = 1; i <= q; ++i) {
    538     int tp = que[i].fi;
    539    
    540     if (tp == 1) {
    541       int v = que[i].se;
    542       pii tmp = segMax(1, 1, n, tin[v], tout[v]);
    543       
    544       if (tmp.fi == 0) {
    545         printf("0\n");
    546       }
    547       else {
    548         printf("%d\n", tmp.fi);
    549         updPos(1, 1, n, tmp.se, mp(0, 0));
    550       }
    551     }
    552   }
    553 }
    554 
    555 int main() {
    556   int tt = 1;
    557   
    558   while (tt--) {
    559     solve();
    560   }
    561 
    562   return 0;
    563 }
    564 ```
    565 
    566 Div1E by [bthero](/profile/bthero "Master bthero")
    567 
    568 **Editorial**
    569 
    570 Tutorial is loading...
    571 
    572 **Code in C++ (BThero)**
    573 
    574 ```
    575 // chrono::system_clock::now().time_since_epoch().count()
    576 #include<bits/stdc++.h>
    577 
    578 #define __DBG 1
    579 #define pb push_back
    580 #define eb emplace_back
    581 #define mp make_pair
    582 #define fi first
    583 #define se second
    584 #define all(x) (x).begin(), (x).end()
    585 #define debug(x) if (__DBG) cerr << #x << " = " << x << endl;
    586 
    587 using namespace std;
    588 
    589 typedef long long ll;
    590 typedef pair<int, int> pii;
    591 typedef pair<ll, ll> pll;
    592 
    593 const int MAXN = (int)5e5 + 5;
    594 
    595 int arr[MAXN];
    596 int n;
    597 
    598 void solve() {
    599   scanf("%d", &n);
    600   
    601   for (int i = 1; i <= n; ++i) {
    602     scanf("%d", &arr[i]);
    603   }
    604   
    605   int zero = 0, two = -1;
    606   set<pll> one;
    607   ll shifter = 0;
    608   int sign = 1;
    609   
    610   for (int i = 1; i <= n; ++i) {
    611     int x = arr[i];
    612     
    613     if (two != -1) {
    614       zero += 2;
    615       sign = 1;
    616       shifter = 0;
    617       one.clear();
    618       
    619       if (two < x) {
    620         one.insert(mp(x - two, x - two));
    621       }
    622     }
    623     else if (!one.empty()) {
    624       zero++;
    625       
    626       if (sign == -1) {
    627         // shifter - idx >= x
    628         // shifter - x >= idx
    629         // idx <= shifter - x
    630         ll lim = shifter - x;
    631         
    632         while (!one.empty() && one.begin() -> se <= lim) {
    633           one.erase(one.begin());
    634         }
    635         
    636         if (!one.empty() && one.begin() -> fi <= lim) {
    637           pll it = mp(lim + 1, one.begin() -> se);
    638           one.erase(one.begin());
    639           assert(it.fi <= it.se);
    640           one.insert(it);
    641         }
    642       }
    643       else {
    644         // shifter + idx >= x
    645         // idx >= x - shifter
    646         ll lim = x - shifter;
    647         
    648         while (!one.empty() && one.rbegin() -> fi >= lim) {
    649           one.erase(--one.end());
    650         }
    651         
    652         if (!one.empty() && one.rbegin() -> se >= lim) {
    653           pll it = mp(one.rbegin() -> fi, lim - 1);
    654           one.erase(--one.end());
    655           assert(it.fi <= it.se);
    656           one.insert(it);
    657         }
    658       }
    659       
    660       shifter = x - shifter;
    661       sign *= -1;
    662     }
    663     else {
    664       sign = -1;
    665       shifter = x;
    666       int lim = min(arr[i - 1] - 1, x - 1);
    667       
    668       if (1 <= lim) {
    669         one.insert(mp(1, lim));
    670       }
    671     }
    672     
    673     // consider x/2!
    674     two = -1;
    675     
    676     if (x % 2 == 0) {
    677       int y = x / 2;
    678       ll val = (y - shifter) / sign;
    679       auto it = one.lower_bound(mp(val + 1, (ll)-1e18));
    680       bool found = 0;
    681       
    682       if (it != one.begin()) {
    683         --it;
    684         
    685         if (it -> fi <= val && val <= it -> se) {
    686           found = 1;
    687         }
    688       }
    689       
    690       if (found) {
    691         two = y;
    692       }
    693       else {
    694         one.insert(mp(val, val));
    695       }
    696     }
    697   }
    698   
    699   int ans;
    700   
    701   if (two != -1) {
    702     ans = zero + 2;
    703   }
    704   else if (!one.empty()) {
    705     ans = zero + 1;
    706   }
    707   else {
    708     ans = zero;
    709   }
    710   
    711   printf("%d\n", 2 * n - ans);
    712 }
    713 
    714 int main() {
    715   int tt;
    716   scanf("%d", &tt);
    717   
    718   while (tt--) {
    719     solve();
    720   }
    721 
    722   return 0;
    723 }
    724 ```
    725 
    726 **Alternative solution code in C++ (hugopm)**
    727 
    728 ```
    729 #include <bits/stdc++.h>
    730 #define int long long
    731 #define len(v) ((int)((v).size()))
    732 #define all(v) (v).begin(), (v).end()
    733 #define rall(v) (v).rbegin(), (v).rend()
    734 #define chmax(x, v) x = max((x), (v))
    735 #define chmin(x, v) x = min((x), (v))
    736 using namespace std;
    737 using pii = pair<int, int>;
    738 
    739 struct EndSet {
    740 	set<int> points;
    741 	pii seg = {1, 0};
    742 
    743 	int cbase = 0, cdir = 1;
    744 
    745 	void setFree(int mx) {
    746 		points.clear(), cbase = 0, cdir = 1;
    747 		seg = {1, mx};
    748 	}
    749 
    750 	void setPush(int x) {
    751 		setFree(0);
    752 		points.insert(x);
    753 	}
    754 
    755 	void rotate(int balance) {
    756 		cbase = balance - cbase;
    757 		cdir = -cdir;
    758 		seg = {balance - seg.second, balance - seg.first};
    759 	}
    760 
    761 	int tr(int x) {
    762 		return cbase + cdir*x;
    763 	}
    764 
    765 	int anti(int x) {
    766 		return cdir * (x - cbase);
    767 	}
    768 
    769 	bool in(int x) {
    770 		if (points.count(anti(x)))
    771 			return true;
    772 		return (seg.first <= x && x <= seg.second);	
    773 	}
    774 
    775 	void push(int x) {
    776 		points.insert(anti(x));
    777 	}
    778 
    779 	void popBelow(int x) {
    780 		seg.second = min(seg.second, x);
    781 		auto nextIt = [&] {
    782 			return (cdir == 1 ? prev(points.end()) : points.begin());
    783 		};
    784 		while (!points.empty() && tr(*nextIt()) > x)
    785 			points.erase(nextIt());
    786 	}
    787 	
    788 	bool empty() {
    789 		return points.empty() && seg.first > seg.second;
    790 	}
    791 };
    792 
    793 void solve() {
    794 	int n; cin >> n;
    795 	EndSet util;
    796 	int curAns = 0;
    797 	for (int i = 0; i < n; ++i) {
    798 		int x; cin >> x;
    799 		util.popBelow(x-1); 
    800 		if (x % 2 == 0 && util.in(x/2)) {
    801 			curAns += 2;
    802 			util.setPush(x/2);
    803 		} else if (util.empty()) {
    804 			if (x % 2 == 0)
    805 				curAns += 1, util.setPush(x/2);
    806 			else
    807 				util.setFree(x-1);
    808 		} else {
    809 			curAns += 1;
    810 			if (x % 2 == 0)
    811 				util.push(x/2);
    812 		}
    813 		util.rotate(x);
    814 	}	
    815 	cout << 2*n - curAns << "\n";
    816 }
    817 
    818 signed main() {
    819 	ios::sync_with_stdio(false), cin.tie(0);
    820 	int nbTests;
    821 	cin >> nbTests;
    822 	for (int iTest = 0; iTest < nbTests; ++iTest) {
    823 		solve();
    824 	}
    825 }
    826 ```
    827 
    828 Div1F by [bthero](/profile/bthero "Master bthero")
    829 
    830 **Editorial**
    831 
    832 ...
    833 
    834 **Code in C++ (BThero)**
    835 
    836 ```
    837 // chrono::system_clock::now().time_since_epoch().count()
    838 #include<bits/stdc++.h>
    839 
    840 #define pb push_back
    841 #define eb emplace_back
    842 #define mp make_pair
    843 #define fi first
    844 #define se second
    845 #define all(x) (x).begin(), (x).end()
    846 #define debug(x) cerr << #x << " = " << x << endl;
    847 
    848 using namespace std;
    849 
    850 typedef long long ll;
    851 typedef pair<int, int> pii;
    852 typedef vector<int> vi;
    853 typedef vector<vi> vvi;
    854 
    855 const int dx[] = {0, 1, 0, -1};
    856 const int dy[] = {1, 0, -1, 0};
    857 const char dc[] = {'R', 'D', 'L', 'U'};
    858 const int INF = (int)1e6;
    859 const int MAXN = (int)3e5 + 5;
    860 
    861 namespace {
    862   struct Edge {
    863     int v, to, f, c;
    864     
    865     Edge() {
    866       v = to = f = c = 0;
    867     }
    868     
    869     Edge(int v, int to, int c) : v(v), to(to), c(c) {
    870       f = 0;
    871     }
    872   };
    873   
    874   vector<Edge> e;
    875   vector<int> adj[MAXN];
    876   int ptr[MAXN], d[MAXN], q[MAXN];
    877   int S, T, newS, newT, V;
    878   int cap[2][MAXN];
    879   
    880   void prep() {
    881     e.clear();
    882     
    883     for (int i = 0; i < V; ++i) {
    884       adj[i].clear();
    885       ptr[i] = d[i] = q[i] = 0;
    886       cap[0][i] = cap[1][i] = 0;
    887     }
    888   }
    889   
    890   void addEdge(int u, int v, int c) {
    891     //printf("E %d %d %d\n", u, v, c);
    892   
    893     adj[u].pb((int)e.size());
    894     e.pb(Edge(u, v, c));
    895     adj[v].pb((int)e.size());
    896     e.pb(Edge(v, u, 0));
    897   }
    898   
    899   void addEdgeLim(int u, int v) {
    900     //printf("F %d %d\n", u, v);
    901     ++cap[0][v];
    902     ++cap[1][u];
    903   }
    904   
    905   bool bfs() {
    906     fill(d, d + V, -1);
    907     d[newS] = 0;
    908     int l = 0, r = 0;
    909     q[r++] = newS;
    910     
    911     while (l < r) {
    912       int v = q[l++];
    913       
    914       for (int id : adj[v]) {
    915         if (e[id].f < e[id].c) {
    916           int to = e[id].to;
    917           
    918           if (d[to] == -1) {
    919             d[to] = d[v] + 1;
    920             q[r++] = to;
    921           }
    922         }
    923       }
    924     }
    925     
    926     return d[newT] != -1;
    927   }
    928   
    929   int dfs(int v, int flow = INF) {
    930     if (!flow || v == newT) {
    931       return flow;
    932     }
    933     
    934     int sum = 0;
    935     
    936     for (; ptr[v] < (int)adj[v].size(); ++ptr[v]) {
    937       int id = adj[v][ptr[v]];
    938       int to = e[id].to;
    939       int can = e[id].c - e[id].f;
    940       
    941       if (d[to] != d[v] + 1 || can == 0) {
    942         continue;
    943       }
    944       
    945       int pushed = dfs(to, min(flow, can));
    946       
    947       if (pushed > 0) {
    948         e[id].f += pushed;
    949         e[id ^ 1].f -= pushed;
    950         sum += pushed;
    951         flow -= pushed;
    952         
    953         if (flow == 0) {
    954           return sum;
    955         }
    956       }
    957     }
    958     
    959     return sum;
    960   }
    961   
    962   int maxFlow() {
    963     int ret = 0;
    964     
    965     while (bfs()) {
    966       fill(ptr, ptr + V, 0);
    967     
    968       while (int pushed = dfs(newS)) {
    969         ret += pushed;
    970       }
    971     }
    972     
    973     return ret;
    974   }
    975 }
    976 
    977 vvi arr, follow;
    978 int n, m;
    979 
    980 bool inside(int x, int y) {
    981   return 0 <= x && x < n && 0 <= y && y < m;
    982 }
    983 
    984 int id(int x, int y) {
    985   return x * m + y;
    986 }
    987 
    988 void solve() {
    989   scanf("%d %d", &n, &m);
    990   arr = follow = vvi(n, vi(m, -1));
    991   S = n * m;
    992   T = S + 1;
    993   newS = T + 1;
    994   newT = newS + 1;
    995   V = newT + 1;
    996   prep();
    997   
    998   for (int i = 0; i < n; ++i) {
    999     for (int j = 0; j < m; ++j) {
   1000       scanf("%d", &arr[i][j]);
   1001     }
   1002   }
   1003   
   1004   for (int i = 0; i < n; ++i) {
   1005     for (int j = 0; j < m; ++j) {
   1006       for (int dir = 0; dir < 4; ++dir) {
   1007         int ni = i + dx[dir], nj = j + dy[dir];
   1008         
   1009         if (inside(ni, nj)) {
   1010           if (arr[ni][nj] < arr[i][j]) {
   1011             follow[i][j] = dir;
   1012           }
   1013           else if ((i + j) % 2 == 0 && arr[ni][nj] == arr[i][j]) {
   1014             addEdge(id(i, j), id(ni, nj), 1);
   1015           }
   1016         }
   1017       }
   1018       
   1019       if (follow[i][j] == -1) {
   1020         // important vertex
   1021         if ((i + j) % 2) {
   1022           addEdgeLim(id(i, j), T);
   1023         }
   1024         else {
   1025           addEdgeLim(S, id(i, j));
   1026         }
   1027       }
   1028       else {
   1029         if ((i + j) % 2) {
   1030           addEdge(id(i, j), T, 1);
   1031         }
   1032         else {
   1033           addEdge(S, id(i, j), 1);
   1034         }
   1035       }
   1036     }
   1037   }
   1038   
   1039   for (int i = 0; i <= T; ++i) {
   1040     if (cap[0][i] > 0) {
   1041       addEdge(newS, i, cap[0][i]);
   1042     }
   1043     
   1044     if (cap[1][i] > 0) {
   1045       addEdge(i, newT, cap[1][i]);
   1046     }
   1047   }
   1048   
   1049   addEdge(T, S, INF);
   1050   maxFlow();
   1051   
   1052   for (int id : adj[newS]) {
   1053     if (e[id].f != e[id].c) {
   1054       printf("NO\n");
   1055       return;
   1056     }
   1057   }
   1058   
   1059   vvi ansv, ansc;
   1060   ansv = ansc = vvi(n, vi(m));
   1061   
   1062   for (int i = 0; i < n; ++i) {
   1063     for (int j = 0; j < m; ++j) {
   1064       int dir = follow[i][j];
   1065       
   1066       if (dir != -1) {
   1067         int ni = i + dx[dir], nj = j + dy[dir];
   1068         ansv[i][j] = arr[i][j] - arr[ni][nj];
   1069         ansc[i][j] = dir;
   1070       }
   1071     }
   1072   }
   1073   
   1074   for (Edge it : e) {
   1075     int v = it.v, to = it.to;
   1076     
   1077     if (max(v, to) < n * m && it.f == it.c && it.c == 1) {
   1078       int ax = v / m, ay = v % m;
   1079       int bx = to / m, by = to % m;
   1080       ansv[ax][ay] = arr[ax][ay] - 1;
   1081       ansv[bx][by] = 1;
   1082       
   1083       for (int dir = 0; dir < 4; ++dir) {
   1084         if (mp(ax + dx[dir], ay + dy[dir]) == mp(bx, by)) {
   1085           ansc[ax][ay] = dir;
   1086           ansc[bx][by] = (dir + 2) % 4;
   1087         }
   1088       }
   1089     }
   1090   }
   1091   
   1092   printf("YES\n");
   1093   
   1094   for (int i = 0; i < n; ++i) {
   1095     for (int j = 0; j < m; ++j) {
   1096       printf("%d%c", ansv[i][j], " \n"[j == m - 1]);
   1097     }
   1098   }
   1099   
   1100   for (int i = 0; i < n; ++i) {
   1101     for (int j = 0; j < m; ++j) {
   1102       printf("%c%c", dc[ansc[i][j]], " \n"[j == m - 1]);
   1103     }
   1104   }
   1105 }
   1106 
   1107 int main() {
   1108   int tt;
   1109   scanf("%d", &tt);
   1110   
   1111   while (tt--) {
   1112     solve();
   1113   }
   1114 
   1115   return 0;
   1116 }
   1117 ```