codeforces-scrape

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

1712.md (13304B)


      1 Source: https://codeforces.com/blog/entry/105919
      2 
      3 Thanks for participating in the round, we hope you liked the problems!
      4 
      5 **Solve count predictions (official div. 2)**
      6 
      7 | Handle | A | B | C | D | E1 | E2 | F |
      8 | --- | --- | --- | --- | --- | --- | --- | --- |
      9 | [Vladithur](/profile/Vladithur "Мастер Vladithur") | 16K | 8K | 3K | 900 | 500 | 50 | 4 |
     10 | [GlowCheese](/profile/GlowCheese "Мастер GlowCheese") | 14K | 9K | 5K | 500 | ? | ? | ? |
     11 | [thanhchauns2](/profile/thanhchauns2 "Кандидат в мастера thanhchauns2") | 14K | 8K | 2K | 1K | 500 | ? | ? |
     12 | [QBaraki](/profile/QBaraki "Эксперт QBaraki") | 14K | 7K | 2K | 1K | 500 | 24 | 5 |
     13 | [welleyth](/profile/welleyth "Мастер welleyth") | 16K | 10K | 4K | 1.5K | 600 | 130 | 2 |
     14 | [Kon567889](/profile/Kon567889 "Мастер Kon567889") | 14K | 10K | 5K | 2K | ? | ? | 5 |
     15 
     16 [1712A - Чудесная перестановка](/contest/1712/problem/A "Codeforces Round 813 (Div. 2)")
     17 
     18 **Hint**
     19 
     20 The smallest possible sum is $1 + 2 + \ldots + k$.
     21 
     22 **Tutorial**
     23 
     24 Tutorial is loading...
     25 
     26 **Solution**
     27 
     28 ```
     29 #include <bits/stdc++.h>
     30 
     31 #define all(x) (x).begin(), (x).end()
     32 #define allr(x) (x).rbegin(), (x).rend()
     33 #define gsize(x) (int)((x).size())
     34 
     35 const char nl = '\n';
     36 typedef long long ll;
     37 typedef long double ld;
     38 
     39 using namespace std;
     40 
     41 int main() {
     42 	ios::sync_with_stdio(0); cin.tie(0);
     43 	
     44 	int T;
     45 	cin >> T;
     46 	while (T--) {
     47 		int n, k;
     48 		cin >> n >> k;
     49 		vector<int> a(n);
     50 		for (int i = 0; i < n; i++) cin >> a[i];
     51 		
     52 		vector<int> b = a;
     53 		sort(all(b));
     54 		int x = b[k - 1];
     55 		
     56 		int ans = 0;
     57 		for (int i = 0; i < k; i++) {
     58 			if (a[i] > x) ans++;
     59 		}
     60 		cout << ans << nl;
     61 	}
     62 }
     63 ```
     64 
     65 Bonus: solve for every $k$ from $1$ to $n$ for $n \le 10^5$.
     66 
     67 [1712B - Жалкая перестановка](/contest/1712/problem/B "Codeforces Round 813 (Div. 2)")
     68 
     69 **Hints**
     70 
     71 **Hint 1**
     72 
     73 In an optimal answer, for all $1 \le i \le n$, $\operatorname{lcm}(i, p_i) = i \cdot p_i$.
     74 
     75 **Hint 2**
     76 
     77 $\operatorname{lcm}(x, x + 1) = x \cdot (x + 1)$.
     78 
     79 **Hint 3**
     80 
     81 $\operatorname{lcm}(x, x + 1) + \operatorname{lcm}(x + 1, x) = x^2 + (x + 1)^2 - 1$.
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Solution**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 
     92 #define all(x) (x).begin(), (x).end()
     93 #define allr(x) (x).rbegin(), (x).rend()
     94 #define gsize(x) (int)((x).size())
     95 
     96 const char nl = '\n';
     97 typedef long long ll;
     98 typedef long double ld;
     99 
    100 using namespace std;
    101 
    102 int main() {
    103 	ios::sync_with_stdio(0); cin.tie(0);
    104 	
    105 	int T;
    106 	cin >> T;
    107 	while (T--) {
    108 		int n;
    109 		cin >> n;
    110 		if (n % 2 == 0) {
    111 			for (int i = 1; i <= n; i += 2) {
    112 				cout << i + 1 << ' ' << i << ' ';
    113 			}
    114 			cout << nl;
    115 		} else {
    116 			cout << 1 << ' ';
    117 			for (int i = 2; i <= n; i += 2) {
    118 				cout << i + 1 << ' ' << i << ' ';
    119 			}
    120 			cout << nl;
    121 		}
    122 	}
    123 }
    124 ```
    125 
    126 Bonus: try to prove the solution without the editorial!
    127 
    128 [1712C - Очередная задача про сортировку](/contest/1712/problem/C "Codeforces Round 813 (Div. 2)")
    129 
    130 **Hints**
    131 
    132 **Hint 1**
    133 
    134 The operation only decreases numbers.
    135 
    136 **Hint 2**
    137 
    138 An array is sorted if there is no index $i$ such that $a_i \gt a_{i + 1}$.
    139 
    140 **Hint 3**
    141 
    142 Suppose there is an index $i$ such that $a_i \gt a_{i + 1}$. What operations do you need to perform to make $a_i \le a_{i + 1}$?
    143 
    144 **Tutorial**
    145 
    146 Tutorial is loading...
    147 
    148 **Solution**
    149 
    150 ```
    151 #include <bits/stdc++.h>
    152  
    153 #define all(x) (x).begin(), (x).end()
    154 #define allr(x) (x).rbegin(), (x).rend()
    155 #define gsize(x) (int)((x).size())
    156  
    157 const char nl = '\n';
    158 typedef long long ll;
    159 typedef long double ld;
    160  
    161 using namespace std;
    162  
    163 int main() {
    164 	ios::sync_with_stdio(0); cin.tie(0);
    165 	
    166 	int T;
    167 	cin >> T;
    168 	while (T--) {
    169 		int n;
    170 		cin >> n;
    171 		
    172 		vector<int> a(n);
    173 		map<int, vector<int>> p;
    174 		for (int i = 0; i < n; i++) {
    175 			cin >> a[i];
    176 			p[a[i]].push_back(i);
    177 		}
    178 		
    179 		int ans = 0;
    180 		set<int> ts;
    181 		for (int i = 0; i < n - 1; i++) {
    182 			if (a[i] > a[i + 1]) ts.insert(i);
    183 		}
    184 		
    185 		while (!ts.empty()) {
    186 			int i = *ts.begin();
    187 			int x;
    188 			if (a[i] > 0) {
    189 				x = a[i];
    190 			} else {
    191 				x = a[i + 1];
    192 			}
    193 			
    194 			for (int j: p[x]) {
    195 				a[j] = 0;
    196 				ts.erase(j - 1);
    197 				ts.erase(j);
    198 				if (j > 0 && a[j - 1] > a[j]) ts.insert(j - 1);
    199 				if (j + 1 < n && a[j] > a[j + 1]) ts.insert(j);
    200 			}
    201 			ans++;
    202 		}
    203 		
    204 		cout << ans << nl;
    205 	}
    206 }
    207 ```
    208 
    209 Bonus: solve for when $a_i$ can also be negative.
    210 
    211 [1712D - Пустой граф](/contest/1712/problem/D "Codeforces Round 813 (Div. 2)")
    212 
    213 **Hints**
    214 
    215 **Hint 1**
    216 
    217 $\operatorname{d}(u; v) \le 2 \cdot \min(a_1 \ldots a_n)$
    218 
    219 **Hint 2**
    220 
    221 *diameter* $\le 2 \cdot \min(a_1 \ldots a_n)$
    222 
    223 **Hint 3**
    224 
    225 *diameter* $\le \max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}$
    226 
    227 **Hint 4**
    228 
    229 Binary search on the answer or do a clever greedy.
    230 
    231 **Tutorial**
    232 
    233 Tutorial is loading...
    234 
    235 **Solution**
    236 
    237 ```
    238 #include <bits/stdc++.h>
    239 
    240 #define all(x) (x).begin(), (x).end()
    241 #define allr(x) (x).rbegin(), (x).rend()
    242 #define gsize(x) (int)((x).size())
    243 
    244 const char nl = '\n';
    245 typedef long long ll;
    246 typedef long double ld;
    247 
    248 using namespace std;
    249 
    250 const int inf = 1000000000;
    251 
    252 bool f(vector<int> a, int k, int ans) {
    253 	int n = gsize(a);
    254 	int dk = 0;
    255 	for (int i = 0; i < n; i++) {
    256 		if (a[i] * 2 < ans) {
    257 			a[i] = inf;
    258 			k--;
    259 			dk++;
    260 		}
    261 	}
    262 	
    263 	if (k < 0) return false;
    264 	if ((k > 0 && dk > 0) || k >= 2) return true;
    265 	
    266 	if (k == 1 && dk == 0) {
    267 		return *max_element(all(a)) >= ans;
    268 	}
    269 	
    270 	for (int i = 0; i < n - 1; i++) {
    271 		if (min(a[i], a[i + 1]) >= ans) return true;
    272 	}
    273 	
    274 	return false;
    275 }
    276 
    277 void solve() {
    278 	int n, k;
    279 	cin >> n >> k;
    280 	vector<int> a(n);
    281 	for (int i = 0; i < n; i++) cin >> a[i];
    282 	
    283 	int lb = 0, ub = inf, tans = 0;
    284 	while (lb <= ub) {
    285 		int tm = (lb + ub) / 2;
    286 		if (f(a, k, tm)) {
    287 			tans = tm;
    288 			lb = tm + 1;
    289 		} else {
    290 			ub = tm - 1;
    291 		}
    292 	}
    293 	
    294 	cout << tans << nl;
    295 }
    296 
    297 int main() {
    298 	ios::sync_with_stdio(0); cin.tie(0);
    299 	
    300 	int T;
    301 	cin >> T;
    302 	while (T--) solve();
    303 }
    304 ```
    305 
    306 Bonus: solve for every $k$ from $1$ to $n$.
    307 
    308 [1712E2 - Сумма НОК (сложная версия)](/contest/1712/problem/E2 "Codeforces Round 813 (Div. 2)")
    309 
    310 **Hints**
    311 
    312 **Hint 1**
    313 
    314 Count the number of "bad" triplets such that $\operatorname{lcm}(i, j, k) \lt i + j + k$.
    315 
    316 **Hint 2**
    317 
    318 $\operatorname{lcm}(i, j, k) \le 2 \cdot k$ in a bad triplet.
    319 
    320 **Hint 3**
    321 
    322 A triplet is bad iff $\operatorname{lcm}(i, j, k) = k$ or ($\operatorname{lcm}(i, j, k) = 2 \cdot k$ and $i + j \gt k$).
    323 
    324 **Hint 4**
    325 
    326 $\operatorname{lcm}(i, j, k) = x$ implies $i$, $j$, and $k$ are all divisors of $x$.
    327 
    328 **Hint 5**
    329 
    330 For every $k$, iterate over all pairs of divisors of $2 \cdot k$.
    331 
    332 **Hint 6**
    333 
    334 Think of the "bad" triplets as of segments $[i; k]$ with some weight.
    335 
    336 **Hint 7**
    337 
    338 Solve in offline.
    339 
    340 **Tutorial**
    341 
    342 Tutorial is loading...
    343 
    344 **Solution**
    345 
    346 ```
    347 #include <bits/stdc++.h>
    348  
    349 #define all(x) (x).begin(), (x).end()
    350 #define allr(x) (x).rbegin(), (x).rend()
    351 #define gsize(x) (int)((x).size())
    352  
    353 const char nl = '\n';
    354 typedef long long ll;
    355 typedef long double ld;
    356  
    357 using namespace std;
    358 
    359 const int maxn = 200000; 
    360 
    361 int t[(maxn + 1) * 4];
    362 
    363 void update(int v, int tl, int tr, int i, int x) {
    364 	t[v] += x;
    365 	if (tl != tr - 1) {
    366 		int tm = (tl + tr) / 2;
    367 		if (i < tm) update(2*v + 1, tl, tm, i, x);
    368 		else update(2*v + 2, tm, tr, i, x);
    369 	}
    370 }
    371 
    372 int query(int v, int tl, int tr, int l, int r) {
    373 	if (l >= r) return 0;
    374 	if (tl == l && tr == r) return t[v];
    375 	else {
    376 		int tm = (tl + tr) / 2;
    377 		int r1 = query(2*v + 1, tl, tm, l, min(r, tm));
    378 		int r2 = query(2*v + 2, tm, tr, max(l, tm), r);
    379 		return r1 + r2;
    380 	}
    381 }
    382  
    383  
    384 int main() {
    385 	ios::sync_with_stdio(0); cin.tie(0);
    386 	
    387 	vector<vector<int>> d(2*maxn + 1);
    388 	
    389 	for (int i = 1; i <= maxn; i++) {
    390 		for (int j = i; j <= 2*maxn; j += i) {
    391 			d[j].push_back(i);
    392 		}
    393 	}
    394 	
    395 	vector<vector<pair<int, int>>> segs(maxn + 1);
    396 	
    397 	for (int k = 1; k <= maxn; k++) {
    398 		for (int ti = 0; ti < gsize(d[2*k]); ti++) {
    399 			int i = d[2*k][ti], ct = 0;
    400 			
    401 			for (int tj = ti + 1; tj < gsize(d[2*k]); tj++) {
    402 				int j = d[2*k][tj];
    403 				if (j >= k) break;
    404 				if (i + j > k || (k % i == 0 && k % j == 0)) ct++;
    405 			}
    406 			
    407 			if (ct > 0)	{
    408 				segs[i].emplace_back(k, ct);
    409 			}
    410 		}
    411 	}
    412 	
    413 	
    414 	
    415 	int T;
    416 	cin >> T;
    417 	
    418 	vector<ll> ans(T);
    419 	vector<array<int, 3>> queries;
    420 	
    421 	for (int i = 0; i < T; i++) {
    422 		ll l, r;
    423 		cin >> l >> r;
    424 		queries.push_back({l, r, i});
    425 		ans[i] = (r - l + 1) * (r - l) * (r - l - 1) / 6;
    426 	}
    427 	
    428 	sort(all(queries));
    429 	
    430 	int ti = T - 1;
    431 	for (int i = maxn; i >= 1; i--) {
    432 		
    433 		// Update ST
    434 		for (auto [r, ct]: segs[i]) {
    435 			update(0, 0, maxn + 1, r, ct);
    436 		}
    437 		
    438 		// Get Answers
    439 		while (ti >= 0 && queries[ti][0] == i) {
    440 			ans[queries[ti][2]] -= query(0, 0, maxn + 1, i, queries[ti][1] + 1);
    441 			ti--;
    442 		}
    443 	}
    444 	for (int i = 0; i < T; i++) cout << ans[i] << nl;
    445 }
    446 ```
    447 
    448 Bonus: solve the problem in $\mathcal{O}((n + t) \log n)$ or better.
    449 
    450 [1712F - Триаметр](/contest/1712/problem/F "Codeforces Round 813 (Div. 2)")
    451 
    452 **Hints**
    453 
    454 **Hint 1**
    455 
    456 Let $f_v$ be the distance to the closest vertex $\in L$ to $v$. You can calculate it for every vertex in $O(n)$.
    457 
    458 **Hint 2**
    459 
    460 The distance in the new graph $\operatorname{d'}(u, v)$ is equal to $\min(\operatorname{d}(u, v), f_u + f_v + x)$
    461 
    462 **Hint 3**
    463 
    464 Suppose there is a vertex $v$ with $f_v \gt 0$. Then there is always a vertex $u$ in the subtree of $v$ such that $f_u \lt f_v$ and $depth_u$ > $depth_v$.
    465 
    466 **Hint 4**
    467 
    468 Think small-to-large merging.
    469 
    470 **Hint 5**
    471 
    472 Maintain the largest value of $depth_v$ over all $v$ with $f_v = i$ for all needed $i$.
    473 
    474 **Hint 6**
    475 
    476 In this problem, small-to-large merging works in $O(n)$.
    477 
    478 **Hint 7**
    479 
    480 The diameter is $\le n$. So you can increase it by $1$ at most $n$ times.
    481 
    482 **Tutorial**
    483 
    484 Tutorial is loading...
    485 
    486 **Solution**
    487 
    488 ```
    489 #include <bits/stdc++.h>
    490 
    491 #define all(x) (x).begin(), (x).end()
    492 #define allr(x) (x).rbegin(), (x).rend()
    493 #define gsize(x) (int)((x).size())
    494 
    495 const char nl = '\n';
    496 typedef long long ll;
    497 typedef long double ld;
    498 
    499 using namespace std;
    500 
    501 const int maxn = 1000000;
    502 int f[maxn], d[maxn];
    503 vector<int> g[maxn], g2[maxn], val[maxn];
    504 int n, q;
    505 
    506 vector<int> ans, x;
    507 
    508 void solve() {
    509 	
    510 	for (int v = n - 1; v >= 0; v--) {
    511 		for (int u: g[v]) {
    512 			if (gsize(val[u]) > gsize(val[v])) swap(val[u], val[v]);
    513 			for (int fu = 0; fu < gsize(val[u]); fu++) {
    514 				for (int qi = 0; qi < q; qi++) {
    515 					while (true) {
    516 						int fv = max(0, ans[qi] - fu - x[qi]);
    517 						if (fv < gsize(val[v]) && 
    518 							val[v][fv] + val[u][fu] - 2*d[v] >= ans[qi]) ans[qi]++;
    519 						else break;
    520 					}
    521 				}
    522 			}
    523 			for (int fu = 0; fu < gsize(val[u]); fu++) {
    524 				val[v][fu] = max(val[v][fu], val[u][fu]);
    525 			}
    526 			val[u].clear();
    527 			val[u].shrink_to_fit();
    528 		}
    529 		{
    530 			int fu = f[v];
    531 			for (int qi = 0; qi < q; qi++) {
    532 				while (true) {
    533 					int fv = max(0, ans[qi] - fu - x[qi]);			
    534 					if (fv < gsize(val[v]) && 
    535 						val[v][fv] - d[v] >= ans[qi]) ans[qi]++;
    536 					else break;
    537 				}
    538 			}
    539 			if (fu == gsize(val[v])) {
    540 				val[v].push_back(d[v]);
    541 			}
    542 		}
    543 	}
    544 	
    545 	for (int i = 0; i < q; i++) {
    546 		ans[i]--;
    547 	}
    548 }
    549 
    550 int main() {
    551 	ios::sync_with_stdio(0); cin.tie(0);
    552 	
    553 	cin >> n;
    554 	
    555 	vector<int> deg(n);
    556 	for (int i = 1; i < n; i++) {
    557 		int p;
    558 		cin >> p;
    559 		d[i] = d[p - 1] + 1;
    560 		g[p - 1].push_back(i);
    561 		g2[i].push_back(p - 1);
    562 	}
    563 	
    564 	{
    565 		queue<int> qe;
    566 		vector<bool> used(n, false);
    567 		for (int i = 0; i < n; i++) {
    568 			if (gsize(g2[i]) + gsize(g[i]) == 1) {
    569 				qe.push(i);
    570 				used[i] = true;
    571 			}
    572 		}
    573 		
    574 		while (!qe.empty()) {
    575 			int v = qe.front();
    576 			qe.pop();
    577 			for (int u: g[v]) {
    578 				if (used[u]) continue;
    579 				f[u] = f[v] + 1;
    580 				qe.push(u);
    581 				used[u] = true;
    582 			}
    583 			
    584 			for (int u: g2[v]) {
    585 				if (used[u]) continue;
    586 				f[u] = f[v] + 1;
    587 				qe.push(u);
    588 				used[u] = true;
    589 			}
    590 		}
    591 	}
    592 	
    593 	cin >> q;
    594 	for (int i = 0; i < q; i++) {
    595 		int tx;
    596 		cin >> tx;
    597 		x.push_back(tx);
    598 		ans.push_back(0);
    599 	}
    600 	
    601 	solve();
    602 	
    603 	for (int tans: ans) cout << tans << ' ';
    604 	cout << nl;
    605 }
    606 ```
    607 
    608 Bonus: solve for $n, q \le 10^6$.
    609 
    610 **Don't forget to rate the problems!**
    611 
    612 **Problem Feedback**
    613 
    614 **A**
    615 
    616 * Good problem
    617 * Mid problem
    618 * Bad problem
    619 
    620 **B**
    621 
    622 * Good problem
    623 * Mid problem
    624 * Bad problem
    625 
    626 **C**
    627 
    628 * Good problem
    629 * Mid problem
    630 * Bad problem
    631 
    632 **D**
    633 
    634 * Good problem
    635 * Mid problem
    636 * Bad problem
    637 
    638 **E1**
    639 
    640 * Good problem
    641 * Mid problem
    642 * Bad problem
    643 
    644 **E2**
    645 
    646 * Good problem
    647 * Mid problem
    648 * Bad problem
    649 
    650 **F**
    651 
    652 * Good problem
    653 * Mid problem
    654 * Bad problem
    655 
    656 PS: Solution codes probably will be added later.
    657 
    658 **UPD: explanations of the references:**
    659 
    660 **Click here**
    661 
    662 Hope you liked them!
    663 
    664 **A**
    665 
    666 The quote is just a modification of the original title of KonoSuba.
    667 
    668 **B**
    669 
    670 This is just something I invented, no reference here. Hope you liked the short poem!
    671 
    672 **C**
    673 
    674 The quote is the meme "people die when they are killed" in the Fate series, changed to fit the programming context. And the title is just "Fate Zero" changed to "Sort Zero".
    675 
    676 **D**
    677 
    678 "Do you have a wish?" is a recurring phrase in the LN series [HakoMari](https://myanimelist.net/manga/55215/Utsuro_no_Hako_to_Zero_no_Maria), referring to the wish granting "boxes". The title is just "Empty Box" changed to "Empty Graph". Also, "O_o" is a reference to one of the main characters, "O".
    679 
    680 **E**
    681 
    682 The quote can probably be traced to many origins, but I personally modified the quote "We are legion, for we are many" from the series 86. There were also a lot of 6's and 8's in the sample, which might have helped you guess.
    683 
    684 **F**
    685 
    686 I didn't really think about this one, just modified a quote from Vivy a bit.
    687 
    688 **UPD2: added solution codes (better late than never...)**