2227 - Walking Among Mountains I

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
dovier
Posts: 1143
Joined: 8 years ago
Location: Havana, Cuba
Gender: Male
Cuba

2227 - Walking Among Mountains I

Post by dovier » 7 years ago




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

Re: 2227 - Walking Among Mountains I

Post by ymondelo20 » 6 years ago

Time limits was increased.
All submissions rejudged after that.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

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

Re: 2227 - Walking Among Mountains I

Post by humbertodiaz » 5 years ago

Saludos. Necesito algunas clarificaciones sobre este ejercicio. Primero, cual es el origen del mapa?

Segundo, la descripcion dice "always traveling forward or down with length 1". Entonces, los caminos solo pueden ser en unas direcciones particulares? Cuales direcciones son "forward" y "down"? En realidad eso no parece ser consistente con el origen que podria inferir. Quizas es un error en una traduccion y es legal moverse en cualquier direccion.

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

Re: 2227 - Walking Among Mountains I

Post by Dariel » 5 years ago

primera pregunta sobre "...forward and down..." quiere decir que solo solo pudes caminar hacia delante o hacia abajo.
Sobre el origen del mapa, el punto de partida siempre es en la posición (1, 1) y el de llegada es en la posición (x, y).
Quiero decir que desde la posición (1, 1) puedes ir directamente a las posiciones (1, 2) o (2, 1).
Saludos, y espero que sea de tu ayuda.
Dariel.

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

Re: 2227 - Walking Among Mountains I

Post by humbertodiaz » 5 years ago

Gracias Dariel. Entiendo lo que significan las palabras literalmente, pero con respecto al mapa, que es "adelante"? Y que es para abajo? La ambigüedad solo empeora si consideramos que el ejercicio se trata de montañas y que podemos subir o bajar (dependiendo de las alturas), que no debe ser a lo que se refiere esa parte de la descripcion. En adicion, el ejercicio dice que comenzamos en (1, 1), pero no dice cual lugar del mapa corresponde a ese punto.

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

Re: 2227 - Walking Among Mountains I

Post by HaZard » 5 years ago

humbertodiaz wrote:Gracias Dariel. Entiendo lo que significan las palabras literalmente, pero con respecto al mapa, que es "adelante"? Y que es para abajo? La ambigüedad solo empeora si consideramos que el ejercicio se trata de montañas y que podemos subir o bajar (dependiendo de las alturas), que no debe ser a lo que se refiere esa parte de la descripcion. En adicion, el ejercicio dice que comenzamos en (1, 1), pero no dice cual lugar del mapa corresponde a ese punto.
Hace ya algun tiempo que hice el ejercicio este y no me acuerdo bien, pero por lo que veo te puedes mover en las cuatro direcciones, arriba, abajo, derecha e izquierda, la casilla (1, 1) es la de más arriba a la izquierda, ahora realmente debes darte cuenta de que solo hay que analizar moverse hacia la derecha o hacia abajo, porque de lo contrario o gastas más calorías o caminas por gusto, Saludos
teruel

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

Re: 2227 - Walking Among Mountains I

Post by humbertodiaz » 5 years ago

HaZard wrote:Hace ya algun tiempo que hice el ejercicio este y no me acuerdo bien, pero por lo que veo te puedes mover en las cuatro direcciones, arriba, abajo, derecha e izquierda, la casilla (1, 1) es la de más arriba a la izquierda, ahora realmente debes darte cuenta de que solo hay que analizar moverse hacia la derecha o hacia abajo, porque de lo contrario o gastas más calorías o caminas por gusto, Saludos
Gracias! Ahora lo puedo intentar. Creo que si es critico saber si uno se puede mover en las cuatro direcciones. Se pueden crear mapas en que existe una ruta que requiere movimiento en todas direcciones pero tiene el costo minimo. Por ejemplo, el siguiente mapa:

55555
99995
55555
59999
55555

...con el objetivo de llegar a la esquina de abajo a la derecha. Se puede hacer consumiendo 0 calorias si se sigue la ruta con la misma altura.

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

Re: 2227 - Walking Among Mountains I

Post by HaZard » 5 years ago

humbertodiaz wrote:
HaZard wrote:Hace ya algun tiempo que hice el ejercicio este y no me acuerdo bien, pero por lo que veo te puedes mover en las cuatro direcciones, arriba, abajo, derecha e izquierda, la casilla (1, 1) es la de más arriba a la izquierda, ahora realmente debes darte cuenta de que solo hay que analizar moverse hacia la derecha o hacia abajo, porque de lo contrario o gastas más calorías o caminas por gusto, Saludos
Gracias! Ahora lo puedo intentar. Creo que si es critico saber si uno se puede mover en las cuatro direcciones. Se pueden crear mapas en que existe una ruta que requiere movimiento en todas direcciones pero tiene el costo minimo. Por ejemplo, el siguiente mapa:

55555
99995
55555
59999
55555

...con el objetivo de llegar a la esquina de abajo a la derecha. Se puede hacer consumiendo 0 calorias si se sigue la ruta con la misma altura.
Si, tienes toda la razon, no creo que ese tipo de casos de prueba aparezcan en el ejercicio, porque casi todas las soluciones son similares a la mía, aunque no estoy muy de acuerdo con que no haya casos como esos en los que hay que usar Teoría de Grafos o un Backtracking
teruel

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

Re: 2227 - Walking Among Mountains I

Post by humbertodiaz » 5 years ago

HaZard wrote:Si, tienes toda la razon, no creo que ese tipo de casos de prueba aparezcan en el ejercicio, porque casi todas las soluciones son similares a la mía, aunque no estoy muy de acuerdo con que no haya casos como esos en los que hay que usar Teoría de Grafos o un Backtracking
Yo le enviare un correo a Yonny despues a ver si el sabria decir definitivamente cual era la intencion de este ejercicio. Si se permite movimiento en todas direcciones, entonces se pueden añadir pruebas que incluyan ese aspecto. No seria la primera vez que se haga una cosa asi. Yo encontre que algunas de las soluciones para Words (#1167) generaban resultados suboptimos pero todavia eran aceptadas. Se podia ver a traves de Datagen. Tambien Marko Schutz noto, usando Datagen, que las pruebas para Network Problem (#1368) no eran suficientemente fuertes y sometio algunos casos adicionales. Eso invalido muchas soluciones incorrectas, incluyendo la mia. =P

Post Reply

Return to “Problem set”