Aquí se presentan soluciones a varios problemas de la edición Open 2021 del concurso USACO, con explicaciones breves y código reescrito para mejorar la legibilidad y variar la implementación original.
Problema G1 – USACO 2021 Open Gold
Enfoque: Para cada posición i se almacena anterior[i], el índice del elemento igual más cercano hacia la izquierda. Para cada r, los intervalos válidos son [anterior[r]+1, r-2]. Se usa un árbol de segmentos que manteine la suma de posiciones disponibles. Al procesar r, se elimina la posición anterior[r] del árbol (ya no puede ser inicio de un intervalo válido) y se añade la posición r. Complejidad O(n log n).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200000;
struct SegTree {
vector<ll> sum;
SegTree() : sum(4 * N + 10, 0) {}
void upd(int p, int l, int r, int idx, int v) {
if (l == r) { sum[p] += v; return; }
int m = (l + r) >> 1;
if (idx <= m) upd(p*2, l, m, idx, v);
else upd(p*2+1, m+1, r, idx, v);
sum[p] = sum[p*2] + sum[p*2+1];
}
ll qry(int p, int l, int r, int ql, int qr) {
if (ql > qr) return 0;
if (ql <= l && r <= qr) return sum[p];
int m = (l + r) >> 1; ll ans = 0;
if (ql <= m) ans += qry(p*2, l, m, ql, qr);
if (qr > m) ans += qry(p*2+1, m+1, r, ql, qr);
return ans;
}
} st;
int n, a[N+5], prevIdx[N+5], last[N+5];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
prevIdx[i] = last[a[i]];
last[a[i]] = i;
}
ll ans = 0;
st.upd(1, 0, n, 0, 1);
for (int i = 1; i <= n; ++i) {
ans += st.qry(1, 0, n, prevIdx[i], i-2);
st.upd(1, 0, n, i, 1);
if (prevIdx[i]) st.upd(1, 0, n, prevIdx[i]-1, -1);
}
cout << ans << '\n';
return 0;
}
Problema G2 – USACO 2021 Open Gold
Enfoque: Cada punto se divide en 4 nodos (uno por cada portal). Se conectan los nodos que corresponden a portales del mismo número, y también se conectan los nodos que representan celdas adyacentes. El grafo resultante se compone de componentes conectados. Cada operación permite unir dos componentes con costo ci, y el problema se reduce a encontrar el árbol de expansión mínima. Algoritmo: calcular los componentes con DFS, luego ordenar las aristas (con costo ci) y aplicar Kruskall. Complejidad O(n log n).
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int n, c[N+5], t[N+5][5];
vector<int> adj[N*4+5], posList[N*2+5];
int comp[N*4+5], totalComp = 0;
struct Edge { int u, v, w; };
vector<Edge> edges;
void dfs(int u, int id) {
comp[u] = id;
for (int v : adj[u])
if (!comp[v]) dfs(v, id);
}
int parent[N+5];
int find(int x) { return (parent[x] == x) ? x : parent[x] = find(parent[x]); }
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> c[i];
int base = (i-1)*4;
adj[base].push_back(base+1);
adj[base+1].push_back(base);
adj[base+2].push_back(base+3);
adj[base+3].push_back(base+2);
for (int j = 0; j < 4; ++j) {
cin >> t[i][j];
posList[t[i][j]].push_back(base + j);
}
}
for (int i = 1; i <= 2*n; ++i) {
int a = posList[i][0], b = posList[i][1];
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 0; i < 4*n; ++i)
if (!comp[i]) dfs(i, ++totalComp);
for (int i = 1; i <= n; ++i) {
int a = comp[(i-1)*4], b = comp[(i-1)*4+2];
if (a != b) edges.push_back({a, b, c[i]});
}
sort(edges.begin(), edges.end(), [](Edge &x, Edge &y) { return x.w < y.w; });
for (int i = 1; i <= totalComp; ++i) parent[i] = i;
long long ans = 0;
for (auto &e : edges) {
int u = find(e.u), v = find(e.v);
if (u != v) {
ans += e.w;
parent[u] = v;
}
}
cout << ans << '\n';
return 0;
}
Problema G3 – USACO 2021 Open Gold
Enfoque: La cáscara convexa final siempre es un triángulo. Se define DP recursivo f(a,b,c,k) que cuenta la cantidad de formas de seleccionar exactamente k puntos de los que están dentro del triángulo abc, con el orden de los puntos elegidos determinado por su inclusión en subtriángulos. La idea es partir del triángulo máximo que contiene todos los puntos y explorar todas las posibles inclusiones. La implementación utiliza memoización y combinaciones precalculadas. Complejidad aparentemente alta pero suficiente para n ≤ 50.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int N = 50;
const double PI = acos(-1), EPS = 1e-8;
int n, x[N+5], y[N+5];
int inside[N+5][N+5][N+5];
int dp[N+5][N+5][N+5][N+5];
bool visited[N+5][N+5][N+5];
long long fact[N+5], C[N+5][N+5];
double angle(int a, int b, int c) {
double dx1 = x[b]-x[a], dy1 = y[b]-y[a];
double dx2 = x[c]-x[a], dy2 = y[c]-y[a];
double dot = dx1*dx2 + dy1*dy2;
double len1 = sqrt(dx1*dx1+dy1*dy1);
double len2 = sqrt(dx2*dx2+dy2*dy2);
return acos(dot/(len1*len2));
}
bool insideTriangle(int a, int b, int c, int p) {
double sum = angle(p, a, b) + angle(p, b, c) + angle(p, c, a);
return fabs(sum - 2*PI) < EPS;
}
void compute(int a, int b, int c) {
if (visited[a][b][c]) return;
visited[a][b][c] = true;
int cnt = inside[a][b][c];
for (int i = 0; i <= cnt; ++i)
dp[a][b][c][i] = (6LL * C[cnt][i] % MOD) * fact[cnt-i] % MOD;
int tri[3];
for (int p = 1; p <= n; ++p) {
if (p == a || p == b || p == c) continue;
if (!insideTriangle(a, b, c, p)) continue;
tri[0]=a; tri[1]=b; tri[2]=p; sort(tri, tri+3);
compute(tri[0], tri[1], tri[2]);
int subCnt = inside[tri[0]][tri[1]][tri[2]];
int outer = cnt - subCnt - 1;
for (int q = 0; q <= outer; ++q)
for (int w = 0; w <= subCnt; ++w)
for (int t = 0; t <= w; ++t)
dp[a][b][c][q+t] = (dp[a][b][c][q+t] +
1LL * dp[tri[0]][tri[1]][tri[2]][w] *
fact[outer - q + w - t] % MOD *
C[outer][q] % MOD * C[w][t] % MOD) % MOD;
tri[0]=a; tri[1]=c; tri[2]=p; sort(tri, tri+3);
compute(tri[0], tri[1], tri[2]);
subCnt = inside[tri[0]][tri[1]][tri[2]];
outer = cnt - subCnt - 1;
for (int q = 0; q <= outer; ++q)
for (int w = 0; w <= subCnt; ++w)
for (int t = 0; t <= w; ++t)
dp[a][b][c][q+t] = (dp[a][b][c][q+t] +
1LL * dp[tri[0]][tri[1]][tri[2]][w] *
fact[outer - q + w - t] % MOD *
C[outer][q] % MOD * C[w][t] % MOD) % MOD;
tri[0]=b; tri[1]=c; tri[2]=p; sort(tri, tri+3);
compute(tri[0], tri[1], tri[2]);
subCnt = inside[tri[0]][tri[1]][tri[2]];
outer = cnt - subCnt - 1;
for (int q = 0; q <= outer; ++q)
for (int w = 0; w <= subCnt; ++w)
for (int t = 0; t <= w; ++t)
dp[a][b][c][q+t] = (dp[a][b][c][q+t] +
1LL * dp[tri[0]][tri[1]][tri[2]][w] *
fact[outer - q + w - t] % MOD *
C[outer][q] % MOD * C[w][t] % MOD) % MOD;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
fact[0] = 1;
for (int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i % MOD;
C[0][0] = 1;
for (int i = 1; i <= N; ++i) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
}
for (int i = 1; i <= n; ++i)
for (int j = i+1; j <= n; ++j)
for (int k = j+1; k <= n; ++k)
for (int p = 1; p <= n; ++p)
if (p != i && p != j && p != k && insideTriangle(i, j, k, p))
inside[i][j][k]++;
for (int i = 1; i <= n; ++i)
for (int j = i+1; j <= n; ++j)
for (int k = j+1; k <= n; ++k)
if (inside[i][j][k] == n-3) {
compute(i, j, k);
cout << dp[i][j][k][0] << '\n';
return 0;
}
cout << 0 << '\n';
return 0;
}
Problema P1 – USACO 2021 Open Platinum
Enfoque: Versión extendida del problema Gold G1. Ahora cada líder diferente cuenta como una forma distinta. Se mantiene un árbol de segmentos con lazy propagation que registra el número de formas para cada posición. Al procesar i, se añaden contribuciones del intervalo [anterior[i]+1, i-2]. Luego se realizan dos actualizaciones: se resta 1 en el intervalo [anterior[anterior[i]]+1, anterior[i]-1] (porque esas posiciones ya no pueden ser iniciadas por i como líder), y se suma 1 en [anterior[i]+1, i-1] (para marcar que sí pueden). Además, se elimina la posición anterior[i] del árbol (prohibición). Complejidad O(n log n).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200000;
struct SegTree {
vector<ll> sum;
vector<int> lazy, banned;
int n;
SegTree(int n) : n(n), sum(4*n+10, 0), lazy(4*n+10, 0), banned(4*n+10, 0) {}
void build(int p, int l, int r) {
if (l == r) return;
int m = (l+r)>>1;
build(p*2, l, m); build(p*2+1, m+1, r);
banned[p] = banned[p*2] + banned[p*2+1];
}
void push(int p, int l, int r) {
if (lazy[p] == 0) return;
int m = (l+r)>>1;
apply(p*2, l, m, lazy[p]);
apply(p*2+1, m+1, r, lazy[p]);
lazy[p] = 0;
}
void apply(int p, int l, int r, int v) {
lazy[p] += v;
sum[p] += 1LL * v * (r-l+1 - banned[p]);
}
void updateAdd(int p, int l, int r, int ql, int qr, int v) {
if (ql > qr || banned[p] == r-l+1) return;
if (ql <= l && r <= qr) {
apply(p, l, r, v);
return;
}
push(p, l, r);
int m = (l+r)>>1;
if (ql <= m) updateAdd(p*2, l, m, ql, qr, v);
if (qr > m) updateAdd(p*2+1, m+1, r, ql, qr, v);
sum[p] = sum[p*2] + sum[p*2+1];
}
void updateBan(int p, int l, int r, int idx) {
if (idx == 0 || banned[p] == r-l+1) return;
if (l == r) {
banned[p] = 1;
sum[p] = 0;
return;
}
push(p, l, r);
int m = (l+r)>>1;
if (idx <= m) updateBan(p*2, l, m, idx);
else updateBan(p*2+1, m+1, r, idx);
banned[p] = banned[p*2] + banned[p*2+1];
sum[p] = sum[p*2] + sum[p*2+1];
}
ll query(int p, int l, int r, int ql, int qr) {
if (ql > qr || banned[p] == r-l+1) return 0;
if (ql <= l && r <= qr) return sum[p];
push(p, l, r);
int m = (l+r)>>1; ll res = 0;
if (ql <= m) res += query(p*2, l, m, ql, qr);
if (qr > m) res += query(p*2+1, m+1, r, ql, qr);
return res;
}
};
int n, a[N+5], prevIdx[N+5], last[N+5];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
prevIdx[i] = last[a[i]];
last[a[i]] = i;
}
SegTree st(n);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans += st.query(1, 1, n, prevIdx[i]+1, i-2);
st.updateAdd(1, 1, n, prevIdx[prevIdx[i]]+1, prevIdx[i]-1, -1);
st.updateAdd(1, 1, n, prevIdx[i]+1, i-1, 1);
st.updateBan(1, 1, n, prevIdx[i]);
}
cout << ans << '\n';
return 0;
}
Problema P3 – USACO 2021 Open Platinum
Enfoque: DP por filas. Se definne f(i, l, r, x, y) con x indicando si el borde izquierdo está expandiéndose (1) o contrayéndose (0), y y análogo para el derecho. La transición utiliza sumas de prefijos bidimensionales para calcular rápidamente las combinaciones de estados de la fila anterior. Se puede implementar en O(n³).
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int N = 150;
int n, pref[N+5][N+5], dp[N+5][N+5][N+5][2][2], sum[N+5][N+5][N+5][2][2];
char grid[N+5][N+5];
long long ans;
void add(int &a, int b) { a = (a + b) % MOD; }
void sub(int &a, int b) { a = (a - b + MOD) % MOD; }
int getSum(int i, int x1, int y1, int x2, int y2, int l, int r) {
int res = sum[i][x2][y2][l][r];
if (x1 > 1) sub(res, sum[i][x1-1][y2][l][r]);
if (y1 > 1) sub(res, sum[i][x2][y1-1][l][r]);
if (x1 > 1 && y1 > 1) add(res, sum[i][x1-1][y1-1][l][r]);
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> (grid[i]+1);
for (int j = 1; j <= n; ++j)
pref[i][j] = pref[i][j-1] + (grid[i][j] == 'G');
}
for (int i = 1; i <= n; ++i) {
for (int l = 1; l <= n; ++l) {
for (int r = l; r <= n; ++r) {
if (pref[i][r] - pref[i][l-1] == r-l+1) {
int cur = getSum(i-1, l, r, l, r, 0, 0);
add(dp[i][l][r][0][0], cur);
add(dp[i][l][r][0][0], 1);
cur = getSum(i-1, 1, l, l, r, 1, 0);
add(dp[i][l][r][1][0], cur);
cur = getSum(i-1, 1, l-1, l, r, 0, 0);
add(dp[i][l][r][1][0], cur);
cur = getSum(i-1, l, r, r, n, 0, 1);
add(dp[i][l][r][0][1], cur);
cur = getSum(i-1, l, r, r+1, n, 0, 0);
add(dp[i][l][r][0][1], cur);
cur = getSum(i-1, 1, l-1, r+1, n, 0, 0);
add(dp[i][l][r][1][1], cur);
cur = getSum(i-1, 1, l, r+1, n, 1, 0);
add(dp[i][l][r][1][1], cur);
cur = getSum(i-1, 1, l-1, r, n, 0, 1);
add(dp[i][l][r][1][1], cur);
cur = getSum(i-1, 1, l, r, n, 1, 1);
add(dp[i][l][r][1][1], cur);
add(ans, dp[i][l][r][0][0]);
add(ans, dp[i][l][r][0][1]);
add(ans, dp[i][l][r][1][0]);
add(ans, dp[i][l][r][1][1]);
}
}
}
// construir sumas de prefijo 2D para la fila i
for (int l = 1; l <= n; ++l)
for (int r = 1; r <= n; ++r)
for (int x = 0; x < 2; ++x)
for (int y = 0; y < 2; ++y) {
add(sum[i][l][r][x][y], dp[i][l][r][x][y]);
add(sum[i][l][r][x][y], sum[i][l-1][r][x][y]);
add(sum[i][l][r][x][y], sum[i][l][r-1][x][y]);
sub(sum[i][l][r][x][y], sum[i][l-1][r-1][x][y]);
}
}
cout << ans << '\n';
return 0;
}
Nota: El problema P2 (Matrix-Tree) queda pendiente.