Para resolver este problema basta separar algunos casos:
\(a = b\), entonces la respuesta es 0.
\(a < b\), entonces si \(b - a\) es impar, la respuesta es 1; en caso contrario, es 2 (sumamos (b - a - 1) y luego 1).
\(a > b\), entonces si \(a - b\) es par, la respuesta es 1; en caso contrario, es 2 (restamos \(a - b + 1\) y luego sumamos \(1\)).
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
int a, b;
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d %d", &a, &b);
if(a == b) puts("0");
else{
if(a < b) puts((a & 1)^(b & 1)? "1" : "2");
else puts((a & 1)^(b & 1)? "2" : "1");
}
}
return 0;
}Para este problema basta con considerar los subarreglos de tamaño \(L\) y considerar su aporte a la respuesta:
Supongamos que hemos fijado \(l\) y \(r = l + L - 1\), entonces notamos que si deseamos que un subarreglo de mi permutación aporte, necesitamos que exista un subarreglo de tamaño \(L\) tal que contenga a \(l\) como mínimo y a \(r\) como máximo.
Observación 1: Solamente se puede dar lo anterior cuando el subarreglo contiene todos los elementos en el rango \([l, r]\).
Observación 2: La cantidad de veces que se puede dar este caso en una permutación fijada es:
\[ (\text{Posiciones posibles}) \cdot (\text{Formas de reordenar los L elementos}) \cdot (\text{Formas de reordenar el resto de elementos}) \]
Entonces, notamos que \(\text{Posiciones posibles} = n - L + 1\), \(\text{Formas de reordenar los L elementos} = L!\) y \(\text{Formas de reordenar el resto de elementos} = (n - L)!\).
Ahora, esto lo hemos hecho fijando en \(L\) y el \(l\), pero fijar ambos valores nos daría una complejidad de \(O(n^{2})\). Entonces notamos que la expresión no depende de \(l\), sino de \(L\), así que la respuesta parcial será multiplicar la cantidad de formas de elegir \(l\) a la expresión anterior. La cantidad de formas de elegir \(l\) también es \((n - L + 1)\), así que:
\[ aporte(L) = (n - L + 1)^{2} \cdot L! \cdot (n - L)! \]
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
const int N = 250000+5;
int n, MOD;
int f[N];
int add(int a, int b, int m = MOD){
return (a + b) % m;
}
int mul(long long a, long long b, int m = MOD){
return (a * b) % m;
}
void init(){
f[0] = 1;
for(int i = 1; i <= n; i++) f[i] = mul(f[i-1], i);
}
int solve(int L){
return mul(mul(n - L + 1, n - L + 1), mul(f[L], f[n - L]));
}
int main(){
scanf("%d %d", &n, &MOD);
init();
int ans = 0;
for(int L = 1; L <= n; L++){
ans = add(ans, solve(L));
}
printf("%d\n", ans);
return 0;
}Una de las estrategias óptimas en este problema es ubicar un nodo \(a\) con la mayor cantidad de filas de información en alguno de los clúster, luego mover toda la información del cluster al que no pertenece \(a\) hacia \(a\). Luego de esto basta intentar para el resto de nodos del clúster de \(a\) la mejor de dos opciones: Mover toda la información del otro cluster a esa posición o mover la información del nodo actual al \(a\).
Código (por racsosabe, idea por Fischer)
#include<bits/stdc++.h>
using namespace::std;
const int N = 100000+5;
typedef long long ll;
int n;
int m;
int a[N];
int b[N];
long long solve(){
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + m);
ll sumA = accumulate(a + 1, a + 1 + n, 0LL);
ll sumB = accumulate(b + 1, b + 1 + m, 0LL);
ll ansA = sumB, ansB = sumA;
for(int i = 1; i < n; i++){
ansA += min(1LL * a[i], sumB);
}
for(int i = 1; i < m; i++){
ansB += min(1LL * b[i], sumA);
}
return min(ansA, ansB);
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", a+i);
for(int i = 1; i <= m; i++) scanf("%d", b+i);
printf("%lld\n", solve());
return 0;
}Para resolver el problema basta con implementar según el enunciado.
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
int n, a, b;
int main(){
scanf("%d %d %d", &n, &a, &b);
int ans = 0;
int c = 0;
for(int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
if(x == 1){
if(a == 0){
if(b == 0){
if(c == 0) ans += 1;
else{
c -= 1;
}
}
else{
b -= 1;
c += 1;
}
}
else a -= 1;
}
else{
if(b == 0) ans += 2;
else b -= 1;
}
}
printf("%d\n", ans);
return 0;
}Para resolver este problema bastaba simular usando two pointers y siempre darle prioridad al que coma primero o, si hay empate, a Alice.
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
const int N = 100000+5;
int n;
int a[N];
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", a+i);
}
int cL = 0, cR = 0;
int L = 1, R = n;
int tL = 0, tR = 0;
while(L <= R){
if(tL <= tR){
cL += 1;
tL += a[L];
L += 1;
}
else{
cR += 1;
tR += a[R];
R -= 1;
}
}
printf("%d %d\n", cL, cR);
return 0;
}Para resolver este problema basta con modelarlo como un grafo dirigido (posibles multiaristas) de residuos \(G = (V, E)\) definido de la siguiente forma:
\[ V = \{0, 1, \ldots, x-1\} \]
\[ E = \{(u, v) \text{ existe una vez por cada }a_{i} \text{ tal que }10u + a_{i} \equiv v \mod x\} \]
Entonces, lo que se busca sobre este grafo es la cantidad de caminos de longitud \(b\) desde el nodo \(0\) al nodo \(k\). Esto se puede calcular con exponenciación rápida de matrices, considerando la matriz de adyacencia ponderada definida como:
\[ M_{ij} = \text{Cantidad de aristas }(i, j)\text{ en E} \]
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
const int N = 100+5;
const int MOD = 1000000000+7;
int add(int a, int b, int m = MOD){
return (a + b) % m;
}
int mul(long long a, long long b, int m = MOD){
return (a * b) % m;
}
int n, b, k, x;
int M[N][N];
int C[N][N];
int R[N][N];
int frec[N];
void multiply(int type){
for(int i = 0; i < x; i++){
for(int j = 0; j < x; j++){
C[i][j] = 0;
for(int p = 0; p < x; p++){
if(type == 1){
C[i][j] = add(C[i][j], mul(M[i][p], R[p][j]));
}
else{
C[i][j] = add(C[i][j], mul(M[i][p], M[p][j]));
}
}
}
}
for(int i = 0; i < x; i++){
for(int j = 0; j < x; j++){
if(type == 1) R[i][j] = C[i][j];
else M[i][j] = C[i][j];
}
}
}
void fastexp(int e){
while(e > 0){
if(e & 1) multiply(1);
multiply(0);
e >>= 1;
}
}
int main(){
scanf("%d %d %d %d", &n, &b, &k, &x);
for(int i = 1; i <= n; i++){
int d;
scanf("%d", &d);
frec[d] += 1;
}
for(int r1 = 0; r1 < x; r1++){
for(int d = 1; d < 10; d++){
int r3 = add(mul(r1, 10, x), d, x);
M[r1][r3] += frec[d];
}
}
for(int i = 0; i < x; i++){
for(int j = 0; j < x; j++){
R[i][j] = i == j;
}
}
fastexp(b);
printf("%d\n", R[0][k]);
return 0;
}Para resolver este problema debemos usar una pista que nos da el enunciado: Al iniciar el procedimiento, se elige un nodo como centro y desde ahí se desprenden el resto de los hedgehog.
Observación clave: El centro del hedgehog es el centro del árbol, ya que por la forma de construcción siempre se crean nuevas hojas tomándolo como referencia, así que todas estas están en el mismo nivel.
Gracias a la observación clave nos basta hallar el centro del árbol, con lo que hay dos casos:
Hay un solo centro: Podemos mandar un DFS para verificar que cumpla con la estructura.
Hay dos centros: No es posible, ya que solo debe haber 1 para que cumpla.
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
const int N = 100000+5;
int n, k;
int h[N];
int deg[N];
int sum[N];
bool vis[N];
vector<int> G[N];
bool DFS(int u, int depth, int p = -1){
if(depth == 0) return G[u].size() == 1;
int deg = 0;
bool ans = true;
for(int v : G[u]){
if(v == p) continue;
if(!DFS(v, depth - 1, u)) ans = false;
deg += 1;
}
return deg >= 3 and ans;
}
bool solve(){
vector<int> frontier;
int cnt = n;
for(int i = 1; i <= n; i++){
h[i] = n;
if(deg[i] == 1){
deg[i] = 0;
h[i] = 0;
vis[i] = true;
frontier.emplace_back(i);
}
}
while(!frontier.empty() and cnt >= 2){
vector<int> new_frontier;
for(auto x : frontier){
cnt -= 1;
for(int v : G[x]){
if(vis[v]) continue;
deg[v] -= 1;
if(deg[v] == 1){
vis[v] = true;
new_frontier.emplace_back(v);
deg[v] = 0;
}
}
}
swap(frontier, new_frontier);
}
if(cnt == 0) return false;
if(frontier.empty()) return false;
return DFS(frontier.back(), k);
}
int main(){
scanf("%d %d", &n, &k);
for(int i = 1; i < n; i++){
int u, v;
scanf("%d %d", &u, &v);
G[u].emplace_back(v);
G[v].emplace_back(u);
deg[v] += 1;
deg[u] += 1;
}
puts(solve()?"Yes":"No");
return 0;
}Para resolver este problema bastaba notar que la elección de las dos dimensiones es independiente, así que podemos hallar la cantidad de formas de realizar \(k\) movimientos sobre una base de tamaño \(n\) y la cantidad de formas con una base \(m\) y multiplicar dicho valor.
Entonces, ¿Cómo hallamos la cantidad de formas de realizar \(k\) movimientos sobre una base de tamaño \(n\)? Podemos definir la siguiente función:
\[ memo[k][n] = \text{Cantidad de formas de realizar k movimientos sobre una base de tamaño n} \]
Ahora, podemos fijar el primer movimiento para obtener la base nueva y contar su aporte:
\[ memo[k][n] = \sum\limits_{1 \leq l \leq n - 2}Aporte(n, l, k) \]
Sin embargo, notamos que la función \(Aporte(n, l, k)\) depende de la cantidad de posiciones que pueda tomar \(l\) sobre la base \(n\) cumpliendo las reglas y la cantidad de formas de realizar \(k - 1\) movimientos con una base de tamaño \(l\):
\[ Aporte(n, l, k) = memo[k-1][l] \cdot (n - 1 - l) \]
Entonces si reemplazamos:
\[ memo[k][n] = \sum\limits_{1 \leq l \leq n - 2}memo[k-1][l] \cdot (n - 1 - l) \]
\[ memo[k][n] = (n - 1)\sum\limits_{1 \leq l \leq n - 2}memo[k-1][l] - \sum\limits_{1 \leq l \leq n - 2}l\cdot memo[k-1][l] \]
Ahora, si preprocesamos en \(O(n)\) los resultados de la suma de \(\sum\limits_{1 \leq l \leq n - 2}memo[k-1][l]\) y \(\sum\limits_{1 \leq l \leq n - 2}l\cdot memo[k-1][l]\) por separado en arreglos \(suma[k-1][n-2]\) y \(sump[k-1][n-2]\) respectivamente, tendremos:
\[ memo[k][n] = (n-1)\cdot suma[k-1][n-2] - sump[k-1][n-2] \]
Y así podremos resolver el problema en \(O(n^{2})\).
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
const int N = 1000+5;
const int MOD = 1000000000+7;
int add(int a, int b, int m = MOD){
return (a + b) % m;
}
int mul(long long a, long long b, int m = MOD){
return (a * b) % m;
}
int n, m, k;
int memo[N][N];
int suma[N][N];
int sump[N][N];
void get(int r, int limit){
for(int i = 1; i <= limit; i++){
suma[r][i] = add(suma[r][i-1], memo[r][i]);
sump[r][i] = add(sump[r][i-1], mul(i, memo[r][i]));
}
}
void init(int limit){
for(int i = 1; i <= limit; i++) memo[0][i] = 1;
for(int i = 1; i <= k; i++){
get(i - 1, limit);
for(int l = 1; l <= limit; l++){
memo[i][l] = add(mul(l - 1, suma[i-1][l-2]), MOD - sump[i-1][l-2]);
}
}
}
int main(){
scanf("%d %d %d", &n, &m, &k);
init(max(n, m));
printf("%d\n", mul(memo[k][n], memo[k][m]));
return 0;
}Para resolver este problema basta con separar algunos casos posibles:
Si la suma ya es impar, la respuesta es "YES".
Si la suma es par, necesitamos poder cambiar la paridad de alguno de los elementos, así que la respuesta es "YES" solo si hay al menos 1 elemento par y 1 impar a la vez.
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
int n;
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
int sum = 0;
int odd = 0, even = 0;
for(int i=1; i<=n; i++){
int x;
scanf("%d", &x);
sum = (sum + x) % 2;
if(x & 1) odd += 1;
else even += 1;
}
if(sum) puts("YES");
else{
puts(odd and even? "YES":"NO");
}
}
return 0;
}Para resolver este problema bastaba notar que el costo de memoria por cada cliente era fijo, así que podíamos ordenar los clientes por costo ascendente e ir tomando pedidos hasta que ya no nos alcance la memoria.
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
const int N = 100000+5;
int n, d;
int a, b;
long long c[N];
int main(){
scanf("%d %d", &n, &d);
scanf("%d %d", &a, &b);
for(int i = 1; i <= n; i++){
int x, y;
scanf("%d %d", &x, &y);
c[i] = 1LL * x * a + 1LL * y * b;
}
vector<int> p(n);
iota(p.begin(), p.end(), 1);
sort(p.begin(), p.end(), [&] (int i, int j){
return c[i] < c[j];
});
vector<int> ans;
for(int i : p){
if(d >= c[i]){
ans.emplace_back(i);
d -= c[i];
}
}
printf("%d\n", (int)ans.size());
for(int i = 0; i < ans.size(); i++){
printf("%d%c", ans[i], " \n"[i + 1 == ans.size()]);
}
return 0;
}Para resolver este problema debemos notar que la estructura de la cadena \(b\) es la siguiente:
\[ b = a_{1} a_{2} a_{2} a_{3} a_{3} \ldots a_{n-2} a_{n-1} a_{n-1} a_{n} \]
De manera que nuestra cadena \(a\) se puede obtener con el siguiente procedimiento:
Imprimos \(b_{1}\)
Iteramos sobre las posiciones pares (o impares) en el rango \([2, |b|-1]\), donde |b| es la longitud de \(b\).
Imprimimos \(b_{|b|}\).
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
const int N = 100+5;
int n;
char s[N];
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%s", s);
n = strlen(s);
putchar(s[0]);
for(int i = 1; i + 1 < n; i += 2){
putchar(s[i]);
}
putchar(s[n-1]);
putchar('\n');
}
return 0;
}Para resolver este problema bastaba reducir la respuesta a hallar dos caminos de \((0, 0)\) a \((n-1, n-1)\) tal que contemos una sola vez cada elemento en la suma.
Entonces, podemos plantear el tener 2 caminos que actualmente estén en las posiciones \((x_{1}, y_{1})\) y \((x_{2}, y_{2})\) y que se cumpla que \((x_{1}, y_{1}) \leq (x_{2}, y_{2})\) por comparación lexicográfica (de manera que los caminos no se crucen estrictamente pero si puedan encontrarse en puntos en común).
Esto nos da una solución \(O(n^{4})\) con \(O(n^{4})\) de memoria, lo cual no nos basta. Sin embargo, ya que nuestro camino es monótono, tendremos que \(x + y = pasos\) en todo momento, así que si tenemos una de las coordenadas y el número de pasos realizados, podemos deducir la coordenada faltante.
Una opción sería tener un DP con parámetros \((pasos, x_{1}, x_{2})\), pero esto requeriría \((2 (n-1)\cdot(n-1)\cdot(n-1))\) de memoria, lo cual puede darnos problemas con el ML, así que llevaremos los parámetros \((x_{1}, y_{1}, x_{2})\), ya que podemos deducir \(pasos = x_{1} + y_{1}\).
Ya que tenemos nuestro DP definido, podemos simular las elecciones y maximizar la suma de las celdas visitadas sin contar doble.
Código (por racsosabe)
#include<bits/stdc++.h>
using namespace::std;
const int N = 300+5;
const int inf = 1<<29;
int n;
int a[N][N];
bool vis[N][N][N];
int memo[N][N][N];
int dx[] = {1, 0};
int dy[] = {0, 1};
bool validPos(int x, int y){
return x >= 0 and y >= 0 and x < n and y < n;
}
int DP(int x1, int y1, int x2){
int diag = x1 + y1;
int y2 = diag - x2;
if(diag == 2 * (n - 1)) return a[x1][y1];
if(vis[x1][y1][x2]) return memo[x1][y1][x2];
int ans = -inf;
for(int i = 0; i < 2; i++){
int vx1 = x1 + dx[i];
int vy1 = y1 + dy[i];
if(!validPos(vx1, vy1)) continue;
for(int j = 0; j < 2; j++){
int vx2 = x2 + dx[j];
int vy2 = y2 + dy[j];
if(!validPos(vx2, vy2)) continue;
if(make_pair(vx1, vy1) <= make_pair(vx2, vy2)){
int cur = (x1 == x2 and y1 == y2? a[x1][y1] : a[x1][y1] + a[x2][y2]) + DP(vx1, vy1, vx2);
if(ans < cur) ans = cur;
}
}
}
vis[x1][y1][x2] = true;
return memo[x1][y1][x2] = ans;
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
scanf("%d", &a[i][j]);
}
}
printf("%d\n", DP(0,0,0));
return 0;
}