Page 1 of 1

3022 - Gopher Family

Posted: Fri Oct 17, 2014 6:19 pm
by ymondelo20

Re: 3022 - Gopher Family

Posted: Sun Oct 19, 2014 12:19 am
by AnhellO
Estoy tratando de resolver este problema por medio de un implementación de geometría y greedy (ordenando las distancias de los perritos y los hoyos, y sacando la distancia Euclideana tomando en cuenta la velocidad/seg para cada perrito y su hoyo más cercano), sin embargo estoy sacando WA. ¿Alguien sabe si es posible solucionarlo de está manera?, o bien, ¿se soluciona por medio de Teoría de Grafos?, porque es otra forma en que veo que se puede solucionar, sin embargo no doy como por ese rumbo. De antemano gracias y un saludo! :P

Re: 3022 - Gopher Family

Posted: Mon Oct 20, 2014 11:53 am
by ymondelo20
Estoy bastante seguro de que una solución Greedy no es correcta. Es probable que puedas implementar alguna que resuelva correctamente los datasets actuales, pero con seguridad se podrán diseñar otros conjuntos de datos para los cuales fallaría (no siempre se tienen los datasets perfectos). Y si, se resuelve haciendo uso de Teoría de Grafos, específicamente usando algoritmos de "flujo en redes" en este caso, o técnicas de matching de forma más generalizada sobre grafos bipartitos.

Re: 3022 - Gopher Family

Posted: Mon Nov 03, 2014 9:18 pm
by AnhellO
Algo así me supuse, hahaha.
Muchas gracias de antemano Yonny, y a estudiarle sobre Grafos Bipartitos entonces :D

Saludos!

Re: 3022 - Gopher Family

Posted: Fri Nov 07, 2014 11:02 pm
by humbertodiaz
Yo estuve analizando varios casos posibles y si, existen casos para los cuales una solucion "greedy" no podria escoger correctamente como asociar ardillas con agujeros.

Re: 3022 - Gopher Family

Posted: Wed Nov 19, 2014 8:08 pm
by AnhellO
Que tal humberto, gracias, yo también probé algunos casos nuevos, y sí definitivamente estoy equivocado. Habrá que tratar entonces con Grafos Bipartitos. De antemano gracias y saludos! :)