3091 - Harry Potter vs Warlocks

[ymondelo20]

http://coj.uci.cu/24h/problem.xhtml?pid=3091

[humbertodiaz]

Alguien me podria una pista sobre como resolver este ejercicio? Tengo cierta nocion de lo que deberia envolver pero... No logro llegar.

[HaZard]

hacer un meet-in-the-middle
solución AC

[HaZard]

este problema debería tener la etiqueta de Combinations, ya que por ahí fue que hice mi solución

[ymondelo20]

Listo.

[HaZard]

Good

[ymondelo20]

Some datasets were added to the problem.
All submissions were rejudged after updating the problem.

[Dariel]

hacer un meet-in-the-middle
solución AC

Puedes explicar este algoritmo, muchos no tiene internet y es muy complejo para otros llegar a la solución aplicando ese razonamiento.
Saludos.
Dariel.

[HaZard]

realmente no es como tal un algoritmo, sería más bien una técnica como la dp:

Un meet-in-the-middle (o encontrarse en el medio) se basa en dividir el problema en dos partes (en este caso la lista), trabajarlas por separado y de alguna forma combinar las soluciones de una mitad con la otra.

la solución más evidente a ese problema sería buscar todos los subconjuntos posibles y chequear si harry puede vencer a cada uno por separado, pero esto sería O(2^n), que para 34 elementos es demasiado lento, sin embargo si divides la lista a la mitad en el peor de los casos tendrías dos sublistas de 17 elementos cada una, dando una complejidad O(2 * 2^(N/2)) (en el caso extremo 2^18), el resto va por tí, suerte