O 2024 ICPC Asia Chengdu Regional Contest apresentou um conjunto diversificado de desafios, desde construções simples até problemas envolvendo Programação Dinâmica tridimensional e estruturas de dados. Abaixo, detalhamos a lógica de resolução para os principais problemas da competição.
Problema L: Construção de Sequência
Descrição: O objetivo é construir uma sequência de números onde 50% dos elementos sejam menores ou iguais a a, 95% menores ou iguais a b e 99% menores ou iguais a c.
Estratégia: Podemos fixar o tamanho da sequência em 100 elementos. A construção segue a distribuição percentual solicitada: os primeiros 50 números recebem o valor a, os próximos 45 recebem b, os 4 seguintes recebem c, e o último elemento recebe um valor estritamente maior que c (por exemplo, c + 1).
void process_l() {
int val_a, val_b, val_c;
if (!(cin >> val_a >> val_b >> val_c)) return;
const int total_size = 100;
cout << total_size << "\n";
for (int i = 0; i < 50; ++i) cout << val_a << (i == 99 ? "" : " ");
for (int i = 0; i < 45; ++i) cout << val_b << " ";
for (int i = 0; i < 4; ++i) cout << val_c << " ";
cout << val_c + 1 << endl;
}
Problema J: Simulação de Pontuação
Descrição: Simular um sistema de rodadas onde os jogadores ganham pontos baseados na ordem de acerto quando o valor atual coincide com uma chave específica.
Estratégia: Utilizamos um mapa para rastrear quais usuários já pontuaram em uma rodada específicca e um veter de pares para armazenar o ID do jogador e sua pontuação acumulada. A cada nova operação do tipo 1 (reset), limpamos o estado da rodada atual.
void process_j() {
int num_players, num_ids, num_queries;
cin >> num_players >> num_ids >> num_queries;
vector<pair<int, long long>> scoreboard(num_ids + 1);
for (int i = 1; i <= num_ids; ++i) scoreboard[i] = {i, 0};
int current_key = -1;
int points_available = num_ids;
map<int, bool> has_scored;
while (num_queries--) {
int type;
cin >> type;
if (type == 1) {
cin >> current_key;
has_scored.clear();
points_available = num_ids;
} else if (type == 2) {
int p_id, p_val;
cin >> p_id >> p_val;
if (p_val == current_key && !has_scored[p_id]) {
has_scored[p_id] = true;
scoreboard[p_id].second += points_available--;
}
} else {
int p_id, p_val;
cin >> p_id >> p_val;
if (p_val == current_key) has_scored[p_id] = true;
}
}
sort(scoreboard.begin() + 1, scoreboard.end(), [](const auto& a, const auto& b) {
if (a.second != b.second) return a.second > b.second;
return a.first < b.first;
});
for (int i = 1; i <= num_ids; ++i) {
cout << scoreboard[i].first << " " << scoreboard[i].second << "\n";
}
}
Problema G: Operações Bitwise e Cardinalidade
Descrição: Dado um array, você pode inserir entre elementos adjacentes o resultado de AND, OR ou XOR entre eles. Determine o número máximo de elementos distintos possíveis no array após infinitas operações.
Estratégia: O número de novos valores é limitado pelas combinações bitwise dos vizinhos imediatos. Como operações repetidas de bitwise convergem rapidamente, podemos simular as combinações de l op r e os resultados dessas operações com l e r originais.
void process_g() {
int n;
cin >> n;
vector<int> elements(n);
set<int> distinct_vals;
distinct_vals.insert(0);
for (int &x : elements) cin >> x;
for (int i = 0; i < n - 1; ++i) {
int left = elements[i], right = elements[i+1];
distinct_vals.insert(left);
distinct_vals.insert(right);
int ops[] = {left & right, left | right, left ^ right};
for (int res : ops) {
distinct_vals.insert(res);
distinct_vals.insert(res & left);
distinct_vals.insert(res | left);
distinct_vals.insert(res ^ left);
distinct_vals.insert(res & right);
distinct_vals.insert(res | right);
distinct_vals.insert(res ^ right);
}
}
if(n == 1) distinct_vals.insert(elements[0]);
cout << distinct_vals.size() << endl;
}
Problema A: Transformação em Símbolos de Flecha
Descrição: Transformar uma string vazia em uma string alvo s usando operações que criam "flechas" (ex: >--->>>). Cada flecha deve ter pelo menos 5 caracteres, começar com >, terminar com >>> e ter - no meio.
Estratégia: Verifique primeiro as condições impossíveis (string toda composta por > ou que não termina em >>>). A estratégia consiste em preencher a parte final da string e depois processar os prefixos de forma gananciosa.
void process_a() {
string target;
cin >> target;
int len = target.size();
int count_gt = 0;
for(char c : target) if(c == '>') count_gt++;
if (count_gt == len || target[0] == '-' || target.substr(len - 3) != ">>>") {
cout << "No\n";
return;
}
int suffix_start = len - 1;
for (int i = len - 1; i >= 2; --i) {
if (target.substr(i - 2, 3) == ">>>") suffix_start = i;
else break;
}
cout << "Yes ";
vector<pair<int, int>> steps;
for (int i = len - 1; i >= suffix_start; --i) {
steps.push_back({i - 3, 5});
}
for (int i = 0; i < suffix_start - 2; ++i) {
if (target[i] == '>') {
steps.push_back({i + 1, suffix_start - i + 1});
}
}
cout << steps.size() << "\n";
for (auto p : steps) cout << p.first << " " << p.second << "\n";
}
Problema I: Divisores e GCD em Árvore de Segmentos
Descrição: Dada uma sequência, uma partição em blocos de tamanho k é válida se cada bloco for não-decrescente. Suporte atualizações pontuais e conte quantas partições k são válidas.
Estratégia: Uma partição k é válida se todos os pontos onde a[i] > a[i+1] forem múltiplos de k. Isso implica que k deve ser um divisor do Máximo Divisor Comum (GCD) de todas as posições i onde a condição de ordem é violada. Usamos uma Segment Tree para manter o GCD dessas posições.
int tree[1200005];
void update_tree(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) update_tree(node * 2, start, mid, idx, val);
else update_tree(node * 2 + 1, mid + 1, end, idx, val);
tree[node] = std::gcd(tree[node * 2], tree[node * 2 + 1]);
}
void process_i() {
int n, q;
cin >> n >> q;
vector<int> arr(n + 1);
vector<int> divisor_count(n + 1, 0);
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; j += i) divisor_count[j]++;
}
for (int i = 1; i <= n; ++i) cin >> arr[i];
for (int i = 1; i < n; ++i) {
if (arr[i] > arr[i + 1]) update_tree(1, 1, n, i, i);
}
auto get_ans = [&]() {
int g = tree[1];
return g == 0 ? n : divisor_count[g];
};
cout << get_ans() << "\n";
while (q--) {
int pos, v;
cin >> pos >> v;
arr[pos] = v;
if (pos > 1) {
update_tree(1, 1, n, pos - 1, (arr[pos - 1] > arr[pos] ? pos - 1 : 0));
}
if (pos < n) {
update_tree(1, 1, n, pos, (arr[pos] > arr[pos + 1] ? pos : 0));
}
cout << get_ans() << "\n";
}
}
Problema B: DP com Restrições de Caracteres
Descrição: Conte quantas strings de comprimento n podem ser formadas substituindo '?' por 'a', 'b' ou 'c' sem caracteres adjacentes iguais, respeitando limites extras x, y, z para cada caractere.
Estratégia: Definimos dp[i][ca][cb][last] como o número de formas de preencher até a posição i usando ca caracteres 'a' extras, cb 'b' extras, terminando no caractere last. Após calcular a DP, utilizamos somas de prefixo 3D (Inclusion-Exclusion) para responder às consultas em O(1).
long long memo[305][305][3];
long long sum_pref[305][305][305];
const int MOD = 1e9 + 7;
void process_b() {
int n, queries;
string s;
cin >> n >> queries >> s;
// Lógica de DP simplificada e pré-processamento de somas 3D
// ... (Implementação de DP omitida por brevidade, seguindo a lógica de estado mencionada)
// Resposta da consulta via prefix sum 3D:
// result = sum_pref[x][y][z]
}