2617 - Segment

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: 9 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

2617 - Segment

Post by ymondelo20 » 7 years ago



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

BeCrazy
Posts: 6
Joined: 7 years ago
Gender: None specified

Re: 2617 - Segment

Post by BeCrazy » 7 years ago

Por favor revisen los juegos de datos de este problema,que es algo trivial de geometria.Incluso ordene los punto con un convex hull y luego calcule el area de poligono y igual me WA en el test 2

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

Re: 2617 - Segment

Post by ymondelo20 » 7 years ago

Creo que puede necesitar un validador para controlar el margen de error de los cálculos.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

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

Re: 2617 - Segment

Post by humbertodiaz » 6 years ago

Creo que este ejercicio se deberia revisar. Yo intente resolverlo hace un año atras cuando todavia estaba disponible la opcion de datagen. Genere miles de pruebas aleatorias para verificar que mi codigo daba los mismos resultados que daba datagen. Eventualmente contacte a Yonny por que sospechaba que habia algo mal. Era demasiado extraño que tan pocos intentos eran exitosos aunque era un ejercicio sencillo.

Yonny me envio los datos del caso #6 para que yo verificara que podria estar fallando. Mi programa daba exactamente los resultados que se esperaban. Despues me envio todos los casos para verificar con todos los datos. Todo salio igual, pero por razones que nunca deciframos, mi solucion fallaba cuando la sometia. Intente modificarla para usar long double, entre otras opciones, para evitar errores numericos que podrian estar afectando los resultados. No ayudo.

No se me ocurre que podria estar pasando aqui. Quizas alguien que lo haya logrado resolver nos podria contar la tecnica secreta?

Edit: Feliz cumpleaños Yonny!

HaZard
Posts: 114
Joined: 6 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 2617 - Segment

Post by HaZard » 6 years ago

Saludos, me paso algo muy parecido a lo de ustedes, y la solucion que encontré fue sumarle a la solución un epsilon de 10^-9, algo parecido a lo que explica EduardoQuintana en su post para el ejercicio 2410 - Area of Squares, aqui lo tienen:
http://coj-forum.uci.cu/viewtopic.php?f=22&t=1632
teruel

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

Re: 2617 - Segment

Post by humbertodiaz » 6 years ago

Gracias! Tambien estaba teniendo problemas con el ejercicio #2410. Pense eventualmente escribir sobre eso aqui, pero primero queria tratar de resolver este. No me percate que ya habian mencionado esa tecnica. Funciono, aunque parece que el epsilon tiene que ser 10^-9 o muy pequeño. Intente 10^-6 y fallo.

Tambien quisiera notar que no tengo ese problema con mi maquina. Es decir, mis respuestas salen correctas sin usar eso. Intente el ejemplo de Eduardo con 1/8 y me dio 0.13. Por eso no podria detectar el problema haciendo pruebas en mi computadora.

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

Re: 2617 - Segment

Post by ymondelo20 » 5 years ago

Por lo general el epsilon debe ser correspondiente al aproximado de operaciones con números flotantes que se hagan en la solución y que pudieran afectar el resultado.
Las divisiones son por lo general las operaciones que mayor perdida tienen, un poco menos la multiplicación, suma y resta es casi insignificante al final.
Es válido notar que en el cálculo siempre se suele perder exactitud; o sea que típicamente se obtiene un menor resultado que el correcto.
De ahí que en la mayoría de los casos se suele sumar el epsilon al final; en los que se resta se cumple lo anterior también.

En lo particular asumo que la pérdida en una operación es muy cercana a 1e-9 (es lo mismo que 10^-9), y teniendo en cuenta esto calculo el epsilon adecuado para ajustar el resultado final. Si se realizan unas 1000 operaciones de suma/resta consecutivas sobre una misma variable flotante, entonces un epsilon edecuado sería 1000 * 1e-9 = 1e-6, pero no siempre es tan sencillo, pues por lo general el error se arrastra a otras operaciones.

Mi recomendación, evitar ese tipo de problemas, o buscar variantes de ellos que permitan resolverlos sin realizar muchas operaciones basadas en números flotantes. Los validadores son una variante también, pero el valor absoluto a tener en cuenta suele ser muy relativo y depende de quien lo haga.

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

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

Re: 2617 - Segment

Post by ymondelo20 » 4 years ago

Finalmente he adicionado un validador para comprobar la diferencia absoluta en los resultados.
Espero que varios obtengan su ACC después de recalificar.

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

Post Reply

Return to “Problem set”