Codeforces Round #506 (Div. 3) Editorial

Revision en5, by vovuh, 2018-08-25 18:16:46

1029A - Many Equal Substrings

Tutorial
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, prefix-function)
#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
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
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
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
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
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;
}

#### History

Revisions

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