A - Prefixo e Sufixo

A menor string concatenada é equivalente à maior sobreposição entre as duas strings. Para cada sufixo s' de s, verificamos o prefixo correspondente de t. Se forem iguais, atualizamos o comprimennto máximo da sobreposição. A resposta é 2 * n - max_overlap.

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    string s, t;
    cin >> n >> s >> t;

    int max_overlap = 0;
    for (int k = n; k >= 1; --k) {
        if (s.substr(n - k, k) == t.substr(0, k)) {
            max_overlap = k;
            break;
        }
    }
    cout << 2 * n - max_overlap;
    return 0;
}

B - Pirâmide da Mediana Fácil

Para que o valor x alcance o topo, ele deve estar na posição central inicial. Se colocarmos um número menor que x à esquerda e um maior à direita, a mediana da camada superior será x. Este padrão se propaga para cima. Existem casos de borda quando x é 1 ou 2n-1, onde é impossível.

#include <iostream>
#include <vector>
using namespace std;

void print_array(const vector<int>& arr, int n) {
    cout << "Yes\n";
    for (int i = 1; i < 2 * n; ++i) {
        cout << arr[i] << "\n";
    }
}

int main() {
    int n, x;
    cin >> n >> x;

    if (x == 1 || x == 2 * n - 1) {
        cout << "No";
        return 0;
    }

    vector<int> a(2 * n);
    for (int i = 1; i < 2 * n; ++i) {
        a[i] = i;
    }

    if (x == n) {
        print_array(a, n);
    } else if (x == n - 1) {
        swap(a[x], a[x + 1]);
        swap(a[x - 1], a[x + 2]);
        print_array(a, n);
    } else if (x == n + 1) {
        swap(a[x], a[x - 1]);
        swap(a[x + 1], a[x - 2]);
        print_array(a, n);
    } else {
        swap(a[x], a[n]);
        swap(a[x - 1], a[n + 1]);
        swap(a[x + 1], a[n - 1]);
        print_array(a, n);
    }
    return 0;
}

C - Exercício dos Coelhos

Cada operação troca os deltas entre posições adjacentes. Após k operações, podemos usar exponenciação por módulo de permutações para computar as posições finais. As coordenadas são reconstruídas a partir das diferenças.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> x(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> x[i];
    }

    int m;
    long long k;
    cin >> m >> k;
    vector<int> perm(n + 1);
    for (int i = 1; i <= n; ++i) {
        perm[i] = i;
    }

    for (int i = 0; i < m; ++i) {
        int a;
        cin >> a;
        swap(perm[a], perm[a + 1]);
    }

    vector<vector<int>> power(64, vector<int>(n + 1));
    for (int i = 1; i <= n; ++i) {
        power[0][i] = perm[i];
    }

    for (int bit = 1; bit < 64; ++bit) {
        for (int i = 1; i <= n; ++i) {
            power[bit][i] = power[bit - 1][power[bit - 1][i]];
        }
    }

    vector<long long> delta(n + 1);
    for (int i = n; i > 1; --i) {
        delta[i] = x[i] - x[i - 1];
    }

    vector<long long> result_delta(n + 1);
    for (int i = 1; i <= n; ++i) {
        int pos = i;
        for (int bit = 63; bit >= 0; --bit) {
            if ((k >> bit) & 1) {
                pos = power[bit][pos];
            }
        }
        result_delta[i] = (pos == 1) ? 0 : delta[pos];
    }

    vector<long long> result(n + 1);
    result[1] = x[1];
    for (int i = 2; i <= n; ++i) {
        result[i] = result[i - 1] + result_delta[i];
    }

    for (int i = 1; i <= n; ++i) {
        cout << result[i] << "\n";
    }
    return 0;
}

D - Pirâmide da Mediana Difícil

Usamos busca binária na resposta. Para um valor candidato, transformamos a sequência em uma string binária (menor ou igual ao candidato vs. maior). A mediana final é determinada pelo par adjacente mais próximo do centro com a mesma cor. Se não houver tal par, a cor é a da borda.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(2 * n - 1);
    for (int i = 0; i < 2 * n - 1; ++i) {
        cin >> a[i];
    }

    int left = 1, right = 2 * n - 1, answer = 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        bool found_higher_pair = false;
        bool found_lower_pair = false;
        int center = n - 1; // zero-indexed

        for (int d = 0; d < n; ++d) {
            int idx1 = center - d;
            int idx2 = idx1 + 1;
            if (idx1 >= 0 && idx2 < 2 * n - 1) {
                if (a[idx1] >= mid && a[idx2] >= mid) {
                    found_higher_pair = true;
                    break;
                }
                if (a[idx1] < mid && a[idx2] < mid) {
                    found_lower_pair = true;
                    break;
                }
            }
        }

        if (found_higher_pair || (!found_lower_pair && a[0] >= mid)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << answer;
    return 0;
}

E - Rotação 3x3

A rotação de 180 graus em uma subgrade 3x3 preserva a paridade das colunas e pode inverter a ordem das linhas. Modelamos as colunas como sequências com sinais. A solubilidade depende da paridade das inversões e do número de negativos em duas subsequências.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct BIT {
    int n;
    vector<bool> tree;
    BIT(int size) : n(size), tree(size + 1, false) {}
    void update(int idx) {
        for (; idx > 0; idx -= idx & -idx) tree[idx] = !tree[idx];
    }
    bool query(int idx) {
        bool res = false;
        for (; idx <= n; idx += idx & -idx) res = res ^ tree[idx];
        return res;
    }
};

int main() {
    int n;
    cin >> n;
    vector<vector<int>> grid(3, vector<int>(n + 1));
    for (int row = 0; row < 3; ++row) {
        for (int col = 1; col <= n; ++col) {
            cin >> grid[row][col];
        }
    }

    vector<int> pattern(n + 1);
    vector<bool> flipped(2, false); // flipped[0] for even columns, flipped[1] for odd columns

    for (int col = 1; col <= n; ++col) {
        if (grid[0][col] == grid[1][col] - 1 && grid[1][col] == grid[2][col] - 1 && grid[2][col] % 3 == 0) {
            pattern[col] = grid[2][col] / 3;
        } else if (grid[0][col] == grid[1][col] + 1 && grid[1][col] == grid[2][col] + 1 && grid[0][col] % 3 == 0) {
            pattern[col] = grid[0][col] / 3;
            flipped[col % 2] = !flipped[col % 2];
        } else {
            cout << "No";
            return 0;
        }
        if ((pattern[col] % 2) != (col % 2)) {
            cout << "No";
            return 0;
        }
    }

    BIT even_tree(n), odd_tree(n);
    long long inversions[2] = {0, 0};

    for (int col = 1; col <= n; ++col) {
        if (col % 2 == 0) {
            inversions[0] ^= even_tree.query(pattern[col]);
            even_tree.update(pattern[col]);
        } else {
            inversions[1] ^= odd_tree.query(pattern[col]);
            odd_tree.update(pattern[col]);
        }
    }

    if ((inversions[1] ^ flipped[0]) || (inversions[0] ^ flipped[1])) {
        cout << "No";
    } else {
        cout << "Yes";
    }
    return 0;
}

F - Apagão

Modelamos o problema com grafo direcionado onde arestas representam operações possíveis. Cada componente fraco pode ser colorido com 3 cores. Se a colorição for válida, o número máximo de arestas é a soma dos produtos dos tamanhos das cores. Se a colorição falhar, o componente pode ser transformado em um grafo completo.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n + 1), reverse_graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        reverse_graph[v].push_back(u);
    }

    vector<bool> visited(n + 1, false);
    long long total_edges = 0;

    for (int start = 1; start <= n; ++start) {
        if (visited[start]) continue;

        vector<int> component;
        queue<int> q;
        q.push(start);
        visited[start] = true;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            component.push_back(u);
            for (int v : graph[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
            for (int v : reverse_graph[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }

        int size = component.size();
        vector<int> color(size, -1);
        bool valid = true;
        vector<int> cnt(3, 0);

        auto dfs = [&](int u, int col, auto&& dfs_ref) -> void {
            int idx = -1;
            for (int i = 0; i < size; ++i) {
                if (component[i] == u) { idx = i; break; }
            }
            color[idx] = col;
            cnt[col]++;
            for (int v : graph[u]) {
                int vidx = -1;
                for (int i = 0; i < size; ++i) {
                    if (component[i] == v) { vidx = i; break; }
                }
                if (vidx != -1) {
                    if (color[vidx] == -1) {
                        dfs_ref(v, (col + 1) % 3, dfs_ref);
                    } else if (color[vidx] != (col + 1) % 3) {
                        valid = false;
                    }
                }
            }
            for (int v : reverse_graph[u]) {
                int vidx = -1;
                for (int i = 0; i < size; ++i) {
                    if (component[i] == v) { vidx = i; break; }
                }
                if (vidx != -1) {
                    if (color[vidx] == -1) {
                        dfs_ref(v, (col + 2) % 3, dfs_ref);
                    } else if (color[vidx] != (col + 2) % 3) {
                        valid = false;
                    }
                }
            }
        };

        dfs(component[0], 0, dfs);

        if (!valid) {
            total_edges += (long long)size * size;
        } else if (cnt[0] && cnt[1] && cnt[2]) {
            total_edges += (long long)cnt[0] * cnt[1] + (long long)cnt[1] * cnt[2] + (long long)cnt[2] * cnt[0];
        } else {
            int edges = 0;
            for (int u : component) {
                edges += graph[u].size();
            }
            total_edges += edges;
        }
    }

    cout << total_edges;
    return 0;
}