1766 - Full Tank?

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: 6 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

1766 - Full Tank?

Post by ymondelo20 » 6 years ago



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

ArthurGPym
Posts: 11
Joined: 2 years ago
Gender: None specified

Re: 1766 - Full Tank?

Post by ArthurGPym » 2 years ago

Hola. Estuve pensando el problema con programacion dinamica. El estado seria la ciudad donde estoy y cuanto "fuel" tengo. Hay dos posibilidades, o ir a una nueva ciudad si tengo el suficiente fuel sin costo o permanecer en mi ciudad pero comprando fuel y gastando. Veo todas las posibilidades y el costo minimo lo guardo en una matriz[ciudades][capacidadMaxima]. El problema es que me dice time limit exceeded. Que estoy haciendo mal?

HaZard
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 1766 - Full Tank?

Post by HaZard » 2 years ago

¿cómo haces la transición entre las ciudades? cómo haces la dp, memoization o dijkstra ???
Last edited by HaZard on Mon Sep 05, 2016 4:41 pm, edited 1 time in total.
teruel

ArthurGPym
Posts: 11
Joined: 2 years ago
Gender: None specified

Re: 1766 - Full Tank?

Post by ArthurGPym » 2 years ago

Intenté usar dijkstra pero no logro hacerlo funcionar de forma eficiente/correcta.

User avatar
isaac
Posts: 83
Joined: 2 years ago
Gender: None specified

Re: 1766 - Full Tank?

Post by isaac » 2 years ago

Creo que seria bueno antes de aplicar el dijkstra, hacer un arbol de expansion minima descartando tanto los caminos que crean ciclos como los que son imposibles de transitar completos. Seria un buen comienzo

HaZard
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 1766 - Full Tank?

Post by HaZard » 2 years ago

estando parado en un nodo, no puedes tirarte a ver todas las ciudades y para cada una comprobar los k litros de combustible posibles, es más eficiente que si no tienes combustible hagas una arista hacia el mismo nodo con un litro más, claro si mejora el costo
teruel

ArthurGPym
Posts: 11
Joined: 2 years ago
Gender: None specified

Re: 1766 - Full Tank?

Post by ArthurGPym » 2 years ago

Gracias. Voy a probar lo que me dicen y ver si me funciona.

Post Reply

Return to “Problem set”