codeforces-scrape

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

1144.md (7476B)


      1 Source: https://codeforces.com/blog/entry/66307
      2 
      3 [1144A - Diverse Strings](/contest/1144/problem/A "Codeforces Round 550 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      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 #define forn(i, n) for (int i = 0; i < int(n); i++)
     19 
     20 int main() {
     21     int n;
     22     cin >> n;
     23     forn(i, n) {
     24         string s;
     25         cin >> s;
     26         if (set<char>(s.begin(), s.end()).size() == s.length()
     27                 && *max_element(s.begin(), s.end()) == char(*min_element(s.begin(), s.end()) + (s.length() - 1)))
     28             cout << "Yes" << endl;
     29         else
     30             cout << "No" << endl;
     31     }
     32 }
     33 ```
     34 
     35 [1144B - Parity Alternated Deletions](/contest/1144/problem/B "Codeforces Round 550 (Div. 3)")
     36 
     37 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47 
     48 using namespace std;
     49 
     50 int main() {
     51 #ifdef _DEBUG
     52 	freopen("input.txt", "r", stdin);
     53 //	freopen("output.txt", "w", stdout);
     54 #endif
     55 	
     56 	int n;
     57 	cin >> n;
     58 	int sum = 0;
     59 	vector<int> even, odd;
     60 	for (int i = 0; i < n; ++i) {
     61 		int x;
     62 		cin >> x;
     63 		sum += x;
     64 		if (x & 1) odd.push_back(x);
     65 		else even.push_back(x);
     66 	}
     67 	
     68 	sort(odd.rbegin(), odd.rend());
     69 	sort(even.rbegin(), even.rend());
     70 	int k = min(odd.size(), even.size());
     71 	int rem = sum;
     72 	rem -= accumulate(odd.begin(), odd.begin() + k, 0);
     73 	rem -= accumulate(even.begin(), even.begin() + k, 0);
     74 	if (int(odd.size()) > k) {
     75 		rem -= odd[k];
     76 	}
     77 	if (int(even.size()) > k) {
     78 		rem -= even[k];
     79 	}
     80 	
     81 	cout << rem << endl;
     82 	
     83 	return 0;
     84 }
     85 ```
     86 
     87 [1144C - Two Shuffled Sequences](/contest/1144/problem/C "Codeforces Round 550 (Div. 3)")
     88 
     89 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     90 
     91 **Tutorial**
     92 
     93 Tutorial is loading...
     94 
     95 **Solution**
     96 
     97 ```
     98 #include <bits/stdc++.h>
     99 
    100 using namespace std;
    101 
    102 int main() {
    103 #ifdef _DEBUG
    104 	freopen("input.txt", "r", stdin);
    105 //	freopen("output.txt", "w", stdout);
    106 #endif
    107 	
    108 	int n;
    109 	cin >> n;
    110 	vector<int> cnt(200 * 1000 + 1);
    111 	for (int i = 0; i < n; ++i) {
    112 		int x;
    113 		cin >> x;
    114 		++cnt[x];
    115 		if (cnt[x] > 2) {
    116 			cout << "NO" << endl;
    117 			return 0;
    118 		}
    119 	}
    120 	
    121 	cout << "YES" << endl << count(cnt.begin(), cnt.end(), 2) << endl;
    122 	for (int i = 0; i <= 200 * 1000; ++i) {
    123 		if (cnt[i] == 2) {
    124 			cout << i << " ";
    125 			--cnt[i];
    126 		}
    127 	}
    128 	cout << endl << count(cnt.begin(), cnt.end(), 1) << endl;
    129 	for (int i = 200 * 1000; i >= 0; --i) {
    130 		if (cnt[i] == 1) {
    131 			cout << i << " ";
    132 			--cnt[i];
    133 		}
    134 	}
    135 	cout << endl;
    136 	
    137 	assert(count(cnt.begin(), cnt.end(), 0) == 200 * 1000 + 1);
    138 	
    139 	return 0;
    140 }
    141 ```
    142 
    143 [1144D - Equalize Them All](/contest/1144/problem/D "Codeforces Round 550 (Div. 3)")
    144 
    145 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
    146 
    147 **Tutorial**
    148 
    149 Tutorial is loading...
    150 
    151 **Solution**
    152 
    153 ```
    154 #include <bits/stdc++.h>
    155 
    156 using namespace std;
    157 
    158 int main() {
    159 #ifdef _DEBUG
    160 	freopen("input.txt", "r", stdin);
    161 //	freopen("output.txt", "w", stdout);
    162 #endif
    163 	
    164 	int n;
    165 	cin >> n;
    166 	
    167 	vector<int> a(n), cnt(200 * 1000 + 1);
    168 	for (int i = 0; i < n; ++i) {
    169 		cin >> a[i];
    170 		++cnt[a[i]];
    171 	}
    172 	
    173 	int val = max_element(cnt.begin(), cnt.end()) - cnt.begin();
    174 	int pos = find(a.begin(), a.end(), val) - a.begin();
    175 	
    176 	cout << n - cnt[val] << endl;
    177 	int siz = 0;
    178 	for (int i = pos - 1; i >= 0; --i) {
    179 		cout << 1 + (a[i] > a[i + 1]) << " " << i + 1 << " " << i + 2 << " " << endl;
    180 		a[i] = a[i + 1];
    181 		++siz;
    182 	}
    183 	for (int i = 0; i < n - 1; ++i) {
    184 		if (a[i + 1] != val) {
    185 			assert(a[i] == val);
    186 			cout << 1 + (a[i + 1] > a[i]) << " " << i + 2 << " " << i + 1 << " " << endl;
    187 			a[i + 1] = a[i];
    188 			++siz;
    189 		}
    190 	}
    191 	
    192 	assert(siz == n - cnt[val]);
    193 	return 0;
    194 }
    195 ```
    196 
    197 [1144E - Median String](/contest/1144/problem/E "Codeforces Round 550 (Div. 3)")
    198 
    199 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
    200 
    201 **Tutorial**
    202 
    203 Tutorial is loading...
    204 
    205 **Solution**
    206 
    207 ```
    208 #include <bits/stdc++.h>
    209 
    210 using namespace std;
    211 
    212 vector<int> get(const string &s) {
    213 	vector<int> res(s.size() + 1);
    214 	for (int i = 0; i < int(s.size()); ++i) {
    215 		res[i + 1] = s[i] - 'a';
    216 	}
    217 	return res;
    218 }
    219 
    220 int main() {
    221 #ifdef _DEBUG
    222 	freopen("input.txt", "r", stdin);
    223 //	freopen("output.txt", "w", stdout);
    224 #endif
    225 	
    226 	int k;
    227 	string s, t;
    228 	cin >> k >> s >> t;
    229 	vector<int> a = get(s), b = get(t);
    230 	
    231 	for (int i = k; i >= 0; --i) {
    232 		a[i] += b[i];
    233 		if (i) {
    234 			a[i - 1] += a[i] / 26;
    235 			a[i] %= 26;
    236 		}
    237 	}
    238 	
    239 	for (int i = 0; i <= k; ++i) {
    240 		int rem = a[i] % 2;
    241 		a[i] /= 2;
    242 		if (i + 1 <= k) {
    243 			a[i + 1] += rem * 26;
    244 		} else {
    245 			assert(rem == 0);
    246 		}
    247 	}
    248 	
    249 	for (int i = 1; i <= k; ++i) {
    250 		cout << char('a' + a[i]);
    251 	}
    252 	cout << endl;
    253 	
    254 	return 0;
    255 }
    256 ```
    257 
    258 [1144F - Graph Without Long Directed Paths](/contest/1144/problem/F "Codeforces Round 550 (Div. 3)")
    259 
    260 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    261 
    262 **Tutorial**
    263 
    264 Tutorial is loading...
    265 
    266 **Solution**
    267 
    268 ```
    269 #include <bits/stdc++.h>
    270 
    271 using namespace std;
    272 
    273 const int N = 200 * 1000 + 11;
    274 
    275 int n, m;
    276 vector<int> g[N];
    277 vector<pair<int, int>> e;
    278 
    279 bool bipartite;
    280 vector<int> color;
    281 
    282 void dfs(int v, int c) {
    283 	color[v] = c;
    284 	for (auto to : g[v]) {
    285 		if (color[to] == -1) {
    286 			dfs(to, c ^ 1);
    287 		} else {
    288 			if (color[to] == color[v]) {
    289 				bipartite = false;
    290 			}
    291 		}
    292 	}
    293 }
    294 
    295 int main() {
    296 #ifdef _DEBUG
    297 	freopen("input.txt", "r", stdin);
    298 //	freopen("output.txt", "w", stdout);
    299 #endif
    300 	
    301 	cin >> n >> m;
    302 	for (int i = 0; i < m; ++i) {
    303 		int x, y;
    304 		cin >> x >> y;
    305 		--x, --y;
    306 		g[x].push_back(y);
    307 		g[y].push_back(x);
    308 		e.push_back(make_pair(x, y));
    309 	}
    310 	
    311 	bipartite = true;
    312 	color = vector<int>(n, -1);
    313 	dfs(0, 0);
    314 	
    315 	if (!bipartite) {
    316 		cout << "NO" << endl;
    317 		return 0;
    318 	}
    319 	
    320 	cout << "YES" << endl;
    321 	for (int i = 0; i < m; ++i) {
    322 		cout << (color[e[i].first] < color[e[i].second]);
    323 	}
    324 	cout << endl;
    325 	
    326 	return 0;
    327 }
    328 ```
    329 
    330 [1144G - Two Merged Sequences](/contest/1144/problem/G "Codeforces Round 550 (Div. 3)")
    331 
    332 [There](//codeforces.com/blog/entry/66284?#comment-503140) is different solution for the problem, it is pretty interesting! Thanks, [Roundgod](/profile/Roundgod "Grandmaster Roundgod")!
    333 
    334 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
    335 
    336 **Tutorial**
    337 
    338 Tutorial is loading...
    339 
    340 **Solution**
    341 
    342 ```
    343 #include <bits/stdc++.h>
    344 
    345 using namespace std;
    346 
    347 const int INF = 1e9;
    348 
    349 int main() {
    350 #ifdef _DEBUG
    351 	freopen("input.txt", "r", stdin);
    352 //	freopen("output.txt", "w", stdout);
    353 #endif
    354 	
    355 	int n;
    356 	cin >> n;
    357 	vector<int> a(n);
    358 	for (int i = 0; i < n; ++i) {
    359 		cin >> a[i];
    360 	}
    361 	
    362 	vector<vector<int>> dp(n, vector<int>({-INF, INF}));
    363 	vector<vector<int>> p(n, vector<int>(2, -1));
    364 	dp[0][0] = INF;
    365 	dp[0][1] = -INF;
    366 	
    367 	for (int i = 1; i < n; ++i) {
    368 		{
    369 			if (a[i] > a[i - 1] && dp[i][0] < dp[i - 1][0]) {
    370 				dp[i][0] = dp[i - 1][0];
    371 				p[i][0] = 0;
    372 			}
    373 			if (a[i] < dp[i - 1][0] && dp[i][1] > a[i - 1]) {
    374 				dp[i][1] = a[i - 1];
    375 				p[i][1] = 0;
    376 			}
    377 		}
    378 		{
    379 			if (a[i] < a[i - 1] && dp[i][1] > dp[i - 1][1]) {
    380 				dp[i][1] = dp[i - 1][1];
    381 				p[i][1] = 1;
    382 			}
    383 			if (a[i] > dp[i - 1][1] && dp[i][0] < a[i - 1]) {
    384 				dp[i][0] = a[i - 1];
    385 				p[i][0] = 1;
    386 			}
    387 		}
    388 	}
    389 	
    390 	int pos = -1;
    391 	if (dp[n - 1][0] != -INF) {
    392 		pos = 0;
    393 	}
    394 	if (dp[n - 1][1] != INF) {
    395 		pos = 1;
    396 	}
    397 	
    398 	if (pos == -1) {
    399 		cout << "NO" << endl;
    400 		return 0;
    401 	}
    402 	
    403 	vector<int> inInc(n);
    404 	for (int i = n - 1; i >= 0; --i) {
    405 		if (pos == 0) {
    406 			inInc[i] = 1;
    407 		}
    408 		pos = p[i][pos];
    409 	}
    410 	
    411 	cout << "YES" << endl;
    412 	for (int i = 0; i < n; ++i) {
    413 		cout << !inInc[i] << " ";
    414 	}
    415 	cout << endl;
    416 	
    417 	return 0;
    418 }
    419 ```