Page 1 of 1

2194 - The Trough Game

Posted: Fri Dec 07, 2012 1:03 pm
by ymondelo20

Re: 2194 - The Trough Game

Posted: Wed Nov 09, 2016 10:56 am
by alurquiza
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

Re: 2194 - The Trough Game

Posted: Wed Nov 09, 2016 3:08 pm
by HaZard
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

Re: 2194 - The Trough Game

Posted: Wed Nov 09, 2016 4:57 pm
by alurquiza
Salio en la USACO, diciembre de 2010 divison silver.

Re: 2194 - The Trough Game

Posted: Mon Nov 14, 2016 11:55 am
by HaZard
Ya esa competencia no aparece en el sitio oficial de USACO, enviame el analisis al correo.

Re: 2194 - The Trough Game

Posted: Mon Nov 21, 2016 11:19 am
by HaZard
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

Re: 2194 - The Trough Game

Posted: Mon Nov 21, 2016 11:52 am
by alurquiza
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.

Re: 2194 - The Trough Game

Posted: Mon Nov 21, 2016 1:38 pm
by HaZard
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