3091 - Harry Potter vs Warlocks

Discussion around the problems of the COJ.
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.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3091 - Harry Potter vs Warlocks

Post by ymondelo20 » 4 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

humbertodiaz
Posts: 97
Joined: 5 years ago
Gender: None specified

Re: 3091 - Harry Potter vs Warlocks

Post by humbertodiaz » 4 years ago

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

HaZard
Posts: 114
Joined: 5 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 3091 - Harry Potter vs Warlocks

Post by HaZard » 4 years ago

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

HaZard
Posts: 114
Joined: 5 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 3091 - Harry Potter vs Warlocks

Post by HaZard » 4 years ago

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

User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3091 - Harry Potter vs Warlocks

Post by ymondelo20 » 4 years ago

Listo.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

HaZard
Posts: 114
Joined: 5 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 3091 - Harry Potter vs Warlocks

Post by HaZard » 4 years ago

Good
teruel

User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3091 - Harry Potter vs Warlocks

Post by ymondelo20 » 4 years ago

Some datasets were added to the problem.
All submissions were rejudged after updating the problem.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
Dariel
Posts: 51
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified
Contact:

Re: 3091 - Harry Potter vs Warlocks

Post by Dariel » 4 years ago

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.

HaZard
Posts: 114
Joined: 5 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 3091 - Harry Potter vs Warlocks

Post by HaZard » 4 years ago

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
teruel

Post Reply

Return to “Problem set”