pr5ej2a)

pr5ej2a)

de Valentina Chagas Bas -
Número de respuestas: 4

Buenas, no se me ocurre cual podria ser la solucion optima. Lo que pense yo es que no importa como ordene los tiempos de natacion esa etapa siempre dura lo mismo ya que deben ir uno a la vez, por lo que tendria que ordenar el tiempo de las etapas de ciclismo y carrera a pie para que sea lo mas corto posible. El problema es que no se bien que estrategia usar porque no lo puedo comparar a los problemas del libro. 

En si creo que para cada tramo tenemos su duracion y tambien cuanto tiempo despues del tramo anterior debe empezar. Entonces el tiempo que empieza el primer tramo es n1, el segundo n1+n2 , el tercero n1+n2+n3, ..etc, y el tiempo de llegada es n1+c1+p1 el del segundo es n1+n2+c2+p2 etc, por lo que el ultimo en salir llega en tiempo n1+n2+....+nm+cm+pm. Pero no puedo avanzar mas que eso. No se como ordenarlos. Alguna ayuda? Gracias

En respuesta a Valentina Chagas Bas

Re: pr5ej2a)

de Facundo Benavides -
hola valentina,
me gustó el primer párrafo.
si bien el tiempo de uso total de la piscina no cambia, es relevante el orden en que largan los participantes para que la competencia termine lo antes posible.
lo otro invariante es el tiempo que demoraría cada competidor una vez sale de la piscina. entonces, qué competidor debería salir primero para minimizar el tiempo del triatlón?
sugiero imagines que ese tiempo óptimo sea T* y trates de encontrar una relación con el plazo máximo de salida de la piscina para un competidor cualquier ci.
en esa situación ya estarías como para usar alguno de los resultados del libro y definir un orden de largada.
saludos
En respuesta a Facundo Benavides

Re: pr5ej2a)

de Esteban Normey Rieta -
Buenas,
He estado pensando en como llegar a una solución óptima y, siguiendo la línea de pensamiento creo que llegué a algo. Podrían decirme si toy bien encaminado para hacer una demostración más formal?
Idea:
Para cada participante i hay un tiempo t_i que demora en realizar las 3 pruebas siendo t_i = n_i + c_i + p_i donde n_i := tiempo en natacion, c_i := tiempo en ciclismo y p_i := tiempo a pie. Que asumo que sabemos estos valores por la letra.

Queremos un orden de participantes donde el participante i = 1 sea el primero en salir, i = 2 el segundo y así.

Lo que demora cada paricipante j en llegar a la meta es T_j = n_1 + ... + n_{j-1} + t_j. Queremos minimizar el max T_j.
Depende de dos cosas: 1. cuánto tuvo que esperar.
2. cuánto le toma realizar la competencia.

1. Si lo vamos largando en orden de menor n_j, minimizamos lo que tienen que esperar (la sumatoria de n_1 +...+n_{j-1}).
PERO ESTO NO ES SUFICIENTE (vi haciendo ejemplos)
2. Nos conviene que los que más tarden sean largados antes para que lleguen antes.

Con estas dos observaciones podemos llegar a una conclusión (no se si es verdadera) de que: para minimizar max T_j debemos hacer esperar lo menos posible a cada participante j y largar a los que demoran más antes.
O sea, los ordenamos por menor n_j y resolvemos empates por mayor t_j.
En respuesta a Esteban Normey Rieta

Re: pr5ej2a)

de Facundo Benavides -

hola esteban,

un contraejemplo con 3 participantes sería: 1) 5,4,3; 2) 6,6,2; 3) 7,5,5.

el óptimo se lograría ordenando la largada según 3,2,1 y, si no entendí mal, tu algoritmo ordenaría 1,2,3. los tiempos de competencia serían 25 y 28, respectivamente.

saludos