Buenas!
Adjunto las soluciones a las cuales llegué en ambos ejercicios, ya que quiero saber sin son correctas.
El algoritmo del ejercicio 2 es el visto en la clase de monitoreo.
Gracias,
Saludos.
Buenas,
Como comentó Javier en el foro, la idea es que las dudas sobre si un ejercicio está bien resuelto se despejen durante los monitoreos. El foro de consultas es para despejar dudas puntuales.
De cualquier manera, te realizo algunos comentarios sobre las soluciones.
Para el Ej 1, no es clara cuál es la medida que elegiste para comparar tu solución con la óptima. Es decir para mostrar que tu solución está "por delante". Vos ponés que tu solución está "por delante" porque cubre la mayor cantidad de casas con la menor cantidad posible de antenas, pero esto es directamente la definición de ser óptimo. La idea es que tu solución esté por delante, en el mismo sentido que tu algoritmo elige las antenas. Es decir, la posición de la antena en la posición i de tu solución (si están ordenadas por coordenada), siempre va a ser más a la derecha (o en la misma posición) que la antena en la posición i de la solución óptima.
Luego para terminar la demostración también hay un problema con el absurdo que decidis plantear. La idea es que por absurdo consideres que la cantidad de antenas de tu solución es mayor que la óptima, y utilizando lo que mostraste antes llegues a un absurdo.
Respecto al Ej2 falta argumentar por qué el tiempo de llegada de los otros competidores no se modifica luego de deshacer una inversión.
Por otro lado, hay que justificar que si existe una inversión cualquiera, entonces existe una consecutiva y esta es la que deshacemos.
Saludos,
Guillermo
Como comentó Javier en el foro, la idea es que las dudas sobre si un ejercicio está bien resuelto se despejen durante los monitoreos. El foro de consultas es para despejar dudas puntuales.
De cualquier manera, te realizo algunos comentarios sobre las soluciones.
Para el Ej 1, no es clara cuál es la medida que elegiste para comparar tu solución con la óptima. Es decir para mostrar que tu solución está "por delante". Vos ponés que tu solución está "por delante" porque cubre la mayor cantidad de casas con la menor cantidad posible de antenas, pero esto es directamente la definición de ser óptimo. La idea es que tu solución esté por delante, en el mismo sentido que tu algoritmo elige las antenas. Es decir, la posición de la antena en la posición i de tu solución (si están ordenadas por coordenada), siempre va a ser más a la derecha (o en la misma posición) que la antena en la posición i de la solución óptima.
Luego para terminar la demostración también hay un problema con el absurdo que decidis plantear. La idea es que por absurdo consideres que la cantidad de antenas de tu solución es mayor que la óptima, y utilizando lo que mostraste antes llegues a un absurdo.
Respecto al Ej2 falta argumentar por qué el tiempo de llegada de los otros competidores no se modifica luego de deshacer una inversión.
Por otro lado, hay que justificar que si existe una inversión cualquiera, entonces existe una consecutiva y esta es la que deshacemos.
Saludos,
Guillermo