Problemas ad hoc

Introducción

Según la sección 1.2 de USACO Training:

Los problemas ad hoc son aquellos cuyos algoritmos no caen en categorías estándar con soluciones bien estudiadas. Cada problema ad hoc es distinto; no existen técnicas específicas ni generales para resolverlos.

Estos consejos generales pueden servir al encarar problemas que parecen ad hoc.

• Dibujar muchos casos chicos para entender mejor el problema. Si hay problemas para depurar, dibujar más casos. Si no se sabe por dónde empezar, dibujar más casos. Cuando no se sabe cómo seguir, es probable que falte una observación importante: hay que dibujar más casos y observar propiedades del problema.
• Cada vez que aparezca una observación que parezca útil, ¡escribirla! Anotar las ideas permite volver a ellas más tarde y evita olvidar ideas que podrían ser la solución.
• No quedarse atascado en una idea concreta, salvo que se vea una solución completa.
• Intentar encarar el problema desde muchas perspectivas distintas. Probar a jugar con fórmulas o dibujar una representación visual del problema. Una de las cosas más útiles al resolver problemas ad hoc es seguir probando ideas hasta avanzar. Eso mejora a medida que se resuelven más problemas.

Al final, la mejor forma de mejorar en problemas ad hoc (o en cualquier tipo de problema) es resolver muchos.

Ejemplo - Photoshoot 2

#include <cstring>
#include <iostream>
 
int main() {
	int n;
	std::cin >> n;
	int moved[n] = {0};
	int a[n], b[n];
 
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		a[i]--;
	}
 
	for (int i = 0; i < n; i++) {
		std::cin >> b[i];
		b[i]--;
	}
 
	int res = 0;
	int j = 0;
 
	for (int i = 0; i < n; i++) {
		while (j < n && moved[a[j]]) { j++; }
 
		if (a[j] == b[i]) {
			j++;
		} else {
			res++;
			moved[b[i]] = 1;
		}
	}
 
	std::cout << res << '\n';
}

n = int(input())
a = [int(x) - 1 for x in input().split()]
b = [int(x) - 1 for x in input().split()]
 
moved = [0] * n
j = res = 0
 
 
for i in range(n):
	while j < n and moved[a[j]]:
		j += 1
 
	if a[j] == b[i]:
		j += 1
	else:
		res += 1
		moved[b[i]] = 1
 
 
print(res)

Problemas

Quiz