3091 - Harry Potter vs Warlocks
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
- ymondelo20
- Posts: 1968
- Joined: 8 years ago
- Location: Universidad de las Ciencias Informáticas
- Gender:
- Contact:
3091 - Harry Potter vs Warlocks
"Every problem has a simple, fast and wrong solution" OJ's Main Law. 

-
- Posts: 97
- Joined: 5 years ago
- Gender:
Re: 3091 - Harry Potter vs Warlocks
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
este problema debería tener la etiqueta de Combinations, ya que por ahí fue que hice mi solución
teruel
- ymondelo20
- Posts: 1968
- Joined: 8 years ago
- Location: Universidad de las Ciencias Informáticas
- Gender:
- Contact:
Re: 3091 - Harry Potter vs Warlocks
Listo.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. 

- ymondelo20
- Posts: 1968
- Joined: 8 years ago
- Location: Universidad de las Ciencias Informáticas
- Gender:
- Contact:
Re: 3091 - Harry Potter vs Warlocks
Some datasets were added to the problem.
All submissions were rejudged after updating the problem.
All submissions were rejudged after updating the problem.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. 

Re: 3091 - Harry Potter vs Warlocks
Puedes explicar este algoritmo, muchos no tiene internet y es muy complejo para otros llegar a la solución aplicando ese razonamiento.HaZard wrote:hacer un meet-in-the-middle
solución AC
Saludos.
Dariel.
Re: 3091 - Harry Potter vs Warlocks
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
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
teruel