codeforces-scrape

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

1335.md (8426B)


      1 Source: https://codeforces.com/blog/entry/75993
      2 
      3 [1335A - Candies and Two Sisters](/contest/1335/problem/A "Codeforces Round 634 (Div. 3)")
      4 
      5 Idea: [vovuh](/profile/vovuh "Master vovuh")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19 #ifdef _DEBUG
     20 	freopen("input.txt", "r", stdin);
     21 //	freopen("output.txt", "w", stdout);
     22 #endif
     23 	
     24 	int t;
     25 	cin >> t;
     26 	while (t--) {
     27 		int n;
     28 		cin >> n;
     29 		cout << (n - 1) / 2 << endl;
     30 	}
     31 	
     32 	return 0;
     33 }
     34 ```
     35 
     36 [1335B - Construct the String](/contest/1335/problem/B "Codeforces Round 634 (Div. 3)")
     37 
     38 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution**
     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 t;
     58 	cin >> t;
     59 	while (t--) {
     60 		int n, a, b;
     61 		cin >> n >> a >> b;
     62 		for (int i = 0; i < n; ++i) {
     63 			cout << char('a' + i % b);
     64 		}
     65 		cout << endl;
     66 	}
     67 	
     68 	return 0;
     69 }
     70 ```
     71 
     72 [1335C - Two Teams Composing](/contest/1335/problem/C "Codeforces Round 634 (Div. 3)")
     73 
     74 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     75 
     76 **Tutorial**
     77 
     78 Tutorial is loading...
     79 
     80 **Solution**
     81 
     82 ```
     83 #include <bits/stdc++.h>
     84 
     85 using namespace std;
     86 
     87 int main() {
     88 #ifdef _DEBUG
     89 	freopen("input.txt", "r", stdin);
     90 //	freopen("output.txt", "w", stdout);
     91 #endif
     92 	
     93 	int t;
     94 	cin >> t;
     95 	while (t--) {
     96 		int n;
     97 		cin >> n;
     98 		vector<int> cnt(n + 1);
     99 		for (int i = 0; i < n; ++i) {
    100 			int x;
    101 			cin >> x;
    102 			++cnt[x];
    103 		}
    104 		int mx = *max_element(cnt.begin(), cnt.end());
    105 		int diff = n + 1 - count(cnt.begin(), cnt.end(), 0);
    106 		cout << max(min(mx - 1, diff), min(mx, diff - 1)) << endl;
    107 	}
    108 	
    109 	return 0;
    110 }
    111 ```
    112 
    113 [1335D - Anti-Sudoku](/contest/1335/problem/D "Codeforces Round 634 (Div. 3)")
    114 
    115 Idea: [vovuh](/profile/vovuh "Master vovuh")
    116 
    117 **Tutorial**
    118 
    119 Tutorial is loading...
    120 
    121 **Solution**
    122 
    123 ```
    124 #include <bits/stdc++.h>
    125 
    126 using namespace std;
    127 
    128 int main() {
    129 #ifdef _DEBUG
    130 	freopen("input.txt", "r", stdin);
    131 //	freopen("output.txt", "w", stdout);
    132 #endif
    133 	
    134 	int t;
    135 	cin >> t;
    136 	while (t--) {
    137 		for (int i = 0; i < 9; ++i) {
    138 			string s;
    139 			cin >> s;
    140 			for (auto &c : s) if (c == '2') c = '1';
    141 			cout << s << endl;
    142 		}
    143 	}
    144 	
    145 	return 0;
    146 }
    147 ```
    148 
    149 [1335E1 - Three Blocks Palindrome (easy version)](/contest/1335/problem/E1 "Codeforces Round 634 (Div. 3)")
    150 
    151 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    152 
    153 **Tutorial**
    154 
    155 Tutorial is loading...
    156 
    157 **Solution**
    158 
    159 ```
    160 #include <bits/stdc++.h>
    161 
    162 using namespace std;
    163 
    164 #define sz(a) int((a).size())
    165 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    166 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
    167 
    168 int main() {
    169 #ifdef _DEBUG
    170 	freopen("input.txt", "r", stdin);
    171 //	freopen("output.txt", "w", stdout);
    172 #endif
    173 	
    174 	int t;
    175 	cin >> t;
    176 	while (t--) {
    177 		int n;
    178 		cin >> n;
    179 		vector<int> a(n);
    180 		for (auto &it : a) cin >> it;
    181 		vector<vector<int>> cnt(26, vector<int>(n + 1));
    182 		forn(i, n) {
    183 			forn(j, 26) cnt[j][i + 1] = cnt[j][i];
    184 			++cnt[a[i] - 1][i + 1];
    185 		}
    186 		int ans = 0;
    187 		forn(i, 26) ans = max(ans, cnt[i][n - 1]);
    188 		forn(l, n) fore(r, l, n) {
    189 			int cntin = 0, cntout = 0;
    190 			forn(el, 26) {
    191 				cntin = max(cntin, cnt[el][r + 1] - cnt[el][l]);
    192 				cntout = max(cntout, min(cnt[el][l], cnt[el][n] - cnt[el][r + 1]) * 2);
    193 			}
    194 			ans = max(ans, cntin + cntout);
    195 		}
    196 		cout << ans << endl;
    197 	}
    198 	
    199 	return 0;
    200 }
    201 ```
    202 
    203 [1335E2 - Three Blocks Palindrome (hard version)](/contest/1335/problem/E2 "Codeforces Round 634 (Div. 3)")
    204 
    205 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    206 
    207 **Tutorial**
    208 
    209 Tutorial is loading...
    210 
    211 **Solution**
    212 
    213 ```
    214 #include <bits/stdc++.h>
    215 
    216 using namespace std;
    217 
    218 #define sz(a) int((a).size())
    219 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    220 
    221 int main() {
    222 #ifdef _DEBUG
    223 	freopen("input.txt", "r", stdin);
    224 //	freopen("output.txt", "w", stdout);
    225 #endif
    226 	
    227 	int t;
    228 	cin >> t;
    229 	while (t--) {
    230 		int n;
    231 		cin >> n;
    232 		vector<int> a(n);
    233 		for (auto &it : a) cin >> it;
    234 		vector<vector<int>> cnt(200, vector<int>(n + 1));
    235 		vector<vector<int>> pos(200);
    236 		forn(i, n) {
    237 			forn(j, 200) cnt[j][i + 1] = cnt[j][i];
    238 			++cnt[a[i] - 1][i + 1];
    239 			pos[a[i] - 1].push_back(i);
    240 		}
    241 		int ans = 0;
    242 		forn(i, 200) {
    243 			ans = max(ans, sz(pos[i]));
    244 			forn(p, sz(pos[i]) / 2) {
    245 				int l = pos[i][p] + 1, r = pos[i][sz(pos[i]) - p - 1] - 1;
    246 				forn(el, 200) {
    247 					int sum = cnt[el][r + 1] - cnt[el][l];
    248 					ans = max(ans, (p + 1) * 2 + sum);
    249 				}
    250 			}
    251 		}
    252 		cout << ans << endl;
    253 	}
    254 	
    255 	return 0;
    256 }
    257 ```
    258 
    259 [1335F - Robots on a Grid](/contest/1335/problem/F "Codeforces Round 634 (Div. 3)")
    260 
    261 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    262 
    263 **Tutorial**
    264 
    265 Tutorial is loading...
    266 
    267 **Solution**
    268 
    269 ```
    270 #include <bits/stdc++.h>
    271 
    272 using namespace std;
    273 
    274 int n, m, lognm;
    275 vector<string> c, s;
    276 vector<vector<int>> used, nxt;
    277 
    278 void getnext(int x, int y, int &nx, int &ny) {
    279 	if (s[x][y] == 'U') nx = x - 1, ny = y;
    280 	if (s[x][y] == 'R') nx = x, ny = y + 1;
    281 	if (s[x][y] == 'D') nx = x + 1, ny = y;
    282 	if (s[x][y] == 'L') nx = x, ny = y - 1;
    283 }
    284 
    285 void dfs(int x, int y) {
    286 	used[x][y] = 1;
    287 	int nx = -1, ny = -1;
    288 	getnext(x, y, nx, ny);
    289 	assert(0 <= nx && nx < n && 0 <= ny && ny < m);
    290 	int v = x * m + y, to = nx * m + ny;
    291 	if (!used[nx][ny]) dfs(nx, ny);
    292 	nxt[v][0] = to;
    293 }
    294 
    295 int main() {
    296 #ifdef _DEBUG
    297 	freopen("input.txt", "r", stdin);
    298 //	freopen("output.txt", "w", stdout);
    299 #endif
    300 	
    301 	int t;
    302 	cin >> t;
    303 	while (t--) {
    304 		cin >> n >> m;
    305 		lognm = 0;
    306 		int nm = n * m;
    307 		while ((1 << lognm) <= nm) ++lognm;
    308 		c = s = vector<string>(n);
    309 		for (auto &it : c) cin >> it;
    310 		for (auto &it : s) cin >> it;
    311 		
    312 		used = vector<vector<int>>(n, vector<int>(m));
    313 		nxt = vector<vector<int>>(n * m, vector<int>(lognm));
    314 		for (int i = 0; i < n; ++i) {
    315 			for (int j = 0; j < m; ++j) {
    316 				if (!used[i][j]) dfs(i, j);
    317 			}
    318 		}
    319 		for (int deg = 1; deg < lognm; ++deg) {
    320 			for (int i = 0; i < n; ++i) {
    321 				for (int j = 0; j < m; ++j) {
    322 					int id = i * m + j;
    323 					nxt[id][deg] = nxt[nxt[id][deg - 1]][deg - 1];
    324 				}
    325 			}
    326 		}
    327 		
    328 		vector<vector<int>> black, white;
    329 		black = white = vector<vector<int>>(n, vector<int>(m));
    330 		for (int i = 0; i < n; ++i) {
    331 			for (int j = 0; j < m; ++j) {
    332 				int v = i * m + j, to = v;
    333 				for (int deg = lognm - 1; deg >= 0; --deg) {
    334 					if ((nm >> deg) & 1) to = nxt[to][deg];
    335 				}
    336 				if (c[i][j] == '0') ++black[to / m][to % m];
    337 				else ++white[to / m][to % m];
    338 			}
    339 		}
    340 		
    341 		int all = 0, good = 0;
    342 		for (int i = 0; i < n; ++i) {
    343 			for (int j = 0; j < m; ++j) {
    344 				if (black[i][j]) {
    345 					++all;
    346 					++good;
    347 				} else if (white[i][j]) {
    348 					++all;
    349 				}
    350 			}
    351 		}
    352 		cout << all << " " << good << endl;
    353 	}
    354 	
    355 	return 0;
    356 }
    357 ```
    358 
    359 **Solution (actually _overrated_, fastest O(nm log nm))**
    360 
    361 ```
    362 #include <iostream>
    363 #include <vector>
    364 #include <map>
    365 #include <set>
    366 #include <queue>
    367 #include <algorithm>
    368 #include <string>
    369 #include <cmath>
    370 #include <cstdio>
    371 #include <iomanip>
    372 #include <fstream>
    373 #include <cassert>
    374 #include <cstring>
    375 #include <unordered_set>
    376 #include <unordered_map>
    377 #include <numeric>
    378 #include <ctime>
    379 #include <bitset>
    380 #include <complex>
    381 #include <chrono>
    382 #include <random>
    383 #include <functional>
    384 
    385 using namespace std;
    386 
    387 const int N = 1e6 + 7;
    388 const int K = 24;
    389 
    390 int f[N];
    391 int dp[N];
    392 int ndp[N];
    393 int sel[N];
    394 
    395 int fans[N];
    396 int sans[N];
    397 
    398 void solve() {
    399 	int n, m;
    400 	cin >> n >> m;
    401 	for (int i = 0; i < n; i++) {
    402 		string s;
    403 		cin >> s;
    404 		for (int j = 0; j < m; j++) {
    405 			sel[i * m + j] = (s[j] == '0');
    406 		}
    407 	}
    408 	for (int i = 0; i < n; i++) {
    409 		string s;
    410 		cin >> s;
    411 		for (int j = 0; j < m; j++) {
    412 			int to = -1;
    413 			if (s[j] == 'U') to = (i - 1) * m + j;
    414 			if (s[j] == 'D') to = (i + 1) * m + j;
    415 			if (s[j] == 'L') to = i * m + (j - 1);
    416 			if (s[j] == 'R') to = i * m + (j + 1);
    417 			f[i * m + j] = to;
    418 		}
    419 	}
    420 	n *= m;
    421 	for (int i = 0; i < n; i++) {
    422 		dp[i] = f[i];
    423 	}
    424 	for (int j = 0; j < K; j++) {
    425 		for (int i = 0; i < n; i++) {
    426 			ndp[i] = dp[dp[i]];
    427 		}
    428 		for (int i = 0; i < n; i++) {
    429 			dp[i] = ndp[i];
    430 		}
    431 	}
    432 	fill(fans, fans + n, 0);
    433 	fill(sans, sans + n, 0);
    434 	for (int i = 0; i < n; i++) {
    435 		fans[dp[i]]++;
    436 		sans[dp[i]] += sel[i];
    437 	}
    438 	int fs = 0, ss = 0;
    439 	for (int i = 0; i < n; i++) {
    440 		fs += (fans[i] > 0);
    441 		ss += (sans[i] > 0);
    442 	}
    443 	cout << fs << ' ' << ss << '\n';
    444 }
    445 
    446 signed main() {
    447 	ios_base::sync_with_stdio(false);
    448 	cin.tie(0);
    449 
    450 	int q;
    451 	cin >> q;
    452 	while (q--) {
    453 		solve();
    454 	}
    455 }
    456 ```