Supongamos que nos dan un arreglo de enteros \(a\) con tamaño \(n\) y nos piden hallar la cantidad de subarreglos de \(a\) tales que la suma de sus elementos es un múltiplo de \(m\).
Usando fuerza bruta podríamos obtener un mínimo de \(O(n^{2})\) para generar todos los arreglos que empiecen o terminen en una posición fijada.
Claramente, \(O(n^{2})\) es demasiado tiempo para \(n = 10^{5}\), por lo que debemos buscar una alternativa.
Dado que un subarreglo es el sufijo de un prefijo, podemos decir que la suma de los elementos de un subarreglo es la diferencia de dos prefijos, de esta manera definimos los prefijos:
\[ prefix_{0} = 0 \] \[ prefix_{i} = a_{i} + prefix_{i-1}, i > 0 \]
Gracias a la forma anterior, podemos decir que la suma de los elementos del subarreglo \([l, r]\) es \(prefix_{r} - prefix_{l - 1}\).
Ahora, ya que la suma debe ser múltiplo de \(m\), tendremos que:
\[ prefix_{r} - prefix_{l - 1} \equiv 0 \mod m \]
\[ prefix_{r} \equiv prefix_{l - 1} \mod m \]
Por lo que si fijamos el límite superior \(r\) y mantenemos las frecuencias de todos los resultados de \(prefix_{i} \mod m\) para todos los \(0 \leq i < r\), podremos obtener todos los subarreglos en \(O(n\log{n})\) si el módulo es tan grande que se deben guardar los resultados en un map (se puede obtener \(O(n)\) con alta probabilidad usando unordered_map).
Una implementación sería así:
#include<bits/stdc++.h>
using namespace::std;
int main(){
int n;
scanf("%d", &n);
vector<int> a(n + 1, 0);
vector<int> prefix(n + 1, 0);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
prefix[i] = (prefix[i-1] + a[i]) % m;
}
map<int,int> F;
F[prefix[0]] += 1;
long long ans = 0LL;
for(int i=1; i<=n; i++){
ans += F[prefix[i]];
F[prefix[i]] += 1;
}
cout << ans << endl;
return 0;
}Siempre es útil tener este tipo de planteamientos cuando nos piden hallar propiedades de subarreglos.
El problema anterior fue muy fácil, así que piensen este reto:
Veamos un problema relacionado con el anterior. Dado un arreglo de enteros \(a\) con tamaño \(n\), determinar la máxima suma de entre todos sus subarreglos.
Notemos que, al igual que el problema anterior, podemos obtener una solución \(O(n^{2})\) generando todos los subarreglos.
Sin embargo, si planteamos este problema similar al anterior, tendremos fijo un \(r\) y queremos:
\[ \max\limits_{l \leq r}{\{prefix_{r} - prefix_{l - 1}\}} \]
Ya que \(l \leq r\) entonces \(l - 1 < r\), así que podemos decir \(l' = l - 1\) y buscaremos:
\[ \max\limits_{l' < r}{\{prefix_{r} - prefix_{l'}\}} = prefix_{r} + \max\limits_{l' < r}{\{- prefix_{l'}\}} \]
Pero el máximo de \(-x\) es el negativo del mínimo de \(x\), así que:
\[ \max\limits_{l' < r}{\{prefix_{r} - prefix_{l'}\}} = prefix_{r} - \min\limits_{l' < r}{\{ prefix_{l'}\}} \]
Por lo que nos basta saber cuál es el mínimo prefijo antes de \(r\) y ese será el óptimo, esto lo podemos obtener y mantener en \(O(1)\), así que nuestra solución será \(O(n)\):
#include<bits/stdc++.h>
using namespace::std;
int main(){
int n;
scanf("%d", &n);
vector<int> a(n + 1, 0);
vector<long long> prefix(n + 1, 0LL);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
prefix[i] = prefix[i-1] + a[i];
}
long long ans = LLONG_MIN; // 0 si es válido el subarreglo vacio
long long minimo = 0LL;
for(int i=1; i<=n; i++){
ans = max(ans, prefix[i] - minimo);
minimo = min(minimo, prefix[i]);
}
cout << ans << endl;
return 0;
}Otra forma de analizar el problema también considera fijar el final del subarreglo, pero lo usaremos de otra manera:
Definimos:
Entonces, tenemos solo dos opciones:
\(memo_{i} = a_{i}\), pues ese elemento solo es el máximo subarreglo
\(memo_{i} = a_{l} + a_{l+1} + \ldots + a_{i}\), pues existe un \(l < i\) tal que el subarreglo \([l, i]\) es el máximo.
Notemos que "Para que el elemento \(l\) sea tomado hacia la izquierda de \(i\), primero deberemos tomar el \((i - 1)\)", por lo que analizamos:
\[ X_{i-1} = a_{l} + a_{l+1} + \ldots + a_{i-1}, \text{ para algun }l < i \]
Y para que \(X_{i - 1} + a_{i}\) sea máximo, ya que \(a_{i}\) es constante para \(i\), se debe dar que \(X_{i - 1}\) debe ser máximo.
Ya que \(X_{i - 1}\) es una "un subarreglo que termina en \((i - 1)\) y que debe ser máximo", claramente \(X_{i - 1} = memo_{i - 1}\), así que las segunda opción se vuelve:
Comparando las dos expresiones, tenemos que:
\[ memo_{i} = \max{\{a_{i}, a_{i} + memo_{i - 1}\}} = a_{i} + \max{\{0, memo_{i-1}\}} \]
Y de esta manera podemos obtener el resultado total en \(O(n)\).
Analicemos el siguiente problema:
Dada una barra de longitud \(l\) y una tabla de precios \(p_{i}\) de manera que \(p_{i}\) es la ganancia obtenida al vender una pieza de longitud \(i\). Si es posible realizar la cantidad de cortes enteros que uno desee, determine la máxima ganancia posible.
Una solución con fuerza bruta nos daría una complejidad de \(O(2^{l-1})\), ya que hay \(l - 1\) puntos para hacer los cortes y en cada uno tenemos dos opciones: cortar o no cortar en dicho punto.
Deberemos plantear algunas observaciones:
Definimos \(memo_{i}\) como una función que nos dará la ganancia máxima usando una barra de longitud \(i\). Nuestra respuesta será \(memo_{l}\).
\(l\) se deberá expresar como una suma de cortes \(r_{i}\), es decir \(l = r_{1} + r_{2} + \ldots + r_{k}\).
La ganancia obtenida será \(\sum\limits_{i = 1}^{k}p_{r_{i}}\) en tal caso.
Si fijamos el resultado de alguno de los cortes (por simplicidad, \(r_{1}\)), tendremos una longitud restante de \(l - r_{1}\), la cual deberá ser distribuida de manera óptima también, pues:
\[ memo_{l} = \max\limits_{0 < r_{1} \leq l}{\{p_{r_{1}} + f(l - r_{1})\}} \]
Pero ya que \(f(l - r_{1})\) debe obtener la máxima ganancia usando una barra de longitud \(l - r_{1}\), esta función debe dar el mismo resultado que \(memo_{l - r_{1}}\):
\[ memo_{l} = \max\limits_{0 < r_{1} \leq l}{\{p_{r_{1}} + memo_{l - r_{1}}\}} \]
Y si llenamos los resultados en un arreglo \(memo[l]\) por \(l\) ascendente, obtendremos un algoritmo \(O(l^{2})\):
#include<bits/stdc++.h>
using namespace::std;
int main(){
int l;
scanf("%d", &l);
vector<int> p(l + 1, 0); // p_{0} = 0
vector<long long> memo(l + 1, 0LL); // memo_{0} = 0, los demás se asignaran la primera vez
for(int i=1; i<=l; i++){
scanf("%d", &p[i]);
memo[i] = p[i]; // caso r_{1} = i
for(int r_1=1; r_1<i; r_1++){
memo[i] = max(memo[i], p[r_1] + memo[i - r_1]);
}
}
cout << memo[l] << endl;
return 0;
}Pueden entrar al contest mediante el siguiente link