Brute force es un enfoque exhaustivo que trabaja revisando toda posible respuesta mientras la correcta no es encontrada. Esto hace que los algoritmos regidos por este enfoque sean lentos en ejecución. Por ejemplo buscar los factores primos de un número increiblemente grande (> 10^1000) o elegir el mejor movimiento en una partida de ajedrez, tienen tantos estados que hace imposible computacionalmente encontrar una solución bajo este enfoque.
Para hacer un problema de brute force, por tanto, se debe recorrer de la forma más inteligente los estados (tenga en cuenta que el nombre brute force solo se refiere a que no se aplicará ninguna heurística para reolver el problema, pero no a como esto se vaya a realizar).
La estructura común de un algoritmo de brute force es:
c = firstState(Problem)
while c ≠ Λ :
if isPossibleSolution(Problem, c) then
output(Problem, c)
c = nextState(Problem, c)Supongamos que queremos hallar una solución para la ecuación ax + by = c, tal que x > 0 e y > 0 sean enteros. Si queremos recorrer las posibles soluciones, es claro que tengo que tener un valor para x y uno para y. Entonces en un primer intento podemos fijar tanto x como y. de tal forma que tendriamos un algoritmo O(c^2).
bool hasSolution = false;
for (int x = 1; x <= c; ++x) {
for (int y = 1; y <= c; ++y) {
if (not hasSolution and a * x + b * y == c) {
cout << "(" << x << ", " << y << ")" << endl;
hasSolution = true;
}
}
}Esta es una forma eficiente de recorrer toda posible solución?
rpta: No.
Si pensamos mejor el problema, o dibujamos la recta ax + by = c. Podemos darnos cuenta que y es una función de x, por tanto, para todo x hay un único y. Luego es suficiente fijar x en O(c).
bool hasSolution = false;
for (int x = 1; x <= c; ++x) {
int y = (c - a * x) / b; //<- calculamos "y" con una division entera, importa que el resultado sea solo entero?
if (not hasSolution and y > 0 and a * x + b * y == c) {
cout << "(" << x << ", " << y << ")" << endl;
hasSolution = true;
}
}Esta es una forma eficiente de recorrer toda posible solución?
Rpta: Al menos con fuerza bruta, sí. Existe una solución usando el algoritmo extendido de euclides O(log n), pero, no trabaja con fuerza bruta.
Fijar cosas es un recurso muy usado en fuerza bruta, esto ayuda a liberar cálculos engorrosos y a transformar el problema en algo más amigable de codear.
Sea n un número entero, supongamos que queremos hallar la secuencia l, l+1, l+2, ..., r de mayor longitud de tal forma que (l) + (l+1) + (l+2) + ... + (r-1) + (r) = n. Podemos en un primer intento fijar l y r teniendo un algoritmo O(n^3) ??.
int length = 0;
int bestL, bestR;
for (int l = 1; l <= n; ++l) {
for (int r = l; r <= n; ++r) {
if (length >= r - l + 1) {
continue;
}
int sum = 0;
for (int i = l; i <= r; ++i) {
sum += i;
}
if (sum == n) {
length = r - l + 1;
bestL = l;
bestR = r;
}
}
}
if (length != 0) {
cout << bestL << " " << bestR << endl;
}nuestro primer problema es calcular la suma de l a r. Existe una forma eficiente de realizar esto?
Rpta: sí
Para esta reducción, las matemáticas están para ayudarnos. Sea la progresión: 1, 2, 3, 4, ..., m. Esta es una progresión aritmética muy conocida y se sabe que 1 + 2 + 3 + ... + m = m (m + 1) / 2. Por tanto, sum(l ... r) = [r (r + 1) / 2] - [(l-1) l / 2].
auto sum = [](int l, int r) {
return r * (r+1) / 2 - (l-1) * l / 2;
};
int length = 0;
int bestL, bestR;
for (int l = 1; l <= n; ++l) {
for (int r = l; r <= n; ++r) {
if (length >= r - l + 1) {
continue;
}
if (sum(l, r) == n) {
length = r - l + 1;
bestL = l;
bestR = r;
}
}
}
cout << bestL << " " << bestR << endl;Podemos seguir reduciento variables?
supongamos que fijamos l, entonces tendriamos que verificar [r (r+1) / 2] - [(l-1) l / 2] = n, lo podemos manipular como [r (r + 1) / 2] = n + [(l-1) l / 2]. como l esta fijo puedo decir que se debe verificar [r (r+1)] = m. Luego r (r + 1) = m, y entonces, r x r <= r x r + r = m < (r+1)x(r+1). por tanto, r <= sqrt(m) < (r+1). O(n sqrt(log m)).
auto sum = [](int l, int r) {
return r * (r+1) / 2 - (l-1) * l / 2;
};
int length = 0;
int bestL, bestR;
for (int l = 1; l <= n; ++l) {
int m = 2 * n + l * (l+1);
int r = sqrt(m) + 0.5; //<- esto demora sqrt(log m)
for (int i = -1; i <= 0; ++i) {
if (r+i - l + 1 > length and sum(l, r+i) == n) {
length = r+i - l + 1;
bestL = l;
bestR = r+i;
}
}
}
cout << bestL << " " << bestR << endl;Existe una solución mejor?
Sí, Podriamos entonces fijar length. Cual es el temaño máximo de length? Si vemos la ecuación [r (r + 1) / 2] - [(l-1) l / 2] = n, entonces, para que r - l + 1, supongamos que l = 1. Luego el máximo tamaño de length es r, con lo caul length (length + 1) / 2 = n. esto nos dice que length es muy cercano a la raiz cuadrada de n.
Pero, aun necesitamos aprovechar este hecho. es claro que sabiendo length podemos verificar que (l-1) x length + length x (length + 1) / 2 == n cumple. luego tenemos l = (n - length x (length + 1) / 2) / length + 1. Que nos dice que la unica condicion para que l exista, conocido el length es que (n - length x (length + 1) / 2) sea multiplo de length! O(sqrt(n))
int bestL, bestR;
for (int length = 1; length * (length + 1) / 2 <= n; ++length) {
if ((n - length * (length + 1) / 2) % length == 0) {
bestL = (n - length * (length + 1) / 2) / length + 1;
bestR = bestL + length - 1;
}
}
cout << bestL << " " << bestR << endl;Pero esta es la mejor solución?
Sí. sabemos que para que exista l, debe existir un x = length tal que n / x - (x + 1) / 2, con x entero. Luego si x es impar, necesariamente debe ser un divisor de n y si x es par necesariamente n debe ser impar. Pero, hallar los divisores toma O(sqrt(n)), no? pues existen algoritmos que podrian trabajar en menos tiempo, pero sin ser tan ambiciosos, podriamos hallar todos los divisores de n en O(sqrt(n) / log(n)) usando la criba de eratostenes pero, para esto se necesita más conocimientos en teoría de números. Si supieramos un algoritmo para encontrar el mayor o menor divisor propio de un número en un tiempo eficiente podriamos tener un algoritmo O(logn + complejidad de hallar menor o mayor primo que divide n > 2) = O(logn x raiz cuarta de n ) con pollard's rho.
nota: se necesita conocimientos en STL
La técnica de la contribución es muy útil en muchas situaciones, es una forma de reducir cálculos con muchas variables a solo una, generalmente los problemas que se prestan para esta técnica son problemas de combinatoria y conteo.
Sean n puntos distintos en el plano, hallar cuantos triangulos no degenerados se pueden formar, usando los puntos como vertices. Para resolver este problema, podemor hacer lo siguiente: como contribuye un vertice a la respuesta final? si dos vertices y nuestro vertice fijo son no colineares, entonces necesariamente se puede formar un triangulo. En resumidas cuentas, si para cada recta que pase por el punto fijo hay el menos 1 elemento distinto del mismo. entonces esta recta contribuye a la solución final con (cantidad de elementos - 1) x (n - cantidad de elementos) / 6 (se divide entre 6 porque cada punto lo cuenta 3 veces y x 2 veces dado cada direccion).
La pregunta entonces sería: como mapear una recta de forma eficiente? para cada punto mapear una recta podria ser con su vector direccion, lo normalizamos v / gcd(v.x, v.y) y hacemos que v.x sea positivo o si es 0, hacemos que v.y sea positivo. Pruebe que esto le da un unico mapeo a cada recta!
map<pair<int, int>, int> tri[maxN];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x[i] >> y[i];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) {
continue;
}
int vx = x[i] - x[j];
int vy = y[i] - y[j];
int g = gcd(abs(vx), abs(vy));
vx /= g;
vy /= g;
if (vx < 0 or vx == 0 and vy < 0) {
vx = -vx;
vy = -vy;
}
tri[i][{vx, vy}] += 1;
}
}
long long ans = 0;
for (int i = 1; i <= n; ++i) {
for (auto v : tri[i]) {
ans += (n-1 - v.second) * v.second;
}
}
cout << ans / 6 << endl;
return 0;
}