Codeforces Round #418 (Div. 2) Editorial
Difference between en3 and en4, changed 3,158 character(s)
Greetings!↵

[contest:814] has just come to an end. This is my first round here, and hope you all enjoyed the contest! > <↵

Seems the statements still created a few issues :( Anyway hope you liked it, and the characters feature the _Monogatari_ anime series. Let me state again that the statements has little to do with the plot and you are _not_ spoiled for the series! ^ ^↵

So for the impatient, here are the detailed tutorials for problems A, B and C. More are being boiled in the teapot... Goo-doo goo-doo.↵

[tutorial:814A]↵

<spoiler summary="Solution 1">↵
~~~~~↵
#include <cstdio>↵
static const int MAXN = 102;↵

int n, k;↵
int a[MAXN], b[MAXN];↵

int main()↵
{↵
    scanf("%d%d", &n, &k);↵
    int last_zero = -1;↵
    for (int i = 0; i < n; ++i) {↵
        scanf("%d", &a[i]);↵
        if (a[i] == 0) last_zero = i;↵
    }↵
    for (int i = 0; i < k; ++i) scanf("%d", &b[i]);↵

    if (k > 1) {↵
        puts("Yes");↵
    } else {↵
        a[last_zero] = b[0];↵
        bool valid = false;↵
        for (int i = 1; i < n; ++i)↵
            if (a[i] <= a[i - 1]) { valid = true; break; }↵
        puts(valid ? "Yes" : "No");↵
    }↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Solution 2">↵
~~~~~↵
#include <cstdio>↵
#include <algorithm>↵
static const int MAXN = 102;↵

int n, k;↵
int a[MAXN], b[MAXN];↵
int p[MAXN], r[MAXN];↵

inline bool check()↵
{↵
    for (int i = 1; i < n; ++i) if (r[i] <= r[i - 1]) return true;↵
    return false;↵
}↵

int main()↵
{↵
    scanf("%d%d", &n, &k);↵
    int last_zero = -1;↵
    for (int i = 0; i < n; ++i) {↵
        scanf("%d", &a[i]);↵
        if (a[i] == 0) last_zero = i;↵
    }↵
    for (int i = 0; i < k; ++i) scanf("%d", &b[i]);↵

    bool valid = false;↵
    for (int i = 0; i < k; ++i) p[i] = i;↵
    do {↵
        for (int i = 0, ptr = 0; i < n; ++i) {↵
            r[i] = (a[i] == 0) ? b[p[ptr++]] : a[i];↵
        }↵
        if (check()) { valid = true; break; }↵
    } while (std::next_permutation(p, p + k));↵
    puts(valid ? "Yes" : "No");↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:814B]↵

<spoiler summary="Solution 1">↵
~~~~~↵
#include <cstdio>↵
#include <cstring>↵
static const int MAXN = 1e3 + 4;↵

int n;↵
int a[MAXN], b[MAXN];↵
int pa[2][MAXN], pb[2][MAXN];↵

inline void try_recover(int *a, int *p1, int *p2)↵
{↵
    int dup_ct = 0;↵
    int dup1 = -1, dup2 = -1, absent = -1;↵
    for (int i = 0; i < n; ++i)↵
        for (int j = i + 1; j < n; ++j)↵
            if (a[i] == a[j]) dup1 = i, dup2 = j;↵
    for (absent = 1; absent <= n; ++absent) {↵
        bool occurred = false;↵
        for (int i = 0; i < n; ++i) if (a[i] == absent) { occurred = true; break; }↵
        if (!occurred) break;↵
    }↵

    memcpy(p1, a, n * sizeof(int));↵
    memcpy(p2, a, n * sizeof(int));↵
    p1[dup1] = absent;↵
    p2[dup2] = absent;↵
}↵

int main()↵
{↵
    scanf("%d", &n);↵
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);↵
    for (int i = 0; i < n; ++i) scanf("%d", &b[i]);↵

    try_recover(a, pa[0], pa[1]);↵
    try_recover(b, pb[0], pb[1]);↵
    int *ans = NULL;↵
    if (memcmp(pa[0], pb[0], n * sizeof(int)) == 0 || memcmp(pa[0], pb[1], n * sizeof(int)) == 0)↵
        ans = pa[0];↵
    else ans = pa[1];↵

    for (int i = 0; i < n; ++i) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Solution 2 - Casework">↵
~~~~~↵
#include <cstdio>↵
#include <utility>↵
static const int MAXN = 1e3 + 4;↵

int n;↵
int a[MAXN], b[MAXN];↵

std::pair<int, int> get_duplication(int *a)↵
{↵
    static int occ[MAXN];↵
    for (int i = 1; i <= n; ++i) occ[i] = -1;↵
    for (int i = 0; i < n; ++i) {↵
        if (occ[a[i]] != -1) return std::make_pair(occ[a[i]], i);↵
        else occ[a[i]] = i;↵
    }↵
    return std::make_pair(-1, -1);↵
}↵

inline void fix_permutation(int pos)↵
{↵
    static bool occ[MAXN];↵
    for (int i = 1; i <= n; ++i) occ[i] = false;↵
    for (int i = 0; i < n; ++i) if (i != pos) occ[a[i]] = true;↵
    for (int i = 1; i <= n; ++i) if (!occ[i]) { a[pos] = i; return; }↵
}↵

int main()↵
{↵
    scanf("%d", &n);↵
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);↵
    for (int i = 0; i < n; ++i) scanf("%d", &b[i]);↵

    std::pair<int, int> dup_a, dup_b;↵
    dup_a = get_duplication(a);↵
    dup_b = get_duplication(b);↵

    if (dup_a == dup_b) {↵
        a[dup_a.first] = b[dup_b.first];↵
    } else if (dup_a.first == dup_b.first || dup_a.first == dup_b.second) {↵
        a[dup_a.second] = b[dup_a.second];↵
        fix_permutation(dup_a.first);↵
    } else if (dup_a.second == dup_b.first || dup_a.second == dup_b.second) {↵
        a[dup_a.first] = b[dup_a.first];↵
        fix_permutation(dup_a.second);↵
    } else {↵
        a[dup_a.first] = b[dup_a.first];↵
        a[dup_a.second] = b[dup_a.second];↵
    }↵

    for (int i = 0; i < n; ++i) printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:814C]↵

<spoiler summary="Solution">↵
~~~~~↵
#include <cstdio>↵
#include <algorithm>↵
static const int MAXN = 1502;↵
static const int ALPHABET = 26;↵

int n;↵
char s[MAXN];↵
int ans[ALPHABET][MAXN] = {{ 0 }};↵
int q, m_i;↵
char c_i;↵

int main()↵
{↵
    scanf("%d", &n); getchar();↵
    for (int i = 0; i < n; ++i) s[i] = getchar() &mdash; 'a';↵

    for (char c = 0; c < ALPHABET; ++c) {↵
        for (int i = 0; i < n; ++i) {↵
            int replace_ct = 0;↵
            for (int j = i; j < n; ++j) {↵
                if (s[j] != c) ++replace_ct;↵
                ans[c][replace_ct] = std::max(ans[c][replace_ct], j - i + 1);↵
            }↵
        }↵
        for (int i = 1; i < MAXN; ++i)↵
            ans[c][i] = std::max(ans[c][i], ans[c][i - 1]);↵
    }↵

    scanf("%d", &q);↵
    for (int i = 0; i < q; ++i) {↵
        scanf("%d %c", &m_i, &c_i);↵
        printf("%d\n", ans[c_i - 'a'][m_i]);↵
    }↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

Goo-doo goo-doo...↵

(Second half of the night falls, and coming back after a bunch of hours. Thanks for understanding :P)
[tutorial:814D]↵

<spoiler summary="Solution 1 - DP on trees">↵
~~~~~↵
#include <cstdio>↵
#include <cmath>↵
#include <algorithm>↵
#include <vector>↵
typedef long long int64;↵
static const int MAXN = 1004;↵
#ifndef M_PI↵
static const double M_PI = acos(-1.0);↵
#endif↵

int n;↵
int x[MAXN], y[MAXN], r[MAXN];↵
int par[MAXN];↵
std::vector<int> e[MAXN];↵

// Whether one of C[u] and C[v] is contained in another↵
inline bool circle_contains(int u, int v)↵
{↵
    return ((int64)(x[u] - x[v]) * (x[u] - x[v]) + (int64)(y[u] - y[v]) * (y[u] - y[v]) <= (int64)(r[u] - r[v]) * (r[u] - r[v]));↵
}↵

int64 f[MAXN][2][2];↵

void dfs_dp(int u)↵
{↵
    int64 g[2][2] = {{ 0 }};↵
    for (int v : e[u]) {↵
        dfs_dp(v);↵
        for (int i = 0; i <= 1; ++i)↵
            for (int j = 0; j <= 1; ++j)↵
                g[i][j] += f[v][i][j];↵
    }↵
    for (int i = 0; i <= 1; ++i)↵
        for (int j = 0; j <= 1; ++j) {↵
            f[u][i][j] = std::max(↵
                // (1) <u> is assigned to the first group↵
                g[i ^ 1][j] + (int64)r[u] * r[u] * (i == 0 ? +1 : -1),↵
                // (2) <u> is assigned to the second group↵
                g[i][j ^ 1] + (int64)r[u] * r[u] * (j == 0 ? +1 : -1)↵
            );↵
        }↵
}↵

int main()↵
{↵
    scanf("%d", &n);↵
    for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);↵

    for (int i = 0; i < n; ++i) {↵
        par[i] = -1;↵
        for (int j = 0; j < n; ++j)↵
            if (r[j] > r[i] && circle_contains(i, j)) {↵
                if (par[i] == -1 || r[par[i]] > r[j]) par[i] = j;↵
            }↵
        e[par[i]].push_back(i);↵
    }↵

    int64 ans = 0;↵
    for (int i = 0; i < n; ++i) if (par[i] == -1) {↵
        dfs_dp(i);↵
        ans += f[i][0][0];↵
    }↵
    printf("%.8lf\n", (double)ans * M_PI);↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Solution 2 - Greedy">↵
~~~~~↵
#include <cstdio>↵
#include <cmath>↵
#include <algorithm>↵
#include <vector>↵
typedef long long int64;↵
static const int MAXN = 1004;↵
#ifndef M_PI↵
static const double M_PI = acos(-1.0);↵
#endif↵

int n;↵
int x[MAXN], y[MAXN], r[MAXN];↵
int par[MAXN];↵
std::vector<int> e[MAXN];↵

bool level[MAXN];↵

// Whether one of C[u] and C[v] is contained in another↵
inline bool circle_contains(int u, int v)↵
{↵
    return ((int64)(x[u] - x[v]) * (x[u] - x[v]) + (int64)(y[u] - y[v]) * (y[u] - y[v]) <= (int64)(r[u] - r[v]) * (r[u] - r[v]));↵
}↵

void dfs_colour(int u, bool c)↵
{↵
    level[u] = c;↵
    for (int v : e[u]) dfs_colour(v, c ^ 1);↵
}↵

int main()↵
{↵
    scanf("%d", &n);↵
    for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);↵

    for (int i = 0; i < n; ++i) {↵
        par[i] = -1;↵
        for (int j = 0; j < n; ++j)↵
            if (r[j] > r[i] && circle_contains(i, j)) {↵
                if (par[i] == -1 || r[par[i]] > r[j]) par[i] = j;↵
            }↵
        e[par[i]].push_back(i);↵
    }↵

    for (int i = 0; i < n; ++i) if (par[i] == -1) dfs_colour(i, false);↵
    int64 ans = 0;↵
    for (int i = 0; i < n; ++i)↵
        ans += (int64)r[i] * r[i] * (par[i] == -1 || (level[i] == true) ? +1 : -1);↵
    printf("%.8lf\n", (double)ans * M_PI);↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

Goo-doo goo-doo...

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English cyand1317 2017-07-26 11:16:03 4 Tiny change: '[c1][c2], ways[c0 - ' -> '[c1][c2], (ll)ways[c0 - '
en5 English cyand1317 2017-06-08 10:15:57 7528 Post all tutorials
en4 English cyand1317 2017-06-08 07:50:18 3158
en3 English cyand1317 2017-06-07 20:42:56 107
en2 English cyand1317 2017-06-07 18:25:59 43 Fix code formatting, oops (
en1 English cyand1317 2017-06-07 18:12:42 5926 Initial revision (published)