Problema - UVa 427 - FlatLand Piano Movers

[Joacru]

Buenasss. Resolví este problema, pero me quedaron unas dudas cuando leí las hints propuestas por el CP4.
Procedo a contar mi idea de forma resumida y luego planteo mis dudas.

Idea AC

Adjunto una imagen para que se entienda mejor:

Las rectas verde y azul están a una distancia de sus respectivos ejes igual los anchos de los pasillos del testcase.
Si se quiere rotar el piano 90° hay que pasar obligatoriamente por todos los ángulos \alpha (0°\leq\alpha\leq90°).
Sean r y l las longitudes de los lados del piano (r<l) se puede trazar una circunferencia con centro en el origen con radio r. Sea cual sea la rotación del piano, si lo hacemos que uno de los lados toque el origen, el lado opuesto va a ser tangente a la circunferencia. Si trazamos una recta que pase sobre el lado y calculamos las intersecciones D y E con las rectas verde y azul respectivamente, la distancia entre estos dos puntos debe ser mayor o igual a l.
Súper simplificando lo de arriba voy a decir que f(\alpha) = \text{distancia(D,E)}. El piano va a poder pasar si f(\alpha) \geq l (0°\leq\alpha\leq90°).
f(\alpha) es unimodal por lo que se puede usar búsqueda ternaria para encontrar el punto mínimo.

Y acá vienen mis dudas.

¿Por qué f(\alpha) es unimodal?

Haciendo algunas observaciones y teniendo fe concluí que así era, pero no encuentro la forma de asegurarme que así lo sea.

Hints del CP4

Hints del CP4

for each two consecutive corridors; try rotating the piano by a small angle alpha in [0.1…89.9] degrees; use trigonometry to determine if the piano rotated by angle alpha can pass

¿Cómo elegir correctamente en cuánto variar \alpha?

Como no menciona búsqueda ternaria me imagino que se puede iterar por posibles valores de \alpha, pero ¿cómo saber en cuánto variar \alpha para evitar falsos positivos? Y la pregunta va más en general, en cualquier situación ¿cómo se podría estimar esa variación?

¿Cómo que trigonometría?

Estuve pensando en cómo usar trigonometría para resolver este problema. Justo escribiendo esto se me ocurrió algo, lo escribo para ponerlo en discusión. En vez de pegar el piano al origen se puede pegar el piano a las rectas verde y azul. Entonces teniendo el valor de \alpha y el lado l se pueden calcular las longitudes de los catetos del triángulo rectángulo que se forma. Con eso se puede obtener la ubicación de la hipotenusa y habría que checkear si la distancia al origen es al menos r.

---

Gracias por leer y si pueden darme una mano para entender las dudas planteadas les agradezco el doble
¡Gracias de antemano !

[santo]

¡Muy buen análisis!

Sobre trigonometría, si escribís las cuentas que estás haciendo en términos de alpha quedan cuentitas con las funciones trigonométricas seno y coseno seguramente (al menos para rotar y obtener el vector C inicial antes de tirarle todo el resto a una biblioteca de geometría pre-escrita como caja negra, seguramente ese vector lo tengas como (r \cos (\alpha), r \sin (\alpha)) ). Yo creo que cuando dice “cuentitas con trigonometría” el libro se refiere a todo esto sin dar detalle.

Entiendo que el ángulo \alpha = BAC

De tu mismo dibujo C = (r \cos(\alpha), r \sin(\alpha))

Llamando F a donde la prolongación de CE corta al eje X , tenemos que \tan(\alpha) = \frac{\overline{CF}}{r} y que \cos \alpha = \frac{r}{\overline{AF}}.

Sean W_1 y W_2 los anchos de los pasillos azul y verde respectivamente, que también son la coordenada x de E y la coordenada y de D respectivamente. Llamemos C' al punto donde una paralela a las azules que pasa por C toca al eje x, o sea C' = (r \cos \alpha, 0). De lo anterior se ve que \overline{C'F} = \overline{AF} - \overline{AC'} = \frac{r}{\cos \alpha} - r \cos \alpha. Similarmente sea E' = (W_1, 0) donde la azul que pasa por E toca al eje x.

Por teorema de Tales, \frac{\overline{CE}}{\overline{C'E'}} = \frac{\overline{CF}}{C'F} por lo que \frac{\overline{CE}}{W_1 - r \cos \alpha} = \frac{r \tan \alpha}{\frac{r}{\cos \alpha} - r \cos \alpha}, multiplicando en lo de la derecha numerador y denominador por \cos \alpha y simplificando el r queda \frac{\sin \alpha}{1 - \cos^2 \alpha} = \frac{\sin \alpha}{\sin^2 \alpha} = \frac{1}{\sin \alpha} así que finalmente queda que \overline{CE} = \frac{W_1 - r \cos \alpha }{ \sin \alpha}. Esto resiste un check de extremos a ver si no nos equivocamos: para \alpha = 0 se va a infinito, y para \alpha = \frac{\pi}{2} se va a W_1, que se corresponde con el dibujo.

Por simetría al ser lo mismo pero del otro lado, tiene que ser sin hacer las cuentas \overline{CD} = \frac{W_2 - r \sin \alpha }{ \cos \alpha}. Así que la función final es

f(\alpha) = \frac{W_1 - r \cos \alpha }{ \sin \alpha} + \frac{W_2 - r \sin \alpha }{ \cos \alpha}

Que distribuyendo y escribiendo en términos de otras funciones trigonométricas podemos reescribir como:

f(\alpha) = W_1 \csc \alpha + W_2\sec \alpha - r (\tan \alpha + \cot \alpha)

Acá la demo fácil de que es unimodal sonriente sería si de hecho es convexa que es más fuerte, y la forma linda sería usar que suma de convexas es convexa (cosa que para unimodal no vale), pero si bien \csc, \sec, \tan y \cot son convexas en el [0, \frac{\pi}{2}], como aparecen restando esa parte de la cuenta es cóncava, así que la función en su totalidad es una cosa convexa más una cóncava, no queda clara la concavidad sin analizar más en detalle todo.

Por suerte tenemos el truco de que W_1 \geq r y W_2 \geq r, así que podemos separar

f(\alpha) = (W_1-r) \csc \alpha + (W_2-r)\sec \alpha + r (\csc \alpha + \sec \alpha - \tan \alpha - \cot \alpha)

Y como son no negativos los coeficientes W_1-r y W_2-r, esos primeros dos términos son convexos. Si justo la función específica del final, \csc \alpha + \sec \alpha - \tan \alpha - \cot \alpha resulta ser convexa, toda nuestra función queda suma de convexas así que es convexa y terminamos.

Habría que ver que la derivada segunda de esa cosa es no negativa en el intervalo [0, \frac{\pi}{2}], que según wolfram lo es y por lo tanto justamente es convexa. Pero no parece obvio y la cuenta ahí se pone fea, así que en cuanto a intuición no estamos mucho mejor que “por dibujito tiene pinta de ser unimodal”, pero al menos tenemos todo concentrado en esa función en particular específica, que está presente en el corazón de la función de costo en definitiva.

En cuanto a cómo variar \alpha si no vas a usar que es unimodal sino evaluar mucho y listo, si querés tener una cota de error necesitás acotar el módulo de la derivada de f. Ya que lo máximo que puede variar la función dentro de un intervalo de longitud L es L multiplicado por esa cota, y entonces eso te permitiría acotar tu error absoluto en las f que estás evaluando y elegirlo acorde a lo que pida el problema. Si estás metiendo un problema de esa manera confiando en que no da TLE ni problemas de precisión, es muy posible que lo puedas hacer por prueba y error hasta conseguir AC.

Acá en este problema de hecho la derivada al igual que la función se va a infinito al irse a \frac{\pi}{2} el ángulo (y a -infinito al irse a 0), pero esos valores están lejos de ser el \alpha óptimo, así que lo que tendríamos que acotar es el valor de f' pero cerca del \alpha óptimo que es lo que va a importar. Podríamos sacar algunas cotas para saber que \alpha no es tan extremo y separarlo de infinito y tener un lugar concreto para evaluar la derivada como cota, pero llegados a este punto es mucho mejor la solución que observa que es unimodal (de hecho convexa) y usa eso.

[santo]

El tema respecto a la cota en general de la versión que evalúa mucho es que si tenés la derivada clara como para acotarla bien, entonces podés evaluar la derivada, y podés directamente buscar el cero de la derivada haciendo búsqueda binaria. Lo de “evaluar mucho” rara vez es una solución “linda oficial” porque es medio raro tener una cota verdadera para el error sin tener al mismo tiempo una forma mejor de calcularlo.

[Joacru]

¡Genial ! Muchas gracias por la respuesta.
También se me había ocurrido poner las cuentas en función de \alpha sin embargo no encontraba forma de hacerlo.

Hasta este punto me quedó claro:

@santo

Que distribuyendo y escribiendo en términos de otras funciones trigonométricas podemos reescribir como:
f(α)=W_1\cscα+W_2\sec⁡α−r(\tan⁡α+\cot⁡α)

Y luego me pierdo, ¿por qué se puede hacer esto con f(\alpha)?:

@santo

f(α)=(W_1−r)\cscα+(W_2​−r)\secα+r(\cscα+\secα−\tanα−\cotα)

También veo que necesito otros conceptos para entender en totalidad. Si me pueden recomendar bibliografía de confianza y recomendable donde explorar estos temas como funciones convexas, wolfram, etc. estaría muy agradecido .

[santo]

“Wolfram” es simplemente preguntarle “concavity of [toda la cuenta]” y ver qué dice en https://www.wolframalpha.com/ [es una página de computación simbólica / álgebra computacional], que a mano hubiera sido hacer un montón de derivadas y estudiar la función fea resultante a ver el los ceros y evaluar el signo.

Sobre “¿por qué se puede hacer esto con f(α)?”, simplemente haciendo las distributivas de lo de abajo, da lo de arriba.

Sobre bibliografía, para las ideas centrales usadas acá no hay mucho más concepto que “si es convexo entonces es unimodal sonriente” y “si es cóncava entonces es unimodal triste”, y que en una función con derivada segunda, el signo de la derivada segunda te dice si en un tramo es toda convexa (derivada segunda positiva) o cóncava (derivada segunda negativa), y que “suma de convexas es convexa” es algo válido muy útil.

Para la práctica con muchas cuentas trigonométricas y estudio de funciones / derivadas se puede seguir cualquier texto bueno de cursos de análisis matemático, yo puedo comentar del que yo estudié para el examen libre de análisis del CBC que es muy bueno (el que se ve abajo) pero no es único de ninguna manera, los mismos temas están en muchos libros o en internet y es más que nada practicar. Sobre todo enfocando específicamente en programación competitiva es overkill, porque no se usa tanto estudiar funciones a mano para sacar problemas (por ejemplo, en este problema de girar por los pasillos todo el estudio de la función se puede reemplazar por “esto intuitivamente es unimodal” y en una prueba de ICPC hubiera funcionado).

[Joacru]

Gracias por la respuesta.
¡Genial! No conocía esa web.
Respecto a la distributiva, ahí la vi .

@santo

Sobre todo enfocando específicamente en programación competitiva es overkill

Claro, en una competencia en tiempo real sería más eficiente confiar que ponerse a hacer todo esto jajaja, pero no me viene mal estudiar algo de análisis matemático para estar más seguro a la hora de resolver este tipo de problemas, más que nada para reconocer patrones.

Muchas gracias de nuevo por responder. Aprendí varias cositas y terminé de entender otras .