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.
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:

1766 - Full Tank?

Postby ymondelo20 » Mon Mar 26, 2012 4:16 pm



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

ArthurGPym
Posts: 11
Joined: Sat Jul 30, 2016 5:43 pm
Gender: None specified

Re: 1766 - Full Tank?

Postby ArthurGPym » Sun Aug 14, 2016 10:24 pm

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: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 1766 - Full Tank?

Postby HaZard » Tue Aug 23, 2016 2:19 pm

¿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: Sat Jul 30, 2016 5:43 pm
Gender: None specified

Re: 1766 - Full Tank?

Postby ArthurGPym » Sat Aug 27, 2016 9:37 pm

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

User avatar
isaac
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: 1766 - Full Tank?

Postby isaac » Wed Aug 31, 2016 12:37 pm

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: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 1766 - Full Tank?

Postby HaZard » Mon Sep 05, 2016 4:36 pm

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: Sat Jul 30, 2016 5:43 pm
Gender: None specified

Re: 1766 - Full Tank?

Postby ArthurGPym » Mon Sep 05, 2016 11:42 pm

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


Return to “Problem set”

Who is online

Users browsing this forum: No registered users and 1 guest