codeforces-scrape

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

999.md (7375B)


      1 Source: https://codeforces.com/blog/entry/60138
      2 
      3 I'm really sorry for the issue with the problem D difficulty, it was much harder than i expected, and there was a big difficulty gap between problems C and D. I hope in the next rounds it will never happen again.
      4 
      5 **UPD**: I'd like to say a big thanks to [kevinsogo](/profile/kevinsogo "Grandmaster kevinsogo") for the great help with tutorials and the round preparation in general.
      6 
      7 [999A - Mishka and Contest](/contest/999/problem/A "Codeforces Round 490 (Div. 3)")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution (Vovuh)**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 
     18 using namespace std;
     19 
     20 int main() {
     21 #ifdef _DEBUG
     22 	freopen("input.txt", "r", stdin);
     23 //	freopen("output.txt", "w", stdout);
     24 #endif
     25 	
     26 	int n, k;
     27 	cin >> n >> k;
     28 	vector<int> a(n);
     29 	for (int i = 0; i < n; ++i)
     30 		cin >> a[i];
     31 	
     32 	int ans = 0;
     33 	while (!a.empty() && a.back() <= k) {
     34 		++ans;
     35 		a.pop_back();
     36 	}
     37 	reverse(a.begin(), a.end());
     38 	while (!a.empty() && a.back() <= k) {
     39 		++ans;
     40 		a.pop_back();
     41 	}
     42 	
     43 	cout << ans << endl;
     44 	
     45 	return 0;
     46 }
     47 ```
     48 
     49 [999B - Reversing Encryption](/contest/999/problem/B "Codeforces Round 490 (Div. 3)")
     50 
     51 **Tutorial**
     52 
     53 Tutorial is loading...
     54 
     55 **Solution (Vovuh)**
     56 
     57 ```
     58 #include <bits/stdc++.h>
     59 
     60 using namespace std;
     61 
     62 int main() {
     63 #ifdef _DEBUG
     64 	freopen("input.txt", "r", stdin);
     65 //	freopen("output.txt", "w", stdout);
     66 #endif
     67 	
     68 	int n;
     69 	string s;
     70 	cin >> n >> s;
     71 	for (int i = 1; i <= n; ++i) {
     72 		if (n % i == 0) {
     73 			reverse(s.begin(), s.begin() + i);
     74 		}
     75 	}
     76 	cout << s << endl;
     77 	
     78 	return 0;
     79 }
     80 ```
     81 
     82 [999C - Alphabetic Removals](/contest/999/problem/C "Codeforces Round 490 (Div. 3)")
     83 
     84 **Tutorial**
     85 
     86 Tutorial is loading...
     87 
     88 **Solution 1 (Vovuh)**
     89 
     90 ```
     91 #include <bits/stdc++.h>
     92 
     93 using namespace std;
     94 
     95 int main() {
     96 #ifdef _DEBUG
     97 	freopen("input.txt", "r", stdin);
     98 //	freopen("output.txt", "w", stdout);
     99 #endif
    100 	
    101 	int n, k;
    102 	cin >> n >> k;
    103 	string s;
    104 	cin >> s;
    105 	
    106 	vector<int> cnt(26);
    107 	for (auto c : s) ++cnt[c - 'a'];
    108 
    109 	int pos = 26;
    110 	for (int i = 0; i < 26; ++i) {
    111 		if (k >= cnt[i]) {
    112 			k -= cnt[i];
    113 		} else {
    114 			pos = i;
    115 			break;
    116 		}
    117 	}
    118 	
    119 	string ans;
    120 	int rem = k;
    121 	for (auto c : s) {
    122 		int cur = c - 'a';
    123 		if (cur > pos || (cur == pos && rem == 0)) {
    124 			ans += c;
    125 		} else if (cur == pos) {
    126 			--rem;
    127 		}
    128 	}
    129 	
    130 	cout << ans << endl;
    131 	
    132 	return 0;
    133 }
    134 ```
    135 
    136 **Solution 2 (Vovuh)**
    137 
    138 ```
    139 #include <bits/stdc++.h>
    140 
    141 using namespace std;
    142 
    143 int main() {
    144 #ifdef _DEBUG
    145 	freopen("input.txt", "r", stdin);
    146 //	freopen("output.txt", "w", stdout);
    147 #endif
    148 	
    149 	int n, k;
    150 	cin >> n >> k;
    151 	string s;
    152 	cin >> s;
    153 
    154 	vector<pair<char, int>> c(n);
    155 	for (int i = 0; i < n; ++i)
    156 		c[i] = make_pair(s[i], i);
    157 	sort(c.begin(), c.end());
    158 	sort(c.begin() + k, c.end(), [&] (const pair<char, int> &a, const pair<char, int> &b) {
    159 		return a.second < b.second;
    160 	});
    161 	
    162 	for (int i = k; i < n; ++i)
    163 		cout << c[i].first;
    164 	cout << endl;
    165 	
    166 	return 0;
    167 }
    168 ```
    169 
    170 [999D - Equalize the Remainders](/contest/999/problem/D "Codeforces Round 490 (Div. 3)")
    171 
    172 **Tutorial**
    173 
    174 Tutorial is loading...
    175 
    176 **Solution (Vovuh)**
    177 
    178 ```
    179 #include <bits/stdc++.h>
    180 
    181 using namespace std;
    182 
    183 int main() {
    184 #ifdef _DEBUG
    185 	freopen("input.txt", "r", stdin);
    186 //	freopen("output.txt", "w", stdout);
    187 #endif
    188 	
    189 	int n, m;
    190 	cin >> n >> m;
    191 	int k = n / m;
    192 	vector<int> a(n);
    193 	vector<vector<int>> val(m);
    194 	for (int i = 0; i < n; ++i) {
    195 		cin >> a[i];
    196 		val[a[i] % m].push_back(i);
    197 	}
    198 	
    199 	long long ans = 0;
    200 	vector<pair<int, int>> fre;
    201 	for (int i = 0; i < 2 * m; ++i) {
    202 		int cur = i % m;
    203 		while (int(val[cur].size()) > k) {
    204 			int elem = val[cur].back();
    205 			val[cur].pop_back();
    206 			fre.push_back(make_pair(elem, i));
    207 		}
    208 		while (int(val[cur].size()) < k && !fre.empty()) {
    209 			int elem = fre.back().first;
    210 			int mmod = fre.back().second;
    211 			fre.pop_back();
    212 			val[cur].push_back(elem);
    213 			a[elem] += i - mmod;
    214 			ans += i - mmod;
    215 		}
    216 	}
    217 	
    218 	cout << ans << endl;
    219 	for (int i = 0; i < n; ++i)
    220 		cout << a[i] << " ";
    221 	cout << endl;
    222 	
    223 	return 0;
    224 }
    225 ```
    226 
    227 [999E - Reachability from the Capital](/contest/999/problem/E "Codeforces Round 490 (Div. 3)")
    228 
    229 **Tutorial**
    230 
    231 Tutorial is loading...
    232 
    233 **Solution (Vovuh)**
    234 
    235 ```
    236 #include <bits/stdc++.h>
    237 
    238 using namespace std;
    239 
    240 const int N = 5010;
    241 
    242 int n, m, s;
    243 vector<int> g[N];
    244 bool used[N];
    245 bool ok[N];
    246 
    247 int cnt;
    248 
    249 void dfs1(int v) {
    250 	ok[v] = true;
    251 	for (auto to : g[v])
    252 		if (!ok[to])
    253 			dfs1(to);
    254 }
    255 
    256 void dfs2(int v) {
    257 	used[v] = true;
    258 	++cnt;
    259 	for (auto to : g[v])
    260 		if (!used[to] && !ok[to])
    261 			dfs2(to);
    262 }
    263 
    264 int main() {
    265 #ifdef _DEBUG
    266 	freopen("input.txt", "r", stdin);
    267 //	freopen("output.txt", "w", stdout);
    268 #endif
    269 	
    270 	cin >> n >> m >> s;
    271 	--s;
    272 	for (int i = 0; i < m; ++i) {
    273 		int x, y;
    274 		cin >> x >> y;
    275 		--x, --y;
    276 		g[x].push_back(y);
    277 	}
    278 	
    279 	dfs1(s);
    280 	
    281 	vector<pair<int, int>> val;
    282 	for (int i = 0; i < n; ++i) {
    283 		if (!ok[i]) {
    284 			cnt = 0;
    285 			memset(used, false, sizeof(used));
    286 			dfs2(i);
    287 			val.push_back(make_pair(cnt, i));
    288 		}
    289 	}
    290 	sort(val.begin(), val.end());
    291 	reverse(val.begin(), val.end());
    292 	
    293 	int ans = 0;
    294 	for (auto it : val) {
    295 		if (!ok[it.second]) {
    296 			++ans;
    297 			dfs1(it.second);
    298 		}
    299 	}
    300 	
    301 	cout << ans << endl;
    302 	
    303 	return 0;
    304 }
    305 ```
    306 
    307 **Linear Solution (Vovuh)**
    308 
    309 ```
    310 #include <bits/stdc++.h>
    311 
    312 using namespace std;
    313 
    314 const int N = 5010;
    315 
    316 int n, m, s;
    317 vector<int> g[N];
    318 vector<int> tg[N];
    319 vector<int> cg[N];
    320 vector<int> ord;
    321 int indeg[N];
    322 bool ucomp[N];
    323 bool used[N];
    324 int comp[N];
    325 int cnt;
    326 
    327 void dfs1(int v) {
    328 	used[v] = true;
    329 	for (auto to : g[v])
    330 		if (!used[to])
    331 			dfs1(to);
    332 	ord.push_back(v);
    333 }
    334 
    335 void dfs2(int v) {
    336 	comp[v] = cnt;
    337 	for (auto to : tg[v])
    338 		if (comp[to] == -1)
    339 			dfs2(to);
    340 }
    341 
    342 void dfs3(int v) {
    343 	ucomp[v] = true;
    344 	for (auto to : cg[v])
    345 		if (!ucomp[to])
    346 			dfs3(to);
    347 }
    348 
    349 int main() {
    350 #ifdef _DEBUG
    351 	freopen("input.txt", "r", stdin);
    352 //	freopen("output.txt", "w", stdout);
    353 #endif
    354 	
    355 	cin >> n >> m >> s;
    356 	--s;
    357 	for (int i = 0; i < m; ++i) {
    358 		int x, y;
    359 		cin >> x >> y;
    360 		--x, --y;
    361 		g[x].push_back(y);
    362 		tg[y].push_back(x);
    363 	}
    364 	
    365 	for (int i = 0; i < n; ++i) {
    366 		if (!used[i]) {
    367 			dfs1(i);
    368 		}
    369 	}
    370 	
    371 	reverse(ord.begin(), ord.end());
    372 	memset(comp, -1, sizeof(comp));
    373 	for (int i = 0; i < n; ++i) {
    374 		if (comp[ord[i]] == -1) {
    375 			dfs2(ord[i]);
    376 			++cnt;
    377 		}
    378 	}
    379 	
    380 	for (int v = 0; v < n; ++v) {
    381 		for (auto to : g[v]) {
    382 			if (comp[v] != comp[to]) {
    383 				cg[comp[v]].push_back(comp[to]);
    384 				++indeg[comp[to]];
    385 			}
    386 		}
    387 	}
    388 	
    389 	dfs3(comp[s]);
    390 	int ans = 0;
    391 	for (int i = 0; i < cnt; ++i)
    392 		if (!ucomp[i] && indeg[i] == 0)
    393 			++ans;
    394 			
    395 	cout << ans << endl;
    396 	
    397 	return 0;
    398 }
    399 ```
    400 
    401 [999F - Cards and Joy](/contest/999/problem/F "Codeforces Round 490 (Div. 3)")
    402 
    403 **Tutorial**
    404 
    405 Tutorial is loading...
    406 
    407 **Solution (Vovuh)**
    408 
    409 ```
    410 #include <bits/stdc++.h>
    411 
    412 using namespace std;
    413 
    414 const int N = 520;
    415 const int K = 12;
    416 const int C = 100 * 1000 + 11;
    417 
    418 int n, k;
    419 int c[C];
    420 int f[C];
    421 vector<int> h;
    422 
    423 int dp[N][K * N];
    424 
    425 int main() {
    426 #ifdef _DEBUG
    427 	freopen("input.txt", "r", stdin);
    428 //	freopen("output.txt", "w", stdout);
    429 #endif
    430 	
    431 	cin >> n >> k;
    432 	h = vector<int>(k + 1);
    433 	for (int i = 0; i < n * k; ++i) {
    434 		int x;
    435 		cin >> x;
    436 		++c[x];
    437 	}
    438 	for (int i = 0; i < n; ++i) {
    439 		int x;
    440 		cin >> x;
    441 		++f[x];
    442 	}
    443 	for (int i = 1; i <= k; ++i)
    444 		cin >> h[i];
    445 		
    446 	for (int i = 0; i < n; ++i) {
    447 		for (int j = 0; j <= n * k; ++j) {
    448 			for (int cur = 0; cur <= k; ++cur) {
    449 				dp[i + 1][j + cur] = max(dp[i + 1][j + cur], dp[i][j] + h[cur]);
    450 			}
    451 		}
    452 	}
    453 	
    454 	int ans = 0;
    455 	for (int i = 0; i < C; ++i) {
    456 		if (f[i] != 0) ans += dp[f[i]][c[i]];
    457 	}
    458 	
    459 	cout << ans << endl;
    460 	
    461 	return 0;
    462 }
    463 ```