3022 - Gopher Family

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.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3022 - Gopher Family

Post by ymondelo20 » 6 years ago



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

AnhellO
Posts: 25
Joined: 6 years ago
Gender: None specified

Re: 3022 - Gopher Family

Post by AnhellO » 6 years ago

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

User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3022 - Gopher Family

Post by ymondelo20 » 6 years ago

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.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

AnhellO
Posts: 25
Joined: 6 years ago
Gender: None specified

Re: 3022 - Gopher Family

Post by AnhellO » 5 years ago

Algo así me supuse, hahaha.
Muchas gracias de antemano Yonny, y a estudiarle sobre Grafos Bipartitos entonces :D

Saludos!

humbertodiaz
Posts: 97
Joined: 6 years ago
Gender: None specified

Re: 3022 - Gopher Family

Post by humbertodiaz » 5 years ago

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.

AnhellO
Posts: 25
Joined: 6 years ago
Gender: None specified

Re: 3022 - Gopher Family

Post by AnhellO » 5 years ago

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! :)

Post Reply

Return to “Problem set”