2194 - The Trough Game

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.
User avatar
ymondelo20
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

2194 - The Trough Game

Postby ymondelo20 » Fri Dec 07, 2012 1:03 pm



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

User avatar
alurquiza
Posts: 53
Joined: Mon Jun 22, 2015 3:47 pm
Gender: Male

Re: 2194 - The Trough Game

Postby alurquiza » Wed Nov 09, 2016 10:56 am

Este problema no me gusta para nada, ya que es muy engañoso. La solución que se ve es la mascara de bits con costo O(2^N * M * N) y eso al parecer no da, pero el autor utliza esa misma solucion lo que con dos parches, y por eso da en -2seg. Ya lo resolvi, pero es que la solucion que propone el autor, es en base a optimizaciones, y no al costo esperado. :?: :?: :?: :( :o

HaZard
Posts: 113
Joined: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 2194 - The Trough Game

Postby HaZard » Wed Nov 09, 2016 3:08 pm

dame el link a la solucion propuesta por el usuario, aunque si lo resolvi en O(2^N * N * M), pero la complejidad temporal en verdad no es tanto, porque lo que necesitas buscar es cuando mas dos distribuciones que cumplan con la propiedad, y si una distribucion no la cumple entonces para saberlo solo necesitas que incumpla para una de las cadenas que te dan, y se disminuye mucho la complejidad, aunque pienso que si se puediera buscar el peor caso posible, pero eso por ahora te lo debo, si lo encuentro lo publicare entonces, Saludos
teruel

User avatar
alurquiza
Posts: 53
Joined: Mon Jun 22, 2015 3:47 pm
Gender: Male

Re: 2194 - The Trough Game

Postby alurquiza » Wed Nov 09, 2016 4:57 pm

Salio en la USACO, diciembre de 2010 divison silver.

HaZard
Posts: 113
Joined: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 2194 - The Trough Game

Postby HaZard » Mon Nov 14, 2016 11:55 am

Ya esa competencia no aparece en el sitio oficial de USACO, enviame el analisis al correo.
teruel

HaZard
Posts: 113
Joined: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 2194 - The Trough Game

Postby HaZard » Mon Nov 21, 2016 11:19 am

El problema no creo que sea tan complicado como para clasificarlo de nivel 4, en definitiva se resuelve con algo bastante comun, y no hay que razonar mucho tampoco para llegar a la solucion, propongo que lo bajen a nivel 3
teruel

User avatar
alurquiza
Posts: 53
Joined: Mon Jun 22, 2015 3:47 pm
Gender: Male

Re: 2194 - The Trough Game

Postby alurquiza » Mon Nov 21, 2016 11:52 am

HaZard wrote:El problema no creo que sea tan complicado como para clasificarlo de nivel 4, en definitiva se resuelve con algo bastante comun, y no hay que razonar mucho tampoco para llegar a la solucion, propongo que lo bajen a nivel 3


Estoy de acuerdo contigo, pero el problema engaña.

HaZard
Posts: 113
Joined: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 2194 - The Trough Game

Postby HaZard » Mon Nov 21, 2016 1:38 pm

alurquiza wrote:
HaZard wrote:El problema no creo que sea tan complicado como para clasificarlo de nivel 4, en definitiva se resuelve con algo bastante comun, y no hay que razonar mucho tampoco para llegar a la solucion, propongo que lo bajen a nivel 3


Estoy de acuerdo contigo, pero el problema engaña.


En problemas como estos en que la solucion esta muy ajustada a los limites tienes que pensar en como optimizarla lo mas posible, pero si no encuentras nada se convierte en prueba y error
teruel


Return to “Problem set”

Who is online

Users browsing this forum: No registered users and 1 guest