codeforces-scrape

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

1783.md (14425B)


      1 Source: https://codeforces.com/blog/entry/111194
      2 
      3 [1783A - Make it Beautiful](/contest/1783/problem/A "Educational Codeforces Round 141 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     n = int(input())
     17     a = list(map(int, input().split()))
     18     if a[0] == a[n - 1]:
     19         print('NO')
     20     else:
     21         print('YES')
     22         print(a[n - 1], end = ' ')
     23         print(*(a[0:n-1]))
     24 ```
     25 
     26 [1783B - Matrix of Differences](/contest/1783/problem/B "Educational Codeforces Round 141 (Rated for Div. 2)")
     27 
     28 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution (Neon)**
     35 
     36 ```
     37 #include <bits/stdc++.h>
     38 
     39 using namespace std;
     40 
     41 #define forn(i, n) for (int i = 0; i < int(n); ++i)
     42 
     43 int main() {
     44   int t;
     45   cin >> t;
     46   while (t--) {
     47     int n;
     48     cin >> n;
     49     vector<vector<int>> a(n, vector<int>(n));
     50     int l = 1, r = n * n, t = 0;
     51     forn(i, n) {
     52       forn(j, n) {
     53         if (t) a[i][j] = l++;
     54         else a[i][j] = r--;
     55         t ^= 1;
     56       }
     57       if (i & 1) reverse(a[i].begin(), a[i].end());
     58     }
     59     forn(i, n) forn(j, n) cout << a[i][j] << " \n"[j == n - 1];
     60   }
     61 }
     62 ```
     63 
     64 [1783C - Yet Another Tournament](/contest/1783/problem/C "Educational Codeforces Round 141 (Rated for Div. 2)")
     65 
     66 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     67 
     68 **Tutorial**
     69 
     70 Tutorial is loading...
     71 
     72 **Solution (Neon)**
     73 
     74 ```
     75 #include <bits/stdc++.h>
     76 
     77 using namespace std;
     78 
     79 int main() {
     80   ios::sync_with_stdio(false); cin.tie(0);
     81   int t;
     82   cin >> t;
     83   while (t--) {
     84     int n, m;
     85     cin >> n >> m;
     86     vector<int> a(n);
     87     for (auto &x : a) cin >> x;
     88     auto b = a;
     89     sort(b.begin(), b.end());
     90     int ans = 0;
     91     for (int i = 0; i < n && b[i] <= m; ++i) {
     92       m -= b[i];
     93       ++ans;
     94     }
     95     if (ans != 0 && ans != n && m + b[ans - 1] >= a[ans]) ++ans;
     96     cout << n + 1 - ans << '\n';
     97   }
     98 }
     99 ```
    100 
    101 [1783D - Different Arrays](/contest/1783/problem/D "Educational Codeforces Round 141 (Rated for Div. 2)")
    102 
    103 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    104 
    105 **Tutorial**
    106 
    107 Tutorial is loading...
    108 
    109 **Solution (BledDest)**
    110 
    111 ```
    112 #include<bits/stdc++.h>
    113 
    114 using namespace std;
    115 
    116 const int MOD = 998244353;
    117 
    118 int add(int x, int y)
    119 {
    120     x += y;
    121     while(x >= MOD) x -= MOD;
    122     while(x < 0) x += MOD;
    123     return x;
    124 }   
    125 
    126 const int ZERO = 100000;
    127 
    128 int dp[2][ZERO * 2];
    129 
    130 void recalc(int x)
    131 {
    132     for(int i = 0; i < ZERO * 2; i++)
    133         dp[1][i] = 0;
    134 
    135     for(int i = 0; i < ZERO * 2; i++)
    136     {
    137         if(dp[0][i] == 0) continue;
    138         int nx = x + i;
    139         dp[1][nx] = add(dp[1][nx], dp[0][i]);
    140         if(nx != ZERO)
    141             dp[1][2 * ZERO - nx] = add(dp[1][2 * ZERO - nx], dp[0][i]);
    142     }
    143 
    144     for(int i = 0; i < ZERO * 2; i++)
    145         dp[0][i] = dp[1][i];
    146 }
    147 
    148 int main()
    149 {
    150     int n;
    151     cin >> n;
    152     vector<int> a(n);
    153     for(int i = 0; i < n; i++)
    154         cin >> a[i];
    155     dp[0][ZERO] = 1;
    156     for(int i = 1; i + 1 < n; i++)
    157         recalc(a[i]);
    158     int ans = 0;
    159     for(int i = 0; i < ZERO * 2; i++)
    160         ans = add(ans, dp[0][i]);
    161     cout << ans << endl;
    162 }
    163 ```
    164 
    165 [1783E - Game of the Year](/contest/1783/problem/E "Educational Codeforces Round 141 (Rated for Div. 2)")
    166 
    167 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    168 
    169 **Tutorial**
    170 
    171 Tutorial is loading...
    172 
    173 **Solution (BledDest)**
    174 
    175 ```
    176 #include <bits/stdc++.h>
    177 
    178 #define forn(i, n) for (int i = 0; i < int(n); i++)
    179 
    180 using namespace std;
    181 
    182 int main() {
    183 	int t;
    184 	scanf("%d", &t);
    185 	while (t--){
    186 		int n;
    187 		scanf("%d", &n);
    188 		vector<int> a(n), b(n);
    189 		forn(i, n) scanf("%d", &a[i]);
    190 		forn(i, n) scanf("%d", &b[i]);
    191 		vector<int> dx(n + 1);
    192 		forn(i, n) if (b[i] < a[i]){
    193 			++dx[b[i]];
    194 			--dx[a[i]];
    195 		}
    196 		forn(i, n) dx[i + 1] += dx[i];
    197 		vector<int> ans;
    198 		for (int k = 1; k <= n; ++k){
    199 			bool ok = true;
    200 			for (int nk = k; nk <= n; nk += k)
    201 				ok &= dx[nk] == 0;
    202 			if (ok)
    203 				ans.push_back(k);
    204 		}
    205 		printf("%d\n", int(ans.size()));
    206 		for (int k : ans) printf("%d ", k);
    207 		puts("");
    208 	}
    209 	return 0;
    210 }
    211 ```
    212 
    213 [1783F - Double Sort II](/contest/1783/problem/F "Educational Codeforces Round 141 (Rated for Div. 2)")
    214 
    215 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    216 
    217 **Tutorial**
    218 
    219 Tutorial is loading...
    220 
    221 **Solution (BledDest)**
    222 
    223 ```
    224 #include<bits/stdc++.h>
    225 
    226 using namespace std;
    227 
    228 const int N = 5043;
    229 
    230 vector<int> g[N];
    231 int mt[N];
    232 int u[N];
    233 vector<vector<int>> cycle[2];
    234 vector<int> a[2];
    235 int n;
    236 int vs[2];
    237 vector<vector<int>> inter;
    238 
    239 bool kuhn(int x)
    240 {
    241     if(u[x]) return false;
    242     u[x] = true;
    243     for(auto y : g[x])
    244     {
    245         if(mt[y] == x) continue;
    246         if(mt[y] == -1 || kuhn(mt[y]))
    247         {
    248             mt[y] = x;
    249             return true;
    250         }
    251     }
    252     return false;
    253 }
    254 
    255 int find_intersection(const vector<int>& x, const vector<int>& y)
    256 {
    257     for(auto i : x)
    258         for(auto j : y)
    259             if(i == j)
    260                 return i;
    261     return -1;
    262 }
    263 
    264 int main()
    265 {
    266     scanf("%d", &n);
    267     for(int k = 0; k < 2; k++)
    268     {
    269         a[k].resize(n);
    270         for(int j = 0; j < n; j++)
    271         {
    272             scanf("%d", &a[k][j]);
    273             a[k][j]--;
    274         }    
    275     }
    276 
    277     for(int k = 0; k < 2; k++)
    278     {
    279         vector<bool> used(n);
    280         for(int i = 0; i < n; i++)
    281         {
    282             if(used[i]) continue;
    283             vector<int> cur;
    284             int j = i;
    285             while(!used[j])
    286             {
    287                 cur.push_back(j);
    288                 used[j] = true;
    289                 j = a[k][j];            
    290             }
    291             cycle[k].push_back(cur);
    292         }
    293         vs[k] = cycle[k].size();
    294     }
    295 
    296     inter.resize(vs[0], vector<int>(vs[1]));
    297 
    298     for(int i = 0; i < vs[0]; i++)
    299         for(int j = 0; j < vs[1]; j++)
    300         {
    301             inter[i][j] = find_intersection(cycle[0][i], cycle[1][j]);
    302             if(inter[i][j] != -1)
    303                 g[i].push_back(j);
    304         }
    305 
    306     for(int i = 0; i < vs[1]; i++)
    307         mt[i] = -1;
    308     for(int i = 0; i < vs[0]; i++)
    309     {
    310         for(int j = 0; j < vs[0]; j++)
    311             u[j] = false;
    312         kuhn(i);
    313     }
    314     
    315     set<int> res;
    316     for(int i = 0; i < n; i++) res.insert(i);
    317     for(int i = 0; i < vs[1]; i++)
    318         if(mt[i] != -1)
    319             res.erase(inter[mt[i]][i]);
    320 
    321     printf("%d\n", res.size());
    322     for(auto x : res) printf("%d ", x + 1);
    323     puts("");
    324 }
    325 ```
    326 
    327 [1783G - Weighed Tree Radius](/contest/1783/problem/G "Educational Codeforces Round 141 (Rated for Div. 2)")
    328 
    329 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    330 
    331 **Tutorial**
    332 
    333 Tutorial is loading...
    334 
    335 **Solution 1 (adedalic)**
    336 
    337 ```
    338 #include<bits/stdc++.h>
    339 
    340 using namespace std;
    341 
    342 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    343 #define sz(a) int((a).size())
    344 
    345 #define x first
    346 #define y second
    347 
    348 typedef long long li;
    349 typedef long double ld;
    350 typedef pair<int, int> pt;
    351 
    352 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    353 	return out << "(" << p.x << ", " << p.y << ")";
    354 }
    355 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    356 	fore(i, 0, sz(v)) {
    357 		if(i) out << " ";
    358 		out << v[i];
    359 	}
    360 	return out;
    361 }
    362 
    363 const int INF = int(1e9);
    364 const li INF64 = li(1e18);
    365 const ld EPS = 1e-9;
    366 
    367 const int LOG = 18;
    368 const int N = int(2e5) + 55;
    369 
    370 int n;
    371 vector<int> a;
    372 vector<int> g[N];
    373 
    374 inline bool read() {
    375 	if(!(cin >> n))
    376 		return false;
    377 	a.resize(n);
    378 	fore (i, 0, n)
    379 		cin >> a[i];
    380 	fore (i, 0, n - 1) {
    381 		int u, v;
    382 		cin >> u >> v;
    383 		u--, v--;
    384 		g[u].push_back(v);
    385 		g[v].push_back(u);
    386 	}
    387 	return true;
    388 }
    389 
    390 int p[LOG][N];
    391 int h[N], tin[N], tout[N], T = 0;
    392 
    393 void precalcLca(int v, int pr) {
    394 	tin[v] = T++;
    395 	h[v] = 0;
    396 	if (pr != v)
    397 		h[v] = h[pr] + 1;
    398 	p[0][v] = pr;
    399 	fore (pw, 0, LOG - 1)
    400 		p[pw + 1][v] = p[pw][p[pw][v]];
    401 
    402 	for (int to : g[v]) {
    403 		if (to == pr)
    404 			continue;
    405 		precalcLca(to, v);
    406 	}
    407 	tout[v] = T;
    408 }
    409 
    410 bool isParent(int l, int v) {
    411 	return tin[l] <= tin[v] && tout[v] <= tout[l];
    412 }
    413 
    414 int lca(int u, int v) {
    415 	if (isParent(u, v))
    416 		return u;
    417 	if (isParent(v, u))
    418 		return v;
    419 	
    420 	for (int pw = LOG - 1; pw >= 0; pw--) 
    421 		if (!isParent(p[pw][v], u))
    422 			v = p[pw][v];
    423 	assert(!isParent(v, u));
    424 	assert(isParent(p[0][v], u));
    425 	return p[0][v];
    426 }
    427 
    428 int getFarthest(int s) {
    429 	vector<int> used(n, 0);
    430 	queue<int> q;
    431 
    432 	used[s] = 1;
    433 	q.push(s);
    434 	int v;
    435 	while (!q.empty()) {
    436 		v = q.front(); 
    437 		q.pop();
    438 		for (int to : g[v]) {
    439 			if (used[to])
    440 				continue;
    441 			used[to] = 1;
    442 			q.push(to);
    443 		}
    444 	}
    445 	return v;
    446 }
    447 
    448 int getDist(int u, int v) {
    449 	return h[u] + h[v] - 2 * h[lca(u, v)];
    450 }
    451 
    452 const int M = int(2e5);
    453 vector<pt> ops[4 * M];
    454 
    455 void setOp(int v, int l, int r, int lf, int rg, const pt &op) {
    456 	if (l >= r || lf >= rg) return;
    457 	if (l == lf && r == rg) {
    458 		ops[v].push_back(op);
    459 		return;
    460 	}
    461 	int mid = (l + r) / 2;
    462 	if (lf < mid)
    463 		setOp(2 * v + 1, l, mid, lf, min(mid, rg), op);
    464 	if (rg > mid)
    465 		setOp(2 * v + 2, mid, r, max(lf, mid), rg, op);
    466 }
    467 
    468 void updDiam(int &s, int &t, int &curD, const pt &op) {
    469 	int v = op.x;
    470 	a[v] = op.y;
    471 
    472 	int ns = s, nt = t, nD = curD;
    473 
    474 	vector<pt> cds = {{s, v}, {v, t}, {v, v}};
    475 	for (auto &c : cds) {
    476 		int d1 = getDist(c.x, c.y);
    477 		if (nD < a[c.x] + d1 + a[c.y]) {
    478 			nD = a[c.x] + d1 + a[c.y];
    479 			ns = c.x, nt = c.y;
    480 		}
    481 	}
    482 	s = ns;
    483 	t = nt;
    484 	curD = nD;
    485 }
    486 
    487 vector<int> ans;
    488 
    489 void calcDiams(int v, int l, int r, int s, int t, int curD) {
    490 	for (auto &op : ops[v])
    491 		updDiam(s, t, curD, op);
    492 	if (r - l > 1) {
    493 		int mid = (l + r) / 2;
    494 		calcDiams(2 * v + 1, l, mid, s, t, curD);
    495 		calcDiams(2 * v + 2, mid, r, s, t, curD);
    496 	}
    497 	else
    498 		ans[l] = (curD + 1) / 2;
    499 	
    500 	for (auto &op : ops[v])
    501 		a[op.first] = 0;
    502 }
    503 
    504 inline void solve() {
    505 	precalcLca(0, 0);
    506 	int s = getFarthest(0);
    507 	int t = getFarthest(s);
    508 
    509 	int m;
    510 	cin >> m;
    511 	vector<int> lst(n, 0);
    512 	fore (i, 0, m) {
    513 		int v, x;
    514 		cin >> v >> x;
    515 		v--;
    516 
    517 		setOp(0, 0, m, lst[v], i, {v, a[v]});
    518 		lst[v] = i;
    519 		a[v] = x;
    520 	}
    521 	fore (v, 0, n)
    522 		setOp(0, 0, m, lst[v], m, {v, a[v]});
    523 
    524 	ans.resize(m, -1);
    525 	a.assign(n, 0);
    526 	calcDiams(0, 0, m, s, t, getDist(s, t));
    527 
    528 	fore (i, 0, m)
    529 		cout << ans[i] << '\n';
    530 }
    531 
    532 int main() {
    533 #ifdef _DEBUG
    534 	freopen("input.txt", "r", stdin);
    535 	int tt = clock();
    536 #endif
    537 	ios_base::sync_with_stdio(false);
    538 	cin.tie(0), cout.tie(0);
    539 	cout << fixed << setprecision(15);
    540 	
    541 	if(read()) {
    542 		solve();
    543 		
    544 #ifdef _DEBUG
    545 		cerr << "TIME = " << clock() - tt << endl;
    546 		tt = clock();
    547 #endif
    548 	}
    549 	return 0;
    550 }
    551 ```
    552 
    553 **Solution 2 (adedalic)**
    554 
    555 ```
    556 #include<bits/stdc++.h>
    557 
    558 using namespace std;
    559 
    560 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    561 #define sz(a) int((a).size())
    562 
    563 #define x first
    564 #define y second
    565 
    566 typedef long long li;
    567 typedef long double ld;
    568 typedef pair<int, int> pt;
    569 
    570 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    571 	return out << "(" << p.x << ", " << p.y << ")";
    572 }
    573 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    574 	fore(i, 0, sz(v)) {
    575 		if(i) out << " ";
    576 		out << v[i];
    577 	}
    578 	return out;
    579 }
    580 
    581 const int INF = int(1e9);
    582 const li INF64 = li(1e18);
    583 const ld EPS = 1e-9;
    584 
    585 const int LOG = 18;
    586 const int N = int(2e5) + 55;
    587 
    588 int n;
    589 vector<int> a;
    590 vector<int> g[N];
    591 
    592 inline bool read() {
    593 	if(!(cin >> n))
    594 		return false;
    595 	a.resize(n);
    596 	fore (i, 0, n)
    597 		cin >> a[i];
    598 	fore (i, 0, n - 1) {
    599 		int u, v;
    600 		cin >> u >> v;
    601 		u--, v--;
    602 		g[u].push_back(v);
    603 		g[v].push_back(u);
    604 	}
    605 	return true;
    606 }
    607 
    608 struct Lca {
    609 	vector<int> log2, tin;
    610 	vector< vector<int> > hs;
    611 	int T = 0;
    612 
    613 	void dfs(int v, int p, int cdepth) {
    614 		tin[v] = T++;
    615 		hs[0][tin[v]] = cdepth;
    616 		for (int to : g[v]) {
    617 			if (to == p)
    618 				continue;
    619 			dfs(to, v, cdepth + 1);
    620 			hs[0][T++] = cdepth;
    621 		}
    622 	}
    623 
    624 	void init() {
    625 		log2.assign(2 * n, 0);
    626 		fore (i, 2, sz(log2))
    627 			log2[i] = log2[i / 2] + 1;
    628 		hs.assign(log2.back() + 1, vector<int>(2 * n, INF));
    629 
    630 		tin.assign(n, 0);
    631 		T = 0;
    632 
    633 		dfs(0, -1, 0);
    634 		assert(T < 2 * n);
    635 
    636 		fore (pw, 0, sz(hs) - 1) {
    637 			fore (i, 0, T - (1 << pw))
    638 				hs[pw + 1][i] = min(hs[pw][i], hs[pw][i + (1 << pw)]);
    639 		}
    640 	}
    641 
    642 	int getMin(int u, int v) {
    643 		if (tin[u] > tin[v])
    644 			swap(u, v);
    645 		int len = log2[tin[v] + 1 - tin[u]];
    646 		int d = min(hs[len][tin[u]], hs[len][tin[v] + 1 - (1 << len)]);
    647 //		cerr << u << " " << v << ": " << d << endl;
    648 		return d;
    649 	}
    650 	inline int getH(int v) {
    651 		return hs[0][tin[v]];
    652 	}
    653 } lcaST;
    654 
    655 int getFarthest(int s) {
    656 	vector<int> used(n, 0);
    657 	queue<int> q;
    658 
    659 	used[s] = 1;
    660 	q.push(s);
    661 	int v;
    662 	while (!q.empty()) {
    663 		v = q.front(); 
    664 		q.pop();
    665 		for (int to : g[v]) {
    666 			if (used[to])
    667 				continue;
    668 			used[to] = 1;
    669 			q.push(to);
    670 		}
    671 	}
    672 	return v;
    673 }
    674 
    675 int getDist(int u, int v) {
    676 	return lcaST.getH(u) + lcaST.getH(v) - 2 * lcaST.getMin(u, v);
    677 }
    678 
    679 const int M = int(2e5);
    680 vector<pt> ops[4 * M];
    681 
    682 void setOp(int v, int l, int r, int lf, int rg, const pt &op) {
    683 	if (l >= r || lf >= rg) return;
    684 	if (l == lf && r == rg) {
    685 		ops[v].push_back(op);
    686 		return;
    687 	}
    688 	int mid = (l + r) / 2;
    689 	if (lf < mid)
    690 		setOp(2 * v + 1, l, mid, lf, min(mid, rg), op);
    691 	if (rg > mid)
    692 		setOp(2 * v + 2, mid, r, max(lf, mid), rg, op);
    693 }
    694 
    695 void updDiam(int &s, int &t, int &curD, const pt &op) {
    696 	int v = op.x;
    697 	a[v] = op.y;
    698 
    699 	int ns = s, nt = t, nD = curD;
    700 
    701 	vector<pt> cds = {{s, v}, {v, t}, {v, v}};
    702 	for (auto &c : cds) {
    703 		int d1 = getDist(c.x, c.y);
    704 		if (nD < a[c.x] + d1 + a[c.y]) {
    705 			nD = a[c.x] + d1 + a[c.y];
    706 			ns = c.x, nt = c.y;
    707 		}
    708 	}
    709 	s = ns;
    710 	t = nt;
    711 	curD = nD;
    712 }
    713 
    714 vector<int> ans;
    715 
    716 void calcDiams(int v, int l, int r, int s, int t, int curD) {
    717 	for (auto &op : ops[v])
    718 		updDiam(s, t, curD, op);
    719 	if (r - l > 1) {
    720 		int mid = (l + r) / 2;
    721 		calcDiams(2 * v + 1, l, mid, s, t, curD);
    722 		calcDiams(2 * v + 2, mid, r, s, t, curD);
    723 	}
    724 	else
    725 		ans[l] = (curD + 1) / 2;
    726 	
    727 	for (auto &op : ops[v])
    728 		a[op.first] = 0;
    729 }
    730 
    731 inline void solve() {
    732 	lcaST.init();
    733 	int s = getFarthest(0);
    734 	int t = getFarthest(s);
    735 
    736 	int m;
    737 	cin >> m;
    738 	vector<int> lst(n, 0);
    739 	fore (i, 0, m) {
    740 		int v, x;
    741 		cin >> v >> x;
    742 		v--;
    743 
    744 		setOp(0, 0, m, lst[v], i, {v, a[v]});
    745 		lst[v] = i;
    746 		a[v] = x;
    747 	}
    748 	fore (v, 0, n)
    749 		setOp(0, 0, m, lst[v], m, {v, a[v]});
    750 
    751 	ans.resize(m, -1);
    752 	a.assign(n, 0);
    753 	calcDiams(0, 0, m, s, t, getDist(s, t));
    754 
    755 	fore (i, 0, m)
    756 		cout << ans[i] << '\n';
    757 }
    758 
    759 int main() {
    760 #ifdef _DEBUG
    761 	freopen("input.txt", "r", stdin);
    762 	int tt = clock();
    763 #endif
    764 	ios_base::sync_with_stdio(false);
    765 	cin.tie(0), cout.tie(0);
    766 	cout << fixed << setprecision(15);
    767 	
    768 	if(read()) {
    769 		solve();
    770 		
    771 #ifdef _DEBUG
    772 		cerr << "TIME = " << clock() - tt << endl;
    773 		tt = clock();
    774 #endif
    775 	}
    776 	return 0;
    777 }
    778 ```