Codeforces Round #612 (Div. 2)

#include <bits/stdc++.h>

const int N = 110, INF = 0x3f3f3f3f;
int dp[N][N / 2][2], p[N];

inline bool chkmin(int &a, int b) {
    return a > b ? a = b, 1 : 0;
}

inline bool chkmax(int &a, int b) {
    return a < b ? a = b, 1 : 0;
}

int main() {
    int n;
    scanf("%d", &n);
    const int cnt = (n + 1) / 2;
    for (int i = 1; i <= n; i++) 
        scanf("%d", p + i);
    memset(dp, 0x3f, sizeof(dp));
    if (p[1]) {
        int id = p[1] & 1;
        if (id) dp[1][cnt - 1][id] = 0;
        else dp[1][cnt][id] = 0;
    } else {
        dp[1][cnt - 1][1] = dp[1][cnt][0] = 0;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= cnt; j++) {
            if (!p[i]) {
                chkmin(dp[i][j][1], std::min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][0] + 1));
                chkmin(dp[i][j][0], std::min(dp[i - 1][j][1] + 1, dp[i - 1][j][0]));
            } else {
                if (p[i] & 1)
                    chkmin(dp[i][j][1], std::min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][0] + 1));
                else 
                    chkmin(dp[i][j][0], std::min(dp[i - 1][j][1] + 1, dp[i - 1][j][0]));
            }
        }
    }
    printf("%d\n", std::min(dp[n][0][0], dp[n][0][1]));
    return 0;
}

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second

const int N = 2e3 + 7;

std::vector<int> adj[N];
std::vector<std::pii> vec[N];
int n, c[N], root;
bool flag = 1;

void dfs(int u) {
    for (int i = 0, sz = adj[u].size(); i < sz; i++) {
        int v = adj[u][i];
        dfs(v);
        if (!flag) return;
        for (int j = 0; j < vec[v].size(); j++)
            vec[u].push_back(vec[v][j]);
        vec[v].clear();
    }
    if (c[u] > vec[u].size()) {
        flag = 0;
        return;
    }
    std::sort(vec[u].begin(), vec[u].end());
    for (int i = 0; i < vec[u].size(); i++)
        vec[u][i].fi = i + 1;
    vec[u].insert(vec[u].begin() + c[u], std::pii(c[u] + 1, u));
    for (int i = c[u] + 1; i < vec[u].size(); i++)
        vec[u][i].fi++;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int p;
        scanf("%d%d", &p, c + i);
        if (!p) root = i;
        else adj[p].push_back(i);
    }
    dfs(root);
    if (!flag) {
        puts("NO");
    } else {
        for (int i = 0; i < n; i++)
            std::swap(vec[root][i].fi, vec[root][i].se);
        std::sort(vec[root].begin(), vec[root].end());
        puts("YES");
        for (int i = 0; i < n; i++)
            printf("%d%c", vec[root][i].se, " \n"[i == n - 1]);
    }
    return 0;
}

#include <bits/stdc++.h>

void out(int l, int r) {
    std::cout << "? " << l << " " << r << std::endl;
    //std::cout.flush();
}

int cnt0[105], cnt1[105], dif[105];
char ans[105];

int main() {
    int n;
    std::cin >> n;
    if (n <= 3) {
        for (int i = 0; i < n; i++) {
            out(i + 1, i + 1);
            std::string temp;
            std::cin >> temp;
            ans[i] = temp[0];
        }
        std::cout << "! " << ans << std::endl;
        return 0;
    }
    out(1, n);
    for (int i = 0; i < n * (n + 1) / 2; i++) {
        std::string str;
        std::cin >> str;
        int len = str.length();
        for (int j = 0; j < len; j++)
            cnt0[len] += str[j] - ‘a‘;
    }
    out(1, n - 1);
    for (int i = 0; i < n * (n - 1) / 2; i++) {
        std::string str;
        std::cin >> str;
        int len = str.length();
        for (int j = 0; j < len; j++)
            cnt1[len] += str[j] - ‘a‘;
    }
    for (int i = 1; i <= n; i++) {
        dif[i] = cnt0[i] - cnt1[i];
        ans[n - i] = dif[i] - dif[i - 1] + ‘a‘;
    }
    std::cout << "! " << ans << std::endl;
    return 0;
}