Durante uma competição de programação, foram abordados quatro problemas. A seguir, uma análise técnica de cada um, incluindo enunciados, estratégias durante a prova e soluções otimizadas com implementações em código.
Registro da Competição
Para o Problema 1, a leitura do enunciado levou cerca de 28 minutos, e a solução foi desenvolvida após 40 minutos de análise. Foram realizados 60 testes de verificação com sucesso. No Problema 2, a abordagem envolveu modelar a velocidade como parte do estado do grafo, construindo um grafo em camadas e aplicando o algoritmo de Dijkstra. No entanto, houve um erro na conexão das arestas, corrigido posteriormente. O Problema 3 foi resovlido utilizando multiplicação de matrizes, com a otimização de compactar a posição das peças em uma dimensão. Verificou-se que a operação de peça (op) variava de 0 a 2, em vez de 1 a 3. A otimização do código resultou em tempo de execução dentro dos limites. O Problema 4 envolveu técnicas como união por tamanho em árvores, mas uma solução eficiente não foi implementada durante a prova, levando a uma abordagem por força bruta que falhou devido a uma omissão no módulo de operações.
Problema 1: XOR de Sequência
Enunciado
Dada uma sequência de comprimento \(n\), denotada como \(a\), determine a quantidade de quartetos \((i, j, k, l)\) que satisfazem \(a_i \oplus a_j \oplus a_k \oplus a_l = 0\), onde \(\oplus\) representa a operação XOR.
Solução Ótima
A condição \(a_i \oplus a_j \oplus a_k \oplus a_l = 0\) é equivalente a \(a_i \oplus a_j = a_k \oplus a_l\). Portanto, para cada par de índices \((i, j)\), calcula-se o valor \(a_i \oplus a_j\) e armazena-se a contagem em um array auxiliar. Em seguida, para cada par \((k, l)\), verifica-se se o valor \(a_k \oplus a_l\) corresponde a algum valor previamente contado. Isso pode ser implementado com complexidade de tempo \(O(n^2)\).
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 5010;
const int MAX_XOR = 1 << 20;
int seq[MAX_N];
long long xorCounter[MAX_XOR];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int len;
cin >> len;
for (int idx = 1; idx <= len; ++idx) {
cin >> seq[idx];
}
long long result = 0;
for (int i = 2; i <= len - 2; ++i) {
for (int j = 1; j < i; ++j) {
xorCounter[seq[i] ^ seq[j]]++;
}
for (int j = i + 2; j <= len; ++j) {
result += xorCounter[seq[i + 1] ^ seq[j]];
}
}
cout << result << '\n';
return 0;
}
Problema 2: Viagem com Velocidade Variável
Enunciado
Considere um grafo direcionado com \(n\) vértices e \(m\) arestas, cada aresta com peso \(d\) e um atributo especial \(w\). A velocidade inicial é \(v = 1\). Existem \(p\) vértices especiais onde, ao pagar um custo \(c_i\), a velocidade é dobrada (\(v \gets 2v\)). O tempo para percorrer uma aresta com peso \(d\) na velocidade \(v\) é \(\lceil d / v \rceil\). Se \(w = 0\), a velocidade permanece inalterdaa após a aresta; se \(w = 1\), a velocidade é resetada para 1. Determine o caminho mínimo do vértice \(s\) ao vértice \(t\).
Solução Ótima
Observa-se que quando a velocidade é suficientemente alta (por exemplo, \(2^{20}\)), o tempo para percorrer qualquer aresta se estabiliza. Portanto, cada vértice é expandido em 21 camadas (de 0 a 20), representando velocidades de \(2^k\). Arestas com \(w = 1\) são conectadas à camada 0, e nos vértices especiais, adicionam-se arestas para a camada superior com custo correspondente. O grafo resultante é analisado com o algoritmo de Dijkstra, resultando em complexidade \(O(m \log n \log V)\).
#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
struct Edge {
int destination;
int next;
long long weight;
};
const int MAX_EDGES = 2000010;
const int MAX_NODES = 420010;
Edge edges[MAX_EDGES];
int head[MAX_NODES], edgeCount = 1;
void addEdge(int from, int to, long long w) {
edges[edgeCount] = {to, head[from], w};
head[from] = edgeCount++;
}
int nodeCount, edgeNum, source, target, specialCount;
struct State {
int node;
long long dist;
bool operator<(const State& other) const {
return dist > other.dist;
}
};
priority_queue<state> pq;
long long distances[MAX_NODES];
bool visited[MAX_NODES];
void dijkstra() {
memset(distances, 0x3f, sizeof(distances));
pq.push({source, 0});
distances[source] = 0;
while (!pq.empty()) {
State current = pq.top();
pq.pop();
int u = current.node;
if (visited[u]) continue;
visited[u] = true;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].destination;
long long w = edges[i].weight;
if (distances[v] > distances[u] + w) {
distances[v] = distances[u] + w;
pq.push({v, distances[v]});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> nodeCount >> edgeNum >> source >> target;
for (int i = 1; i <= edgeNum; ++i) {
int u, v, w;
char type;
cin >> u >> v >> w >> type;
if (type == 'G') {
for (int layer = 0; layer <= 20; ++layer) {
long long time = (w + (1 << layer) - 1) / (1 << layer);
addEdge(layer * nodeCount + u, layer * nodeCount + v, time);
}
} else {
for (int layer = 0; layer <= 20; ++layer) {
long long time = (w + (1 << layer) - 1) / (1 << layer);
addEdge(layer * nodeCount + u, v, time);
}
}
}
cin >> specialCount;
for (int i = 1; i <= specialCount; ++i) {
int u;
long long cost;
cin >> u >> cost;
for (int layer = 0; layer < 20; ++layer) {
addEdge(layer * nodeCount + u, (layer + 1) * nodeCount + u, cost);
}
}
dijkstra();
long long answer = INF;
for (int layer = 0; layer <= 20; ++layer) {
answer = min(answer, distances[layer * nodeCount + target]);
}
if (answer == INF) {
cout << "-1\n";
} else {
cout << answer << '\n';
}
return 0;
}
</state>
Problema 3: Contagem de Movimentos em Tabuleiro
Enunciado
Em um tabuleiro de dimensões \(a \times b\), uma peça está localizada em \((c, d)\). A peça pode ser um carro, cavalo ou bispo (tipos 0, 1, 2, respectivamente), seguindo as regras de movimentação do xadrez chinês. Determine o número total de sequências de movimentos possíveis em exatamente \(e\) passos.
Solução Ótima
Dado que \(e\) pode ser até \(10^9\), utiliza-se multiplicação de matrizes por exponenciação rápida. As posições do tabuleiro são renumeradas linearmente e achatadas para uma dimensão. A matriz de transição é construída onde cada entrada \((i, j)\) é 1 se a peça puder mover da posição \(i\) para \(j\) em um passo. O resultado é obtido elevando a matriz à potência \(e\) e somando os elementos da linha correspondente à posição inicial. A complexidade é \(O((ab)^3 \log e)\).
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 19260817;
struct Matrix {
int rows, cols;
vector<vector<long long>> data;
Matrix(int r = 0, int c = 0) : rows(r), cols(c), data(r, vector<long long>(c, 0)) {}
Matrix operator*(const Matrix& other) const {
Matrix result(rows, other.cols);
if (cols != other.rows) return result;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < other.cols; ++j) {
for (int k = 0; k < cols; ++k) {
result.data[i][j] = (result.data[i][j] + data[i][k] * other.data[k][j]) % MOD;
}
}
}
return result;
}
};
Matrix matPower(Matrix base, long long exp) {
Matrix result(base.rows, base.cols);
for (int i = 0; i < base.rows; ++i) result.data[i][i] = 1;
while (exp > 0) {
if (exp % 2 == 1) result = result * base;
base = base * base;
exp /= 2;
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int queries;
cin >> queries;
while (queries--) {
int pieceType, rows, cols, startRow, startCol;
long long steps;
cin >> pieceType >> rows >> cols >> startRow >> startCol >> steps;
int totalPositions = rows * cols;
Matrix transition(totalPositions, totalPositions);
for (int pos1 = 0; pos1 < totalPositions; ++pos1) {
int r1 = pos1 / cols + 1;
int c1 = pos1 % cols + 1;
for (int pos2 = 0; pos2 < totalPositions; ++pos2) {
int r2 = pos2 / cols + 1;
int c2 = pos2 % cols + 1;
bool canMove = false;
if (pieceType == 0) { // Carro
canMove = (r1 == r2 || c1 == c2);
} else if (pieceType == 1) { // Cavalo
canMove = (abs(r1 - r2) == 2 && abs(c1 - c2) == 1) || (abs(r1 - r2) == 1 && abs(c1 - c2) == 2);
} else { // Bispo
canMove = (abs(r1 - r2) == 2 && abs(c1 - c2) == 2);
}
if (canMove) transition.data[pos1][pos2] = 1;
}
}
Matrix initial(1, totalPositions);
int startPos = (startRow - 1) * cols + (startCol - 1);
initial.data[0][startPos] = 1;
Matrix finalState = initial * matPower(transition, steps);
long long sum = 0;
for (int i = 0; i < totalPositions; ++i) {
sum = (sum + finalState.data[0][i]) % MOD;
}
cout << sum << '\n';
}
return 0;
}
Problema 4: Técnicas em Árvores
Enunciado
O Problema 4 envolve consultas em uma estrutura de árvore, onde soluções eficientes requerem técnicas como união por tamanho ou estruturas de dados avançadas. Durante a competição, uma abordagem por toça bruta foi implementada, mas falhou devido a erros na implementação. Soluções ideais podem incluir fusão de árvores de segmentos ou árvores persistentes.
A análise completa dos problemas demonstra a aplicação de algoritmos fundamentais como XOR em pares, grafos em camadas com Dijkstra, multiplicação de matrizes para exponenciação rápida e técnicas em árvores, destacando a importância da modelagem correta e otimização em competições de programação.