[T2 p2]

[Chumi-Colores]

Podrían dar algún otro hint para la p2? Llevo estancado un buen rato y no logro llegar a una solución greedy que obtenga un óptimo local que sea óptimo global y finalmente acabo con que mi greedy se transforma en backtracking porque le falta información para decidir.

He pensado muchos algoritmos greedy, pero siempre se da un contraejemplo.

Si el enunciado pidiera un resultado sub óptimo, como dan muchos algoritmos greedy, entonces ya podría verlo mejor, pero al pedir el óptimo me parece imposible.

[Huasito-Appel]

Up!, ando medio parecido en donde para algunos test cases llego al valor optimo pero para otros me caigo, no logro pensar en el greedy que llegue al optimo.

[mc-cari]

Hola, más que nada hay que apoyarse en la definición de greedy, hay que definir cual va a ser la solución parcial y que elementos tiene, para luego expandirla con decisiones óptimas, las cuales son intuitivas. Dependiendo del estado de la solución parcial puede variar la decisión óptima pero no hay problema con probar todas las decisiones posiblemente óptimas ya que en un algoritmo greedy siempre se sabe cual es la mejor solo tomando en cuenta la solución parcial y lo que se expande. Ya con soluciones subóptimas lo mejor es revisar a mano la solución con tests partiendo con una solución parcial (pequeña). Al revisar a mano se pueden descubrir que decisión no fue óptima. Otra opción es intentar demostrar que su solución greedy funciona y ver donde falla la demostración. Finalmente el código no debiera quedar complejo, dado que existen decisiones óptimas.