Page 1 of 1

3091 - Harry Potter vs Warlocks

Posted: Wed Feb 11, 2015 10:56 pm
by ymondelo20

Re: 3091 - Harry Potter vs Warlocks

Posted: Wed Feb 11, 2015 11:44 pm
by humbertodiaz
Alguien me podria una pista sobre como resolver este ejercicio? Tengo cierta nocion de lo que deberia envolver pero... No logro llegar.

Re: 3091 - Harry Potter vs Warlocks

Posted: Sat Feb 14, 2015 2:58 pm
by HaZard
hacer un meet-in-the-middle
solución AC

Re: 3091 - Harry Potter vs Warlocks

Posted: Mon Feb 23, 2015 4:06 pm
by HaZard
este problema debería tener la etiqueta de Combinations, ya que por ahí fue que hice mi solución

Re: 3091 - Harry Potter vs Warlocks

Posted: Tue Feb 24, 2015 3:20 pm
by ymondelo20
Listo.

Re: 3091 - Harry Potter vs Warlocks

Posted: Tue Feb 24, 2015 5:56 pm
by HaZard
Good

Re: 3091 - Harry Potter vs Warlocks

Posted: Wed Feb 25, 2015 12:44 am
by ymondelo20
Some datasets were added to the problem.
All submissions were rejudged after updating the problem.

Re: 3091 - Harry Potter vs Warlocks

Posted: Thu Mar 19, 2015 7:26 pm
by Dariel
HaZard wrote: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.

Re: 3091 - Harry Potter vs Warlocks

Posted: Fri Mar 20, 2015 12:48 pm
by 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