Codeforces Round #527 (Div. 3) Editorial

Revision en2, by vovuh, 2018-12-19 21:12:14

1092A - Uniform String

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		int n, k;
		cin >> n >> k;
		for (int j = 0; j < n; ++j) {
			cout << char('a' + j % k);
		}
		cout << endl;
	}
	
	return 0;
}

1092B - Teams Forming

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	sort(a.begin(), a.end());
	int res = 0;
	for (int i = 0; i < n; i += 2) {
		res += a[i + 1] - a[i];
	}
	
	cout << res << endl;
	
	return 0;
}

1092C - Prefixes and Suffixes

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int n;
vector<string> v;

string res;

bool check(const string &pref, const string &suf) {
	string s = pref + suf.substr(n - 2);
	multiset<string> vv, sPref, sSuf;
	for (int i = 0; i < n - 1; ++i) {
		sPref.insert(s.substr(0, n - i - 1));
		vv.insert(s.substr(0, n - i - 1));
		sSuf.insert(s.substr(i + 1));
		vv.insert(s.substr(i + 1));
	}
	if (vv == multiset<string>(v.begin(), v.end())) {
		for (int i = 0; i < 2 * n - 2; ++i) {
			if (sPref.count(v[i])) {
				res += 'P';
				sPref.erase(sPref.find(v[i]));
			} else if (sSuf.count(v[i])) {
				res += 'S';
				sSuf.erase(sSuf.find(v[i]));
			} else {
				assert(false);
			}
		}
		return true;
	}
	return false;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n;
	v = vector<string>(2 * n - 2);
	vector<string> big;
	for (int i = 0; i < 2 * n - 2; ++i) {
		cin >> v[i];
		if (int(v[i].size()) == n - 1) {
			big.push_back(v[i]);
		}
	}
	
	if (check(big[0], big[1])) {
		cout << res << endl;
	} else {
		check(big[1], big[0]);
		cout << res << endl;
	}
	
	return 0;
}

1092D1 - Great Vova Wall (Version 1)

Tutorial
Tutorial is loading...
Solution 1
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n){
		scanf("%d", &a[i]);
		a[i] &= 1;
	}
	
	vector<int> st;
	forn(i, n){
		if (!st.empty() && a[i] == st.back())
			st.pop_back();
		else
			st.push_back(a[i]);
	}
	
	puts(st.size() <= 1 ? "YES" : "NO");
	return 0;
}
Solution 2
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n){
		scanf("%d", &a[i]);
		a[i] &= 1;
	}
	
	set<pair<int, int>> seg, even;
	forn(i, n){
		int j = i;
		while (j + 1 < n && a[j + 1] == a[i]) ++j;
		seg.insert({i, j});
		if ((j - i + 1) % 2 == 0)
			even.insert({i, j});
		i = j;
	}
	
	while (seg.size() > 1 && !even.empty()){
		auto cur = *even.begin();
		even.erase(cur);
		seg.erase(cur);
		auto it = seg.lower_bound(cur);
		if (it != seg.end()){
			cur.second = it->second;
			if ((it->second - it->first + 1) % 2 == 0)
				even.erase(*it);
			seg.erase(it);
		}
		it = seg.lower_bound(cur);
		if (it != seg.begin()){
			--it;
			cur.first = it->first;
			if ((it->second - it->first + 1) % 2 == 0)
				even.erase(*it);
			seg.erase(it);
		}
		seg.insert(cur);
		if ((cur.second - cur.first + 1) % 2 == 0)
			even.insert(cur);
	}
	
	puts(seg.size() == 1 ? "YES" : "NO");
	return 0;
}

1092D2 - Great Vova Wall (Version 2)

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 1000 * 1000 + 13;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d", &a[i]);
	vector<int> st;
	
	int mx = *max_element(a, a + n);
	
	forn(i, n){
		if (a[i] == mx) continue;
		
		int j = i - 1;
		while (j + 1 < n && a[j + 1] != mx){
			++j;
			if (!st.empty() && st.back() == a[j]){
				st.pop_back();
			}
			else if (st.empty() || st.back() > a[j]){
				st.push_back(a[j]);
			}
			else{
				puts("NO");
				return 0;
			}
		}
		
		if (!st.empty()){
			puts("NO");
			return 0;
		}
		
		i = j;
	}
	
	puts("YES");
	return 0;
}

1092E - Minimal Diameter Forest

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;
const int INF = 1000000000;

int n, m;
vector<int> g[N];

int bfs(int x, int dist[N]){
	queue<int> q;
	q.push(x);
	dist[x] = 0;
	int lst = -1;
	while (!q.empty()){
		int v = q.front();
		q.pop();
		lst = v;
		for (auto u : g[v]) if (dist[u] > dist[v] + 1){
			dist[u] = dist[v] + 1;
			q.push(u);
		}
	}
	return lst;
}

int distx[N], disty[N];
bool used[N];
vector<int> cur;

void dfs(int v){
	used[v] = true;
	cur.push_back(v);
	for (auto u : g[v]) if (!used[u])
		dfs(u);
}

int main() {
	scanf("%d%d", &n, &m);
	forn(i, m){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	forn(i, n) distx[i] = disty[i] = INF;
	
	vector<pair<int, int>> comps;
	forn(i, n) if (!used[i]){
		cur.clear();
		dfs(i);
		int x = bfs(i, distx);
		int y = bfs(x, disty);
		for (auto v : cur) distx[v] = INF;
		bfs(y, distx);
		int d = disty[y], center;
		for (auto v : cur) if (distx[v] == d / 2 && disty[v] == d - d / 2)
			center = v;
		comps.push_back({d, center});
	}
	
	vector<pair<int, int>> ans;
	nth_element(comp.begin(), comp.end() - 1, comp.end());
	forn(i, int(comps.size()) - 1){
		g[comps[i].second].push_back(comps.back().second);
		g[comps.back().second].push_back(comps[i].second);
		ans.push_back({comps[i].second, comps.back().second});
	}
	
	forn(i, n) distx[i] = disty[i] = INF;
	int y = bfs(bfs(comps.back().second, distx), disty);
	
	printf("%d\n", disty[y]);
	for (auto it : ans)
		printf("%d %d\n", it.first + 1, it.second + 1);
	return 0;
}

1092F - Tree with Maximum Cost

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

long long res, ans;

vector<int> a;
vector<long long> sum;
vector<vector<int>> g;

void dfs(int v, int p = -1, int h = 0) {
	res += h * 1ll * a[v];
	sum[v] = a[v];
	
	for (auto to : g[v]) {
		if (to == p) {
			continue;
		}
		dfs(to, v, h + 1);
		sum[v] += sum[to];
	}
}

void go(int v, int p = -1) {
	ans = max(ans, res);
	
	for (auto to : g[v]) {
		if (to == p) {
			continue;
		}
		
		res -= sum[to];
		sum[v] -= sum[to];
		res += sum[v];
		sum[to] += sum[v];
		
		go(to, v);
		
		sum[to] -= sum[v];
		res -= sum[v];
		sum[v] += sum[to];
		res += sum[to];
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	a = vector<int>(n);
	sum = vector<long long>(n);
	g = vector<vector<int>>(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs(0);
	go(0);
	
	cout << ans << endl;
	
	return 0;
}
Tags codeforces, 527, third division, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English vovuh 2018-12-19 21:12:14 33
ru3 Russian vovuh 2018-12-19 21:11:38 69
ru2 Russian vovuh 2018-12-19 20:18:13 2
en1 English vovuh 2018-12-19 20:17:55 8163 Initial revision for English translation
ru1 Russian vovuh 2018-12-19 20:17:08 8139 Первая редакция (опубликовано)