Codeforces Round #506 (Div. 3) Editorial

Revision en4, by vovuh, 2018-08-25 18:16:24

1029A - Many Equal Substrings

Tutorial
Tutorial is loading...
Solution (Vovuh, O(n^2))
#include <bits/stdc++.h>

using namespace std;

#define sz(a) int((a).size())

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	string t;
	cin >> n >> k >> t;
	
	int cnt = 1;
	int pos = 1;
	string ans = t;
	while (cnt < k) {
		if (pos >= sz(ans)) {
			ans += t;
			++cnt;
		} else {
			bool ok = true;
			int len = 0;
			for (int i = 0; i < sz(t); ++i) {
				if (pos + i >= sz(ans)) break;
				++len;
				if (ans[pos + i] != t[i]) ok = false;
			}
			if (ok) {
				ans += t.substr(len);
				++cnt;
			}
		}
		++pos;
	}
	
	cout << ans << endl;
	
	return 0;
}
Solution (Vovuh, префикс-функция)
#include <bits/stdc++.h>

using namespace std;

#define sz(a) int((a).size())

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	string t;
	cin >> n >> k >> t;
	
	vector<int> p(n);
	for (int i = 1; i < sz(t); ++i) {
		int j = p[i - 1];
		while (j > 0 && t[j] != t[i])
			j = p[j - 1];
		if (t[i] == t[j])
			++j;
		p[i] = j;
	}
	
	int len = sz(t) - p[n - 1];
	
	for (int i = 0; i < k - 1; ++i)
		cout << t.substr(0, len);
	cout << t << endl;
	
	return 0;
}

1029B - Creating the Contest

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

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif

	int n;
	scanf("%d", &n);
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
		
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int j = i;
		while (j + 1 < n && a[j + 1] <= a[j] * 2)
			++j;
		ans = max(ans, j - i + 1);
		i = j;
	}
	
	printf("%d\n", ans);
}

1029C - Maximal Intersection

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

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

using namespace std;

const int N = 300 * 1000 + 13;
const int INF = int(1e9);

int n;
int prl[N], prr[N], sul[N], sur[N];
int l[N], r[N];

int main() {
	scanf("%d", &n);
	forn(i, n)
		scanf("%d%d", &l[i], &r[i]);
	
	prl[0] = sul[n] = 0;
	prr[0] = sur[n] = INF;
	
	forn(i, n){
		prl[i + 1] = max(prl[i], l[i]);
		prr[i + 1] = min(prr[i], r[i]);
	}
	
	for (int i = n - 1; i >= 0; --i){
		sul[i] = max(sul[i + 1], l[i]);
		sur[i] = min(sur[i + 1], r[i]);
	}
	
	int ans = 0;
	forn(i, n)
		ans = max(ans, min(prr[i], sur[i + 1]) - max(prl[i], sul[i + 1]));
	printf("%d\n", ans);
	return 0;
}

1029D - Concatenated Multiples

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

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

typedef long long li;

using namespace std;

const int N = 200 * 1000 + 13;
const int LOGN = 11;

int n, k;
int a[N];
int len[N];
vector<int> rems[LOGN];
int pw[LOGN];

int main() {
	scanf("%d%d", &n, &k);
	forn(i, n) scanf("%d", &a[i]);
	
	pw[0] = 1;
	forn(i, LOGN - 1)
		pw[i + 1] = pw[i] * 10 % k;
	
	forn(i, n){
		int x = a[i];
		while (x > 0){
			++len[i];
			x /= 10;
		}
		rems[len[i]].push_back(a[i] % k);
	}
	
	forn(i, LOGN)
		sort(rems[i].begin(), rems[i].end());
	
	li ans = 0;
	forn(i, n){
		for (int j = 1; j < LOGN; ++j){
			int rem = (a[i] * li(pw[j])) % k;
			int xrem = (k - rem) % k;
			auto l = lower_bound(rems[j].begin(), rems[j].end(), xrem);
			auto r = upper_bound(rems[j].begin(), rems[j].end(), xrem);
			ans += (r - l);
			if (len[i] == j && (rem + a[i] % k) % k == 0)
				--ans;
		}
	}
	
	printf("%lld\n", ans);
	return 0;
}

1029E - Tree with Small Distances

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

using namespace std;

const int N = 200 * 1000 + 11;

int p[N];
int d[N];
vector<int> g[N];

void dfs(int v, int pr = -1, int dst = 0) {
	d[v] = dst;
	p[v] = pr;
	for (auto to : g[v]) {
		if (to != pr) {
			dfs(to, v, dst + 1);
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif

	int n;
	scanf("%d", &n);
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		scanf("%d %d", &x, &y);
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs(0);
	set<pair<int, int>> st;
	for (int i = 0; i < n; ++i) {
		if (d[i] > 2) {
			st.insert(make_pair(-d[i], i));
		}
	}
	
	int ans = 0;
	while (!st.empty()) {
		int v = st.begin()->second;
		v = p[v];
		++ans;
		auto it = st.find(make_pair(-d[v], v));
		if (it != st.end()) {
			st.erase(it);
		}
		for (auto to : g[v]) {
			auto it = st.find(make_pair(-d[to], to));
			if (it != st.end()) {
				st.erase(it);
			}
		}
	}
	
	printf("%d\n", ans);
}

1029F - Multicolored Markers

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

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

typedef long long li;

using namespace std;

const int N = 1000 * 1000;

int lens[N];
int k;

li solve(li a, li b){
	k = 0;
	for (li i = 1; i * i <= b; ++i)
		if (b % i == 0)
			lens[k++] = i;
	
	li ans = 2 * (a + b) + 2;
	li x = a + b;
	int l = 0;
	for (li i = 1; i * i <= x; ++i){
		if (x % i == 0){
			while (l + 1 < k && lens[l + 1] <= i)
				++l;
			if (b / lens[l] <= x / i)
				ans = min(ans, (i + x / i) * 2);
		}
	}
	
	return ans;
}

int main() {
	li a, b;
	scanf("%lld%lld", &a, &b);
	printf("%lld\n", min(solve(a, b), solve(b, a)));
	return 0;
}
Tags codeforces, 506, third division, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian vovuh 2018-08-25 18:17:13 0 (опубликовано)
en6 English vovuh 2018-08-25 18:17:06 0 (published)
en5 English vovuh 2018-08-25 18:16:46 28 Tiny change: 'n (Vovuh, префикс-функция)">\n\n~~~' -> 'n (Vovuh, prefix-function)">\n\n~~~'
en4 English vovuh 2018-08-25 18:16:24 6694
ru2 Russian vovuh 2018-08-25 18:15:49 6663 Мелкая правка: 'n\n~~~~~\n#include' -> 'n\n~~~~~\n\n#include'
ru1 Russian vovuh 2018-08-25 18:10:32 929 Первая редакция перевода на Русский (сохранено в черновиках)
en3 English vovuh 2018-08-25 18:09:09 191
en2 English vovuh 2018-08-25 18:07:12 193
en1 English vovuh 2018-08-25 18:06:04 948 Initial revision (saved to drafts)