Paradigmas de programación
Existen 4 grandes paradigmas: busqueda completa, programación dinámica, enfoque condicioso y divide & vencerás. La gran mayoría de los problemas de computer science son solucionables eficientemente con alguna combinación de estos paradigmas, disjunta o no.
Busqueda completa
Este paradigma de busqueda completa se basa, como su nombre lo dice, en realizar una exploración total sobre la estructura de la solución de un problema. Para ello se procede desde enfoques simples como fuerza bruta, algo más refinado como backtracking hasta métodos heurísticos que involucran conceptos de inteligencia artificial.
ejemplo:
sean n enteros, n menor o igual a 1000, en el rango de [-1000, 1000]. verificar que existan 4 números a, b, c, d, no necesariamente distintos, tal que a + b + c = d.
construyendo una solución eficiente
primera solución
Para dar solución a este problema podemos empezar con una idea simple de fuerza bruta llamada fijación. Empezamos fijando los 4 parametros libres tal que podemos tener algo como:
#include <bits/stdc++.h>
using namespace std;
int a[1005];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a+i);
}
bool ok = false;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
for (int l = 1; l <= n; ++l) {
ok = ok | (a[i] + a[j] + a[k] == a[l]);
}}}}
puts(ok ? "YES" : "NO");
return 0;
}
Intuitivamente podemos ver que este algoritmo tiene una complejidad de O(n^4). que se traduce en 10000 segundos maquina.
segunda solución
Ahora podemos incluir el rango de las variables. Como dice el enunciado las variables están en el rango [-1000, 1000], esto es bueno porque puede ser mapeado fácilemente con un array de 2000 elementos, entonces, podriamos reducir la cantidad de variables fijadas a solo 3 y verificar en O(1) que la suma se encuentre.
#include <bits/stdc++.h>
using namespace std;
int a[1005];
bool inSet[2005];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a+i);
inSet[a[i] + 1000] = true;
}
bool ok = false;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
if (a[i] + a[j] + a[k] < -1000 or a[i] + a[j] + a[k] > 1000) {
continue;
}
ok = ok | inSet[a[i] + a[j] + a[k] + 1000];
}}}
puts(ok ? "YES" : "NO");
return 0;
}
Note que usamos un + 1000 al guardar en el vector.
Esta solución es mucho mejor con O(n^3). que seria alrededo de 10 segundos máquina.
Tercera solución
Como último, para este problema podemos manipular sutilmente el enunciado, tal que en vez de pedir si existe a + b + c = d podemos pedir a + b = d - c. esto es muy útil ya que para ambos lados de la igualdad solo tenemos una operación entre dos elementos que solo tiene n^2 posibilidades.
#include <bits/stdc++.h>
using namespace std;
int a[1005];
bool sum[4005];
bool diff[4005];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a+i);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
sum[a[i] + a[j] + 2000] = 1;
diff[a[i] - a[j] + 2000] = 1;
}
}
bool ok = false;
for (int i = 0; i <= 4000; ++i) {
ok = ok | (sum[i] == diff[i]);
}
puts(ok ? "YES" : "NO");
return 0;
}
Esta es una eficiente solución con fuerza bruta que solo toma O(n^2). Note como hemos cambiado memoria por complejidad. Para esto definiremos complejidad de memoria como la mayor cantidad de memoria que usas a la vez en un programa.
Cuarta solución
No implementaremos esta solución, pero esta solución incluye algo más de conocimientos en teoría de números sobretodo funciones generadoras y algo de cálculo complejo. para ello usaremos la función generadora de un dado P(x) tal que tenga n lados y cada uno tenga a[i] puntos. por último la solución consta de revisar que la probabilidad de lanzar un dado 3 veces o una vez den el mismo resultado sea distinta de 0. lanzar un dado 3 veces lo podemos entender como P(x)^3. Luego necesitamos saber que para dos polinomios la conv(P x Q) = conv(P) . conv(Q). Y solo faltaria hacer P x Q = inv(conv(P x Q)) = inv(conv(P) . conv(Q)). y esto se puede lograr con la transformada rápida de fourier en O((n+1000) log (n + 1000)).
Programación dinámica
Programación dinámica es un enfoque en el cual se hace notorio el cambio de memoria por complejidad, generalmente es usado para problemas de optimización, conteo pero, además para problemas de simulación. Generalmente se procede a guardar los estados o alguna característica específica de los mismo, aunque para problemas más complejos se puede guardar partes del estado que luego se pueden armar con algún tipo de estructura de datos.
Ejemplo:
dado un array de n elementos, n menor o igual a 100000 y los elementos en el rango [-10^9, 10^9], hallar la máxima suma de un subarray.
Armando una solución eficiente
primera solución
Primero debemos fijarnos que la cantidad de subarrays es O(n^2). Para una primera solución podemos hacer el siguiente código O(n^3).
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 10;
int a[maxN];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a+i);
}
long long maximumSubarraySum = LLONG_MIN;
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
long long subarraySum = 0;
for (int k = i; k <= j; ++k) {
subarraySum += a[k];
}
maximumSubarraySum = max(maximumSubarraySum, subarraySum);
}
}
printf("%lld\n", maximumSubarraySum);
return 0;
}
segunda solución
Usando nuestro primer enfoque de programación dinámica podemos calcular el tercer for con una simple observación: La suma en el rango [a, b] = sum [1, b] - sum [1, a-1] (note que la suma de un conjunto vacío es 0).
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 10;
int a[maxN];
long long sum[maxN];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a+i);
}
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i-1] + a[i];
}
long long maximumSubarraySum = LLONG_MIN;
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
maximumSubarraySum = max(maximumSubarraySum, sum[j] - sum[i-1]);
}
}
printf("%lld\n", maximumSubarraySum);
return 0;
}
Tercera solución
Para esta solución hay que cambiar significativamente la idea. para esto usaremos un concepto en programación dinámica llamado especialización, esto quiere decir que en vez de pensar dado un array. cual es la maxima suma de un subarray. pensaremos dado un array cual es la suma máxima de un subarray tomando el último elemento (en otras palabras, cual es la maxima suma de un sufijo).
Este pequeño cambio nos da la opción de meterle recursividad, la recursividad nos permite reconocer como guardar los estados. Por tanto la solución sería f(n) = max(a[n-1] + f(n-1), a[n-1]) = a[n-1] + max(0, f(n-1)) con f(0) = 0 (no puedo tomar si no hay elementos). Esto nos está diciendo que primero tomamos el elemento final y luego si la solución para el array sin este elemento es positiva, entonces, la tomo en otro caso solo me quedo con el elemento actual. Finalmente la solución es el máximo para todo n, podemos implementar algo como:
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 10;
int a[maxN];
long long f[maxN];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a+i);
}
for (int i = 1; i <= n; ++i) {
f[i] = a[i] + max(0, f[i-1]);
}
long long maximumSubarraySum = LLONG_MIN;
for (int i = 1; i <= n; ++i) {
maximumSubarraySum = max(maximumSubarraySum, f[i]]);
}
printf("%lld\n", maximumSubarraySum);
return 0;
}
Enfoque codicioso
El enfoque codicioso (greedy), plantea mejorar nuestra solución solo tomando la decisión que mejora nuestro estado actual sin fijarse en lo que puede suceder después.
Ejemplo:
Sergio se está matriculando en la universidad, el solo tiene 30 minutos para hacerlo, y ya consumio casi todo su tiempo. El quiere matricularse en la mayor cantidad de cursos que pueda pero, odia que sus cursos se crucen. dado n intervalos de duración de los cursos, los cursos se repiten en el mismo horario todos los días de la semana, hallar la mayor cantidad de cursos que sergio se pueda matricular.
Armando una solución eficiente
primera solución
Demonos cuenta que una solución es una subsequencia de los horarios, en total hay 2^n subsecuencias, por tanto verificar todas nos demoraría a lo más O(n2^n), aun no haremos un código, esto puede hacerse con recursión o con manejo de bits.
segunda solución
Podemos empezar con una solución por programación dinámica, con un enfoque muy parecido al problema anterior. Sea un intervalo, consideremos todos los intervalos que están antes que el actual, entonces nuestra solución sería f(intervalo) = 1 + max(f(algun intervalo anterior)) (tenga en cuenta que las soluciones anteriores tuvieron que ser calculadas, podemos ordenarlos con la función sort).
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 10;
pair<int, int> classes[maxN];
int dp[maxN];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d %d", &classes[i].first, &classes[i].second);
}
sort(&clases[1], &classes[n+1]);
for (int i = 1; i <= n; ++i) {
dp[i] = 1;
for (int j = 1; j < i; ++j) {
if (classes[j].second <= classes[i].first) {
dp[i] = max(dp[i], 1 + dp[j]);
}
}
}
int maxDisjoint = 0;
for (int i = 1; i <= n; ++i) {
maxDisjoint = max(maxDisjoint, dp[i]);
}
printf("%d\n", maxDisjoint);
return 0;
}
tercera solución
No hablaremos de como se llega esta solución, se probará como es que funciona, pero cuando se vea el tema de greedy se verá más detalladamente como es que surgen estas ideas. Primero ordenaremos como en el problema anterior, luego se comenzará eligiendo el elemento más a la izquierda y sucesivamente tomando el que está más a la izquierda que no se sobrelape con los ya elegidos O(nlogn).
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 10;
pair<int, int> classes[maxN];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d %d", &classes[i].first, &classes[i].second);
}
sort(&clases[1], &classes[n+1], [](pair<int, int> p, pair<int, int> q) {
return p.second < q.second;
});
vector<int> best = {1};
for (int i = 2; i <= n; ++i) {
if (classes[best.back()].second <= classes[i].first) {
best.push_back(i);
}
}
printf("%d\n", (int) best.size());
return 0;
}
prueba: en clases.
Divide & vencerás
Divide y vencerás, bien como su nombre lo dice, propone dividir un problema en partes más pequeñas que sean simples de hacer para luego en el común de los casos armar una solución más compleja.
Ejemplo.
Halle la raíz cuadrada de un número n entero, n menor o igual a 10^9, con al menos 6 digitos de precisión.
Armando una solución eficiente
primera solución
Una primera solución sería plantearnos una solución por busqueda completa, de tal forma que podriamos hallar la raiz cuadrada de n probando con valores con un incremento de epsilon. O(sqrt(n*10^7))
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
double eps = 1e-7;
double sqrtn = 0.;
while ((sqrtn + eps) * (sqrtn + eps) <= n) {
sqrtn += eps;
}
printf("%lf\n", sqrtn);
return 0;
}
segunda solución
Para solucionarlo con un enfoque de divide y venceras, primero nos podemos dar cuenta que la función a calcular es una funcíón creciente, luego que el intervalo de respuestas es desde 0 hasta la raíz cuadrada de mil millones, Ahora nos podemos dar cuenta que si nos fijamos en el elemento medio del intervalo, y este al cuadrado es menor o igual a nuestro, entonces necesariamente todos los menores a la mitad van a ser menores a la raíz cuadrada de n, por otro lado, si este elemento al cuadrado es mayor a n, entonces todos los elementos mayores a la mitad son mayores a la raíz cuadrada de n, esto nos da un simple algoritmo de divide y venceras (se explicara más en clases).
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
double lo = 0, hi = 40000;
for (int i = 0; i <= 100; ++i) {
double mid = lo + (hi-lo)/2;
if (mid * mid <= n) lo = mid;
else hi = mid;
}
printf("%lf\n", lo);
return 0;
}
tercera solución
Con el método de newtom se puede afrontar este problema en especifico de una forma más eficiente. newtom’s method
double Q_rsqrt(double number) {
double f;
double x2;
const double threehalfs = 1.5L;
x2 = number * 0.5L;
f = number;
f = f * ( threehalfs - ( x2 * f * f ) );
return f * number;
}
cuarta solución
Existe un paper muy interesante para solucionar este problema, en su momento fue un boom en la realización de videojuegos. paper
float Q_rsqrt( float number )
{
union {
float f;
uint32_t i;
} conv;
float x2;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
conv.f = number;
conv.i = 0x5f3759df - ( conv.i >> 1 );
conv.f = conv.f * ( threehalfs - ( x2 * conv.f * conv.f ) );
return conv.f * number;
}