Neste artigo, exploramos soluções detalhadas para os problemas da 5ª etapa da Universal Cup (Osijek), focando em abordagens algorítmicas avançadas como NTT, Casco Convexo e Programação Dinâmica.
D. Distinct Subsequences
O desafio consiste em contar quantas subsequências distintas de comprimento k podem ser formadas a partir de uma string binária s.
Para subsequências distintas, utilizamos uma DP clássica: se $lst_i$ é a última ocorrência do caractere $s_i$, a transição é $f_i = \sum_{j=lst_i}^{i-1} f_j$. Introduzindo uma dimensão para o comprimento, temos $g_{i, j} = g_{i - 1, j} + g_{i - 1, j - 1} - g_{lst_i - 1, j - 1}$.
Podemos repersentar as transições como polinômios: $G_i(x) = (1+x) G_{i-1}(x) - x G_{lst_i - 1}(x)$. Como o alfabeto é $\{0, 1\}$, mantemos o estado das últimas posições de '0' e '1'. Através de uma matriz de transição de polinômios e técnica de Divisão e Conquista combinada com NTT (Fast Number Theoretic Transform), conseguimos resolver em $O(3^2 n \log^2 n)$.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353, RAIZ = 3;
long long exp_mod(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
void ntt_transform(vector<int> &a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
long long wlen = exp_mod(RAIZ, (MOD - 1) / len);
if (invert) wlen = exp_mod(wlen, MOD - 2);
for (int i = 0; i < n; i += len) {
long long w = 1;
for (int j = 0; j < len / 2; j++) {
int u = a[i + j], v = (int)(1LL * a[i + j + len / 2] * w % MOD);
a[i + j] = (u + v) % MOD;
a[i + j + len / 2] = (u - v + MOD) % MOD;
w = (w * wlen) % MOD;
}
}
}
if (invert) {
long long n_inv = exp_mod(n, MOD - 2);
for (int &x : a) x = (int)(1LL * x * n_inv % MOD);
}
}
struct PolinomioMatriz {
vector<int> mat[3][3];
};
PolinomioMatriz solve_recursive(int l, int r, const string &s) {
if (l == r) {
PolinomioMatriz res;
for(int i=0; i<3; i++) for(int j=0; j<3; j++) res.mat[i][j] = {0};
if (s[l-1] == '1') {
res.mat[0][0] = {1}; res.mat[1][2] = {0, MOD - 1};
res.mat[2][1] = {1}; res.mat[2][2] = {1, 1};
} else {
res.mat[0][2] = {0, MOD - 1}; res.mat[1][1] = {1};
res.mat[2][0] = {1}; res.mat[2][2] = {1, 1};
}
return res;
}
int mid = (l + r) / 2;
PolinomioMatriz L = solve_recursive(l, mid, s);
PolinomioMatriz R = solve_recursive(mid + 1, r, s);
int lim = 1;
while (lim <= (r - l + 1)) lim <<= 1;
for(int i=0; i<3; i++) {
for(int j=0; j<3; j++) {
L.mat[i][j].resize(lim, 0); R.mat[i][j].resize(lim, 0);
ntt_transform(L.mat[i][j], false); ntt_transform(R.mat[i][j], false);
}
}
PolinomioMatriz res;
for(int i=0; i<3; i++) {
for(int j=0; j<3; j++) {
res.mat[i][j].resize(lim, 0);
for(int k=0; k<3; k++) {
for(int t=0; t<lim; t++)
res.mat[i][j][t] = (res.mat[i][j][t] + 1LL * L.mat[i][k][t] * R.mat[k][j][t]) % MOD;
}
ntt_transform(res.mat[i][j], true);
}
}
return res;
}
int main() {
int n, k; cin >> n >> k;
string s; cin >> s;
auto res = solve_recursive(1, n, s);
cout << res.mat[2][2][k] << endl;
return 0;
}
C. Cyclic Shifts
O objetivo é ordenar uma permutação de tamanho n usando deslocamentos cíclicos de subconjuntos de k elementos com custo total $\le 2$.
A chave é observar que um deslocamento cíclico de $n-1$ elementos equivale a uma troca (swap) entre o elemento excluído e seu vizinho, seguida de uma rotação. Ao processar elementos em posições não adjacentes, podemos realizar múltiplos swaps simultâneos. Implementamos uma variante do Bubble Sort: em cada iteração, realizamos swaps em todas as posições ímpares possíveis e depois nas pares. Realizando isso em $n$ rodadas, o custo total converge para 2.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) cin >> p[i];
cout << n << endl;
for (int i = 0; i < n; i++) {
string mask(n, '1');
int start = (n - i) % 2;
for (int j = start; j < n - 1; j += 2) {
if (p[j] > p[j + 1]) {
swap(p[j], p[j + 1]);
mask[(i + j + 1) % n] = '0';
}
}
cout << mask << "\n";
}
return 0;
}
H. Holiday Regifting
Em um DAG, cada nó possui uma capacidade $c_i$. O nó 1 recebe presentes periodicamente. Quando a capacidade de um nó é atingida, ele distribui presentes para seus sucessores. Queremos o momento em que todos os nós estão vazios.
Processamos os nós em ordem topológica. Para cada prefixo da ordenação, mantemos o ciclo mínimo $T$. Ao adicionar o próximo nó, calculamos quantos ciclos são necessários para zerar sua carga acumulada usando o MDC entre a capacidade e o acúmulo atual. Atualizamos o ciclo global e simulamos a propagação para os sucessores.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main() {
int n, m; cin >> n >> m;
vector<int> cap(n + 1);
for (int i = 1; i <= n; i++) cin >> cap[i];
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
}
long long ciclo_total = 1;
vector<long long> carga(n + 1, 0);
carga[1] = 1;
for (int i = 1; i <= n; i++) {
long long g = cap[i] / __gcd((long long)cap[i], carga[i]);
ciclo_total = (ciclo_total * (g % MOD)) % MOD;
for (int j = i; j <= n; j++) carga[j] *= g;
for (int j = i; j <= n; j++) {
for (int v : adj[j]) carga[v] += carga[j] / cap[j];
carga[j] %= cap[j];
}
}
cout << ciclo_total << endl;
return 0;
}
E. Epidemic Escape
Um ponto se move ao longo de um raio enquanto $n$ círculos crescem. Queremos o instante em que o ponto é coberto por pelo menos $k$ círculos.
A condição de cobertura pode ser transformada geometricamente: para um ponto $(r, \alpha)$ em coordenadas polares e um raio com ângulo $\theta$, o tempo de contato é $T = \frac{r}{2 \cos(\alpha - \theta)}$. Queremos o $k$-ésimo menor valor positivo de $T$, o que equivale ao $k$-ésimo maior valor de $1/T$. Isso se reduz a maximizar um produto escalar. Construímos $k$ camadas de Casco Convexo (Convex Hull) e consultamos os pontos extremos em cada camada.
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
struct Ponto { ld x, y; };
ld produto_escalar(Ponto a, ld c, ld s) { return a.x * c + a.y * s; }
int main() {
int n; cin >> n;
vector<Ponto> pts(n);
for (int i = 0; i < n; i++) {
long long xi, yi; cin >> xi >> yi;
ld d2 = (ld)xi * xi + (ld)yi * yi;
pts[i] = {2.0l * xi / d2, 2.0l * yi / d2};
}
// Simplificação: apenas a lógica de busca do k-ésimo maior via Casco Convexo
int q; cin >> q;
while(q--) {
int qx, qy, k; cin >> qx >> qy >> k;
if(qx == 0 && qy == 0) { cout << -1 << endl; continue; }
ld ang = sqrtl((ld)qx * qx + (ld)qy * qy);
ld cos_t = qx / ang, sin_t = qy / ang;
// Busca nos Cascos Convexos pré-calculados...
}
return 0;
}
B. Balanced Permutations
Uma permutação é equilibrada se o número de subsegmentos onde o máximo está nas extremidades for minimizado. Isso ocorre quando a Árvore Cartesiana da permutação é o mais balanceada possível.
Para encontrar a $k$-ésima menor e $l$-ésima maior permutação, usamos uma estratégia híbrida: para $n$ grande, as permutas equilibradas são aubndantes e a estrutura é rígida; para $n$ pequeno (ex: $n \le 50$), usamos Programação Dinâmica com contagem de estados e busca gulosa (bit-by-bit greedy) para determinar cada posição da permutação respeitando as restrições de balanceamento da árvore.
#include <bits/stdc++.h>
using namespace std;
// A implementação envolve DP de contagem e verificação de balanceamento
// da árvore cartesiana para manter a profundidade mínima.
// O código abaixo esboça a estrutura de controle principal.
int main() {
long long n, k, l;
if(!(cin >> n >> k >> l)) return 0;
// Pré-calcula tamanhos de subárvores e limites de balanceamento
// Executa busca gulosa para k-ésima menor
// Executa busca gulosa para l-ésima maior
return 0;
}