Acordei às oito da manhã para analisar os problemas. O problema T1 parecia similar a um desafio que já havia resolvido anteriormente, envolvendo BFS com otimizações, mas o código poderia ser extenso, então decidi adiar. O problema T2 tinha restrições idênticas a um problema D de uma competição Codeforces que resolvi há um ano, embora o objetivo fosse diferente. Ainda sonolento, não quis deduzir as fórmulas e também adiei. O problema T3 parecia ser sobre propriedades interessantes, com uma solução O(n²) óbvia, mas a otimização exigiria melhorias nas consultas de intervalo e no método de verificação, o que também me desencorajou no momento.

Decidi abordar os problemas em ordem. O T1 parecia um problema de caminho mínimo. Comecei a codificar às 8:25, terminei em meia hora após alguns contratempos, fiz uma depuração rápida e deixei de lado.

Saí para o café da manhã e, no caminho, percebi que o T3 precisava verificar apenas O(n) intervalos, mas ainda só conseguia uma verificação O(n²).

De volta, comecei o T2. Tive uma dificuldade momentânea por um erro de lógica, mas o resto correu bem. Terminei e ajustei o código às 10:30.

Retornei ao T3, escrevi uma solução para 60 pontos em 10 minutos, e então encontrei uma forma de obter a pontuação máxima. Fiquei preso em um detalhe de borda por um tempo, mas finalizei às 11:20.

A plataforma de avaliação demorou a processar as submissões. Após o almoço, descobri que o T3 falhou. O erro era ter escrito sum\[r\] em vez de sum\[r+1\]. Corrigi e a solução foi aceita. Foi frustrante.

Claramente, preciso aprimorar minha habilidade de codificação.

Soluções

T1

Uma abordagem BFS direta pode não ser suficiente. A melhor estratégia é modelar como um problema de caminho mínimo. Primeiro, conecte os pontos vizinhos (quatro direções). Depois, considere o efeito dos teletransportes: um ponto pode alcançar a parede mais próxima em qualquer direção, com um custo igual ao tempo para chegar à parede mais próxima.

Construa o grafo e aplique um algoritmo de caminho mínimo.

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 510, INF = 1e9;
int linhas, colunas;
char grade[MAXN][MAXN];
int distParede[MAXN][MAXN];
int idPonto[MAXN][MAXN], totalNos;
int origem, destino;
int adj[250010][250010];

struct Estado {
    int no, dist;
    bool operator<(const Estado& outro) const {
        return dist > outro.dist;
    }
};

void calcularDistParedes() {
    queue<pair<int,int>> fila;
    for (int i = 0; i < linhas; i++) {
        for (int j = 0; j < colunas; j++) {
            if (grade[i][j] == '#') {
                fila.push({i, j});
                distParede[i][j] = 0;
            }
        }
    }
    int dirs[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    while (!fila.empty()) {
        auto [x, y] = fila.front(); fila.pop();
        for (auto& d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            if (nx >= 0 && nx < linhas && ny >= 0 && ny < colunas && 
                grade[nx][ny] == '.' && distParede[nx][ny] == -1) {
                distParede[nx][ny] = distParede[x][y] + 1;
                fila.push({nx, ny});
            }
        }
    }
}

void encontrarParedeMaisProxima() {
    for (int i = 0; i < linhas; i++) {
        for (int j = 0; j < colunas; j++) {
            if (grade[i][j] == '.') {
                if (i > 0 && grade[i-1][j] == '#') {
                    adj[idPonto[i][j]][idPonto[i-1][j]] = distParede[i][j];
                }
                // Repetir para outras direções
            }
        }
    }
}

int dijkstra() {
    vector<int> dist(totalNos, INF);
    dist[origem] = 0;
    priority_queue<Estado> pq;
    pq.push({origem, 0});
    while (!pq.empty()) {
        Estado atual = pq.top(); pq.pop();
        if (atual.dist > dist[atual.no]) continue;
        if (atual.no == destino) return atual.dist;
        for (int i = 0; i < totalNos; i++) {
            if (adj[atual.no][i]) {
                int novoDist = atual.dist + adj[atual.no][i];
                if (novoDist < dist[i]) {
                    dist[i] = novoDist;
                    pq.push({i, novoDist});
                }
            }
        }
    }
    return -1;
}

int main() {
    freopen("cell.in", "r", stdin);
    freopen("cell.out", "w", stdout);
    memset(distParede, -1, sizeof(distParede));
    cin >> linhas >> colunas;
    for (int i = 0; i < linhas; i++) {
        cin >> grade[i];
        for (int j = 0; j < colunas; j++) {
            if (grade[i][j] == '.') {
                idPonto[i][j] = totalNos++;
            }
        }
    }
    for (int i = 0; i < linhas; i++) {
        for (int j = 0; j < colunas; j++) {
            if (grade[i][j] == 'C') {
                origem = idPonto[i][j]; grade[i][j] = '.';
            } else if (grade[i][j] == 'F') {
                destino = idPonto[i][j]; grade[i][j] = '.';
            }
        }
    }
    calcularDistParedes();
    encontrarParedeMaisProxima();
    int resultado = dijkstra();
    if (resultado != -1) cout << resultado;
    else cout << "no";
    return 0;
}

T2

Aproveitando as propriedades das BSTs, a primeira etapa é ordenar os nós pelo valor da chave. Em seguida, pré-processe uma matriz para verificar se quaisquer dois nós podem ser conectados.

Para a DP, em vez de uma abordagem O(n⁵), otimize. A left e right subtrees are independentes. Defina f\[i\]\[j\]\[0\] como o valor máximo para o intervalo \[i,j\] como a subárvore direita de i-1, e f\[i\]\[j\]\[1\] como o valor máximo como a subárvore esquerda de j+1. A transição envolve escolher qual nó será o filho direto de i-1 ou o filho esquerdo de j+1. Isso resulta em uma complexidade de O(n³).

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int MAXN = 310;
int totalNos;
ll dp[MAXN][MAXN][2];
ll prefixo[MAXN];
pair<int, int> nos[MAXN];
int conexaoPossivel[MAXN][MAXN];

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin >> totalNos;
    for (int i = 1; i <= totalNos; i++) {
        cin >> nos[i].first >> nos[i].second;
    }
    sort(nos + 1, nos + 1 + totalNos);
    for (int i = 1; i <= totalNos; i++) {
        for (int j = 1; j <= totalNos; j++) {
            conexaoPossivel[i][j] = gcd(nos[i].first, nos[j].first);
        }
    }
    for (int i = 1; i <= totalNos; i++) {
        prefixo[i] = prefixo[i - 1] + nos[i].second;
    }
    memset(dp, -0x3f, sizeof(dp));
    for (int i = 1; i <= totalNos; i++) {
        if (i > 1 && conexaoPossivel[i][i-1] != 1) dp[i][i][0] = nos[i].second;
        if (i < totalNos && conexaoPossivel[i][i+1] != 1) dp[i][i][1] = nos[i].second;
    }
    ll resposta = -1;
    for (int tam = 2; tam <= totalNos; tam++) {
        for (int i = 1; i + tam - 1 <= totalNos; i++) {
            int j = i + tam - 1;
            for (int k = i; k <= j; k++) {
                ll val;
                if (k == i) val = dp[i+1][j][0] + prefixo[j] - prefixo[i-1];
                else if (k == j) val = dp[i][j-1][1] + prefixo[j] - prefixo[i-1];
                else val = dp[i][k-1][1] + dp[k+1][j][0] + prefixo[j] - prefixo[i-1];
                
                if (i > 1 && conexaoPossivel[k][i-1] != 1) dp[i][j][0] = max(dp[i][j][0], val);
                if (j < totalNos && conexaoPossivel[k][j+1] != 1) dp[i][j][1] = max(dp[i][j][1], val);
                
                if (tam == totalNos) resposta = max(resposta, val);
            }
        }
    }
    if (resposta < 0) cout << "-1";
    else cout << resposta;
    return 0;
}

T3

Para 30 pontos, uma força bruta O(n³) é suficiente: enumerar intervalos e verificar cada um. Para 60 pontos, O(n²), enumere o centro da rotação e agrupe as verificações.

Para a solução completa, note que os intervalos válidos podem ser otimizados para O(n). Se \[l,r\] é um intervalo de rotação onde a\[l\] != r e a\[r\] != l, a troca é inútil. O intervalo pode ser encolhido. Portanto, só precisamos verificar intervalos da forma \[i,a\[i\]\] ou \[a\[i\],i\].

Para otimizar a verificação, agrupe os intervalos com o mesmo centro de rotação, ordenados por comprimento. Para um intervalo \[l,r\], a resposta é pontosVálidos(1,l-1) + k + pontosVálidos(r+1,n), onde k é o número de intervalos processados. Isso funciona porque o aumento em nowsum só ocorre devido às rotações.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int totalElementos;
int arr[100010];
int prefixo[100010];
vector<int> grupos[200010];

int main() {
    ios::sync_with_stdio(false);
    cin >> totalElementos;
    for (int i = 1; i <= totalElementos; i++) {
        cin >> arr[i];
        prefixo[i] = prefixo[i-1] + (arr[i] == i);
    }
    for (int i = 1; i <= totalElementos; i++) {
        grupos[i + arr[i]].push_back(abs(i - arr[i]) + 1);
    }
    int resposta = prefixo[totalElementos];
    for (int soma = 1; soma <= 2 * totalElementos; soma++) {
        if (grupos[soma].empty()) continue;
        sort(grupos[soma].begin(), grupos[soma].end());
        for (size_t idx = 0; idx < grupos[soma].size(); idx++) {
            int comprimento = grupos[soma][idx];
            int esq, dir;
            if (soma % 2 == 0) {
                esq = soma / 2 - comprimento / 2;
                dir = soma / 2 + (comprimento - 1) / 2;
            } else {
                esq = soma / 2 - comprimento / 2 + 1;
                dir = soma / 2 + comprimento / 2;
            }
            resposta = max(resposta, (int)idx + 1 + prefixo[esq-1] + prefixo[totalElementos] - prefixo[dir]);
        }
    }
    cout << resposta;
    return 0;
}