codeforces-scrape

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

961.md (11392B)


      1 Source: https://codeforces.com/blog/entry/58743
      2 
      3 [961A - Tetris](/contest/961/problem/A "Educational Codeforces Round 41 (Rated for Div. 2)")
      4 
      5 **Editorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 #ifdef _DEBUG
     18 	freopen("input.txt", "r", stdin);
     19 //	freopen("output.txt", "w", stdout);
     20 #endif
     21 
     22 	int n, m;
     23 	cin >> n >> m;
     24 	vector<int> cnt(n);
     25 
     26 	for (int i = 0; i < m; ++i) {
     27 		int col;
     28 		cin >> col;
     29 		++cnt[col - 1];
     30 	}
     31 	
     32 	cout << *min_element(cnt.begin(), cnt.end()) << endl;
     33 	
     34 	return 0;
     35 }
     36 ```
     37 
     38 [961B - Lecture Sleep](/contest/961/problem/B "Educational Codeforces Round 41 (Rated for Div. 2)")
     39 
     40 **Editorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution (Vovuh)**
     45 
     46 ```
     47 #include <bits/stdc++.h>
     48 
     49 using namespace std;
     50 
     51 int main() {
     52 #ifdef _DEBUG
     53 	freopen("input.txt", "r", stdin);
     54 //	freopen("output.txt", "w", stdout);
     55 #endif
     56 
     57 	int n, k;
     58 	scanf("%d %d", &n, &k);
     59 	
     60 	vector<int> a(n);
     61 	vector<int> t(n);
     62 	
     63 	int overall = 0;
     64 	
     65 	for (int i = 0; i < n; ++i)
     66 		scanf("%d", &a[i]);
     67 	for (int i = 0; i < n; ++i)
     68 		scanf("%d", &t[i]);
     69 		
     70 	vector<int> pr(n);
     71 	for (int i = 0; i < n; ++i) {
     72 		if (i) pr[i] += pr[i - 1];
     73 		if (t[i] == 0) pr[i] += a[i];
     74 		else overall += a[i];
     75 	}
     76 	
     77 	int add = 0;
     78 	for (int i = k - 1; i < n; ++i)
     79 		add = max(add, pr[i] - (i >= k ? pr[i - k] : 0));
     80 	
     81 	printf("%d\n", overall + add);
     82 	
     83 	return 0;
     84 }
     85 ```
     86 
     87 [961C - Chessboard](/contest/961/problem/C "Educational Codeforces Round 41 (Rated for Div. 2)")
     88 
     89 **Editorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution (Ajosteen)**
     94 
     95 ```
     96 #include <bits/stdc++.h>
     97 
     98 using namespace std;
     99 
    100 const int N = 109;
    101 
    102 int n;
    103 string a[4][N];
    104 
    105 int main() {
    106 	cin >> n;
    107 	for(int k = 0; k < 4; ++k)
    108 		for(int i = 0; i < n; ++i){
    109 			cin >> a[k][i];
    110 				for(int j = 0; j < n; ++j)
    111 			    a[k][i][j] -= '0';
    112 		}
    113 	
    114 	vector <int> v;
    115 	for(int k = 0; k < 4; ++k){
    116 		int sum = 0;
    117 		for(int i = 0; i < n; ++i)
    118 			for(int j = 0; j < n; ++j)
    119 				if((i + j) % 2 != a[k][i][j])
    120 					++sum;
    121 		v.push_back(sum);
    122 	}
    123 	
    124 	int res = int(1e9);
    125 	vector <int> perm;
    126 	for(int k = 0; k < 4; ++k) perm.push_back(k);
    127 	do{
    128 		int sum = 0;
    129 		for(int k = 0; k < 4; ++k){
    130 			int id = perm[k];
    131 			if(k & 1)
    132 				sum += v[id];
    133 			else
    134 				sum += n * n - v[id];
    135 		}
    136 		
    137 		res = min(res, sum);
    138 	}while(next_permutation(perm.begin(), perm.end()));
    139 
    140 	cout << res << endl;
    141 }
    142 ```
    143 
    144 [961D - Pair Of Lines](/contest/961/problem/D "Educational Codeforces Round 41 (Rated for Div. 2)")
    145 
    146 **Editorial**
    147 
    148 Tutorial is loading...
    149 
    150 **Solution (adedalic)**
    151 
    152 ```
    153 #include <bits/stdc++.h>
    154 
    155 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    156 
    157 #define all(a) (a).begin(), (a).end()
    158 #define sz(a) int(a.size())
    159 #define mp make_pair
    160 
    161 #define x first
    162 #define y second
    163 
    164 using namespace std;
    165 
    166 typedef long long li;
    167 typedef pair<int, int> pt;
    168 
    169 inline pt operator -(const pt &a, const pt &b) {
    170 	return {a.x - b.x, a.y - b.y};
    171 }
    172 
    173 inline li cross(const pt &a, const pt &b) {
    174 	return a.x * 1ll * b.y - a.y * 1ll * b.x;
    175 }
    176 
    177 const int N = 200 * 1000 + 555;
    178 
    179 int n;
    180 pt p[N];
    181 
    182 inline bool read() {
    183 	if(!(cin >> n))
    184 		return false;
    185 	
    186 	fore(i, 0, n)
    187 		scanf("%d%d", &p[i].x, &p[i].y);
    188 	return true;
    189 }
    190 
    191 bool used[N];
    192 
    193 bool check() {
    194 	int i1 = -1, i2 = -1;
    195 	fore(i, 0, n) {
    196 		if(used[i])
    197 			continue;
    198 		if(i1 == -1)
    199 			i1 = i;
    200 		else if(i2 == -1)
    201 			i2 = i;
    202 	}
    203 	if(i2 == -1)
    204 		return true;
    205 		
    206 	fore(i, 0, n) {
    207 		if(used[i])
    208 			continue;
    209 		if(cross(p[i2] - p[i1], p[i] - p[i1]) != 0)
    210 			return false;
    211 	}
    212 	return true;
    213 }
    214 
    215 bool check2(pt a, pt b) {
    216 	memset(used, 0, sizeof used);
    217 	fore(i, 0, n)
    218 		if(cross(b - a, p[i] - a) == 0)
    219 			used[i] = 1;
    220 	return check();
    221 }
    222 
    223 inline void solve() {
    224 	if(n <= 2) {
    225 		puts("YES");
    226 		return;
    227 	}
    228 	
    229 	if(check2(p[0], p[1]) || check2(p[0], p[2]) || check2(p[1], p[2]))
    230 		puts("YES");
    231 	else
    232 		puts("NO");
    233 }
    234 
    235 int main(){
    236 	if(read()) {
    237 		solve();
    238 	}
    239 	return 0;
    240 }
    241 ```
    242 
    243 [961E - Tufurama](/contest/961/problem/E "Educational Codeforces Round 41 (Rated for Div. 2)")
    244 
    245 **Editorial**
    246 
    247 Tutorial is loading...
    248 
    249 **Solution (Ajosteen)**
    250 
    251 ```
    252 #include <bits/stdc++.h>
    253 
    254 using namespace std;
    255 
    256 const int N = 200 * 1000 + 9;
    257 
    258 int n;
    259 int a[N];
    260 int f[N];
    261 vector <int> v[N];
    262 
    263 void upd(int pos, int d){
    264 	for(; pos < N; pos |= pos + 1)
    265 		f[pos] += d;
    266 }
    267 
    268 int get(int pos){
    269 	int res = 0;
    270 	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
    271 		res += f[pos];
    272 	return res;
    273 }
    274 
    275 int main() {
    276 	scanf("%d", &n);
    277 	for(int i = 0; i < n; ++i){
    278 		scanf("%d", a + i);
    279 		--a[i];
    280 	}
    281 		
    282 	for(int i = 0; i < n; ++i){
    283 		if(a[i] < N)
    284 			v[a[i]].push_back(i);
    285 		upd(i, 1);
    286 	}
    287 	
    288 	long long res = 0;
    289 	for(int i = 0; i < n; ++i){
    290 		int to = min(N - 1, a[i]);
    291 		res += get(to);
    292 		for(auto x : v[i])
    293 			upd(x, -1);
    294 	}
    295 	
    296 	for(int i = 0; i < n; ++i)
    297 	    if(i <= a[i])
    298 	        --res;
    299     assert(res % 2 == 0);
    300     
    301 	cout << res / 2 << endl;
    302 }
    303 ```
    304 
    305 [961F - k-substrings](/contest/961/problem/F "Educational Codeforces Round 41 (Rated for Div. 2)")
    306 
    307 **Editorial**
    308 
    309 Tutorial is loading...
    310 
    311 **Alternative solution (jtnydv25)**
    312 
    313 Comment
    314 
    315 **Solution (adedalic, suffix array)**
    316 
    317 ```
    318 #include <bits/stdc++.h>
    319 
    320 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    321 
    322 #define all(a) (a).begin(), (a).end()
    323 #define sz(a) int(a.size())
    324 #define mp make_pair
    325 
    326 #define x first
    327 #define y second
    328 
    329 using namespace std;
    330 
    331 typedef pair<int, int> pt;
    332 
    333 const int LOGN = 21;
    334 const int N = 1000 * 1000 + 555;
    335 
    336 int n;
    337 string s;
    338 
    339 inline bool read() {
    340 	if(!(cin >> n))
    341 		return false;
    342 	
    343 	char buf[N];
    344 	assert(scanf("%s", buf) == 1);
    345 	s = buf;
    346 	return true;
    347 }
    348 
    349 pair<pt, int> d[N], curP[N];
    350 int szd = 0;
    351 
    352 int cnt[N], szcnt;
    353 int rdp[N];
    354 
    355 inline void radix_sort() {
    356 	fore(k, 0, 2) {
    357 		szcnt = 0;
    358 		fore(i, 0, szd) {
    359 			int val = k == 0 ? d[i].x.y : d[i].x.x;
    360 			while(szcnt <= val)
    361 				cnt[szcnt++] = 0;
    362 			cnt[val]++;
    363 		}
    364 		int sum = 0;
    365 		fore(i, 0, szcnt) {
    366 			rdp[i] = sum;
    367 			sum += cnt[i];
    368 		}
    369 		
    370 		fore(i, 0, szd) {
    371 			int val = k == 0 ? d[i].x.y : d[i].x.x;
    372 			curP[rdp[val]++] = d[i];
    373 		}
    374 		fore(i, 0, szd)
    375 			d[i] = curP[i];
    376 	}
    377 }
    378 
    379 int c[N], id[N];
    380 int lcp[N];
    381 
    382 int lg[N];
    383 int st[LOGN][N];
    384 
    385 void precalc() {
    386 	s += '$';
    387 	for(int len = 1; len < 2 * sz(s); len <<= 1) {
    388 		szd = 0;
    389 		fore(i, 0, sz(s)) {
    390 			int sh = len >> 1;
    391 			d[szd++] = {len == 1 ? mp((int)s[i], 0) : mp(c[i], c[(i + sh) % sz(s)]), i};
    392 		}
    393 		radix_sort();
    394 		
    395 		c[d[0].y] = 0;
    396 		fore(i, 1, szd)
    397 			c[d[i].y] = c[d[i - 1].y] + (d[i - 1].x != d[i].x);
    398 		
    399 		if(c[d[szd - 1].y] == sz(s) - 1)
    400 			break;
    401 	}
    402 	
    403 	fore(i, 0, sz(s)) {
    404 		c[i]--;
    405 		if(c[i] >= 0) id[c[i]] = i;
    406 	}
    407 	s.pop_back();
    408 	
    409 	int l = 0;
    410 	fore(i1, 0, n) {
    411 		l = max(l - 1, 0);
    412 		if(c[i1] == n - 1)
    413 			continue;
    414 		
    415 		int i2 = id[c[i1] + 1];
    416 		while(i1 + l < n && i2 + l < n && s[i1 + l] == s[i2 + l])
    417 			l++;
    418 		lcp[c[i1]] = l;
    419 	}
    420 	
    421 	lg[0] = 0;
    422 	fore(i, 1, N) {
    423 		lg[i] = lg[i - 1];
    424 		if((1 << (lg[i] + 1)) <= i)
    425 			lg[i]++;
    426 	}
    427 	
    428 	fore(pw, 0, LOGN) {
    429 		if(pw == 0) {
    430 			fore(i, 0, n)
    431 				st[pw][i] = lcp[i];
    432 			continue;
    433 		}
    434 		fore(i, 0, n) {
    435 			st[pw][i] = st[pw - 1][i];
    436 			if(i + (1 << (pw - 1)) < n)
    437 				st[pw][i] = min(st[pw][i], st[pw - 1][i + (1 << (pw - 1))]);
    438 		}
    439 	}
    440 }
    441 
    442 inline int getMin(int l, int r) {
    443 	if(l >= r) swap(l, r);
    444 	
    445 	int len = lg[r - l];
    446 	return min(st[len][l], st[len][r - (1 << len)]);
    447 }
    448 
    449 inline bool eq(int i1, int i2, int l) {
    450 	if(i1 == i2) return true;
    451 	return getMin(c[i1], c[i2]) >= l;
    452 }
    453 
    454 int l[N], mx[N];
    455 
    456 inline void solve() {
    457 	precalc();
    458 	
    459 	fore(i, 0, n / 2) {
    460 		int c1 = i, c2 = n - 1 - i;
    461 		if(s[c1] != s[c2]) {
    462 			l[i] = -1;
    463 			continue;
    464 		}
    465 		int lf = 0, rg = min(c1, n - 1 - c2) + 1;
    466 		while(rg - lf > 1) {
    467 			int mid = (lf + rg) >> 1;
    468 			
    469 			if(eq(c1 - mid, c2 - mid, 2 * mid + 1))
    470 				lf = mid;
    471 			else
    472 				rg = mid;
    473 		}
    474 		l[i] = lf;
    475 	}
    476 	
    477 	fore(i, 0, n / 2) {
    478 		if(l[i] < 0)
    479 			continue;
    480 		mx[i - l[i]] = max(mx[i - l[i]], 2 * l[i] + 1);
    481 	}
    482 	fore(i, 1, n / 2)
    483 		mx[i] = max(mx[i], mx[i - 1] - 2);
    484 
    485 	fore(i, 0, (n + 1) / 2) {
    486 		if(i) printf(" ");
    487 		printf("%d", mx[i] == 0 ? -1 : mx[i]);
    488 	}
    489 	puts("");
    490 }
    491 
    492 int main(){
    493 	if(read()) {
    494 		solve();
    495 	}
    496 	return 0;
    497 }
    498 ```
    499 
    500 **Solution (adedalic, hashes)**
    501 
    502 ```
    503 #include <bits/stdc++.h>
    504 
    505 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    506 
    507 #define all(a) (a).begin(), (a).end()
    508 #define sz(a) int(a.size())
    509 #define mp make_pair
    510 
    511 #define x first
    512 #define y second
    513 
    514 using namespace std;
    515 
    516 typedef long long li;
    517 
    518 const li MOD = li(1e18) + 3;
    519 const li BASE = 1009;
    520 
    521 inline li norm(li a) {
    522 	while(a >= MOD)
    523 		a -= MOD;
    524 	while(a < 0)
    525 		a += MOD;
    526 	return a;
    527 }
    528 
    529 inline li mul(li a, li b) {
    530 	li m = ((long double)(a) * b) / MOD;
    531 	return norm(a * b - m * MOD);
    532 }
    533 
    534 const int N = 1000 * 1000 + 555;
    535 
    536 int n;
    537 string s;
    538 
    539 inline bool read() {
    540 	if(!(cin >> n))
    541 		return false;
    542 	
    543 	char buf[N];
    544 	assert(scanf("%s", buf) == 1);
    545 	s = buf;
    546 	return true;
    547 }
    548 
    549 li h[N], pw[N];
    550 
    551 inline void precalc() {
    552 	h[0] = 0;
    553 	fore(i, 0, n)
    554 		h[i + 1] = norm(mul(h[i], BASE) + s[i] - 'a' + 1);
    555 		
    556 	pw[0] = 1;
    557 	fore(i, 1, N)
    558 		pw[i] = mul(pw[i - 1], BASE);
    559 }
    560 
    561 inline li getHash(int l, int r) {
    562 	return norm(h[r] - mul(h[l], pw[r - l]));
    563 }
    564 
    565 inline bool eq(int i1, int i2, int l) {
    566 	if(i1 == i2) return true;
    567 	return getHash(i1, i1 + l) == getHash(i2, i2 + l);
    568 }
    569 
    570 int l[N], mx[N];
    571 
    572 inline void solve() {
    573 	precalc();
    574 	
    575 	fore(i, 0, n / 2) {
    576 		int c1 = i, c2 = n - 1 - i;
    577 		if(s[c1] != s[c2]) {
    578 			l[i] = -1;
    579 			continue;
    580 		}
    581 		int lf = 0, rg = min(c1, n - 1 - c2) + 1;
    582 		while(rg - lf > 1) {
    583 			int mid = (lf + rg) >> 1;
    584 			
    585 			if(eq(c1 - mid, c2 - mid, 2 * mid + 1))
    586 				lf = mid;
    587 			else
    588 				rg = mid;
    589 		}
    590 		l[i] = lf;
    591 	}
    592 	
    593 	fore(i, 0, n / 2) {
    594 		if(l[i] < 0)
    595 			continue;
    596 		mx[i - l[i]] = max(mx[i - l[i]], 2 * l[i] + 1);
    597 	}
    598 	fore(i, 1, n / 2)
    599 		mx[i] = max(mx[i], mx[i - 1] - 2);
    600 
    601 	fore(i, 0, (n + 1) / 2) {
    602 		if(i) printf(" ");
    603 		if(mx[i] == 0) mx[i] = -1;
    604 		printf("%d", mx[i]);
    605 	}
    606 	puts("");
    607 }
    608 
    609 int main(){
    610 	if(read()) {
    611 		solve();
    612 	}
    613 	return 0;
    614 }
    615 ```
    616 
    617 [961G - Partitions](/contest/961/problem/G "Educational Codeforces Round 41 (Rated for Div. 2)")
    618 
    619 **Editorial**
    620 
    621 Tutorial is loading...
    622 
    623 **Solution (adedalic)**
    624 
    625 ```
    626 #include <bits/stdc++.h>
    627 
    628 using namespace std;
    629 
    630 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    631 #define forn(i, n) fore(i, 0, n)
    632 
    633 const int MOD = int(1e9) + 7;
    634 
    635 inline int norm(int a) {
    636 	while(a >= MOD)
    637 		a -= MOD;
    638 	while(a < 0)
    639 		a += MOD;
    640 	return a;
    641 }
    642 
    643 inline int mul(int a, int b) {
    644 	return int((a * 1ll * b) % MOD);
    645 }
    646 
    647 inline int binPow(int a, int k) {
    648 	int ans = 1;
    649 	while(k > 0) {
    650 		if(k & 1) ans = mul(ans, a);
    651 		a = mul(a, a);
    652 		k >>= 1;
    653 	}
    654 	return ans;
    655 }
    656 
    657 const int N = 200 * 1000 + 555;
    658 
    659 int f[N], inf[N];
    660 
    661 void precalc() {
    662 	f[0] = inf[0] = 1;
    663 	fore(i, 1, N) {
    664 		f[i] = mul(f[i - 1], i);
    665 		inf[i] = mul(inf[i - 1], binPow(i, MOD - 2));
    666 	}
    667 }
    668 
    669 int n, k, w[N];
    670 
    671 inline bool read() {
    672 	if(!(cin >> n >> k))
    673 		return false;
    674 	forn(i, n)
    675 		cin >> w[i];
    676 	return true;
    677 }
    678 
    679 inline int c(int n, int k) {
    680 	if(k > n || n < 0) return 0;
    681 	if(k == 0 || n == k) return 1;
    682 	
    683 	return mul(f[n], mul(inf[n - k], inf[k]));
    684 }
    685 
    686 inline int s(int n, int k) {
    687 	if(n == 0) return k == 0;
    688 	if(k == 0) return n == 0;
    689 	
    690 	int ans = 0, sg[2] = {1, MOD - 1};
    691 	forn(cnt, k)
    692 		ans = norm(ans + mul(sg[cnt & 1], mul(c(k, cnt), binPow(k - cnt, n))));
    693 	return mul(ans, inf[k]);
    694 }
    695 
    696 inline void solve() {
    697 	int sum = 0;
    698 	forn(i, n)
    699 		sum = norm(sum + w[i]);
    700 		
    701 	int s0 = s(n, k);
    702 	int s1 = mul(n - 1, s(n - 1, k));
    703 	
    704 	cout << mul(sum, norm(s0 + s1)) << endl;
    705 }
    706 
    707 int main() {
    708 #ifdef _DEBUG
    709 	freopen("input.txt", "r", stdin);
    710 #endif
    711 	precalc();
    712 	
    713 	assert(read());
    714 	solve();
    715 
    716 #ifdef _DEBUG
    717 	cerr << "TIME = " << clock() << endl;
    718 #endif
    719 	return 0;
    720 }
    721 ```