Tuenti Challenge 6 (quinta parte)

Viene de aquí.

Challenge 15 – Seat change!

En este problema tenemos que elevar una matriz, que representa una cadena de Markov, a una determinada potencia. A continuación hay que dar el mayor resultado que se encuentre en una fila dada. A priori el problema parece fácil: aunque el exponente sea grande, podemos aplicar exponenciación rápida para elevar cualquier matriz en un tiempo proporcional al logaritmo del exponente, y al cubo del lado de la matriz, que al ser de hasta 50 es factible.

Sin embargo la cosa se complica. No nos piden el resultado con decimales, ni el resultado módulo un determinado número. Nos piden que calculemos toda la fracción, o como mínimo el último dígito del numerador y el último del denominador, lo que nos impide hacer aproximaciones, ya que lo que perderemos serán precisamente los últimos dígitos. Una tentación es trabajar con aritmética modular, módulo 10, pero de nuevo algo falla: tenemos que dar el último dígito del numerador y denominador de la fracción irreducible, lo que implica realizar divisiones por 2 y 5, si el numerador y denominador tienen factores comunes (como el denominador es 100^k no es posible que haya otros factores). Como sabemos, no se puede dividir entre 2 ni 5 módulo 10, y además no parece que haya una forma sencilla de calcular el máximo común divisor sin calcular explícitamente el numerador y el denominador.

Lo que hice entonces fue analizar el input a ver si encontraba algún patrón. Parece que algunos casos repetían la respuesta cíclicamente. Es decir, existen un k y n_0 tal que si n\geq n_0 entonces la respuesta para el exponente n es la misma que para el exponente n+k. Sin embargo en otros casos esto no es así, y por mucho que probara exponentes no encontraba ciclos. Había “casi” ciclos, es decir, secuencias que parecía que se repetían, pero que en un exponente concreto cambian. Entonces aumentaba el tamaño del ciclo, pero cuando más aumentaba el tamaño del patrón que buscaba, más tenía que avanzar para encontrar una repetición. Sin embargo en esos casos el exponente no era tan grande. Había casos de alrededor de 10.000 sin ningún tipo de patrón, y casos de alrededor de 100.000 en los que parece que acabaría habiendo un ciclo, pero por mucho que avanzábamos siempre había una diferencia.

Mi solución enviada consiste entonces en poner un límite, en mi caso 200.000. Si el exponente es menor lo calculamos entero. Si es mayor supondremos que habrá un ciclo. Para eso probaba con diferentes longitudes de ciclo, haciendo el mínimo común múltiplo del ciclo actual y un número que iba creciendo, y llegaba hasta 11. Me guardaba todas las respuestas y devolvía la más común, pero en los casos de la entrada la respuesta siempre era la misma, lo que me daba una cierta seguridad de que sería la respuesta correcta aun sin tener una demostración formal. El algoritmo es francamente lento en ambos casos: si el exponente es menor que 200.000 y calculamos la matriz completa tendremos cerca de 2.500 números de alrededor de 200.000 cifras, por muy rápido que los calculemos. Si el exponente es mayor que 200.000 igualmente probamos con longitudes de ciclo muy grandes para asegurar, por lo que también elevamos la matriz a números grandes, y además varias veces. El resultado es que la ejecución de mi algoritmo tardaba alrededor de un cuarto de hora, pero al menos la respuesta era correcta.

He estado revisando otras soluciones y todas son parecidas. Tratan de detectar ciclos, y si no lo consiguen elevan toda la matriz. El tiempo de ejecución también es de varios minutos, aunque he visto buenas ideas que reducen el tiempo. En primer lugar tratan de buscar un ciclo en las matrices. Es evidente que si las matrices se repiten llegadas a un cierto punto esto da una demostración correcta de que hay un ciclo, ya que cada matriz se obtiene únicamente de la anterior. Esto no es necesariamente cierto si lo que se repiten es únicamente las últimas cifras del numerador y del denominador. En efecto, no obtenemos la misma fracción sumando 1/2+1/2 que 11/2+1/2, ni siquiera los mismos finales. Sin embargo hay casos en los que aparentemente hay ciclos en las cifras y no en las matrices, por lo que habría que jugársela a suponer que el ciclo se producirá siempre sin demostración, o bien calcular toda la matriz, teniendo en cuenta que el exponente llega a 10^8. Otra mejora consiste en no calcular toda la matriz, sino únicamente la submatriz de los estados a los que podemos llegar. Es evidente que si no podemos llegar a un estado no es necesario ni siquiera tenerlo en cuenta. Esto también acelera algunos casos, aunque claro, en caso peor podría ser que pudiéramos acceder a toda la matriz.

Entonces la pregunta es, ¿es posible encontrar un método general, que valga para cualquier matriz y para cualquier exponente? Pues, a falta de que alguien me lo desmienta, ahora mismo estoy bastante convencido de que no existe, y de que la solución esperada consiste en analizar todos los casos, y ver si o bien existe un ciclo, o bien la matriz es pequeña, o bien el exponente es pequeño. En todos los casos de la entrada se producen una o más de estas situaciones, lo que es un indicio de que efectivamente no existe solución general. Vamos a analizarlos uno por uno.

testInput casos 1 y 2

Estos casos se corresponden con un único estado que nunca abandonamos. Por tanto hay un ciclo de longitud 1 y de hecho la respuesta será siempre de 1/1.

testInput casos 3, 4 y 5

La submatriz generada por estos casos y el autómata correspondiente son los siguientes:

\left[\begin{array}{ccc}0&100&0\\0&0&100\\100&0&0\end{array}\right] automata1

Es fácil de ver que el estado se repite cíclicamente cada tres iteraciones. Por tanto hay un ciclo de longitud 3. La respuesta será de 1/1, pero el estado dependerá del estado inicial y del exponente.

testInput casos 7 y 8

Dejamos el caso 6 para más adelante. La submatriz generada por estos casos y el autómata correspondiente son los siguientes:
\left[\begin{array}{cc}50&50\\50&50\end{array}\right]automata2
Aquí se puede ver que el estado no depende del estado anterior. Por lo tanto ciclo es de longitud 1. La respuesta es 1/2, y como puede ser cualquier estado se elegirá el de mayor índice.

testInput casos 9, 10 y 13

La submatriz generada por estos casos y el autómata correspondiente son los siguientes:
\left[\begin{array}{cc}50&50\\100&0\end{array}\right]automata3
Es decir, si estamos en el estado A tenemos un 50% de proababilidades de quedarnos, y un 50% de pasar al estado B y volver inmediatamente al estado A. Aquí la existencia de un ciclo no es tan evidente. De hecho la matriz nunca es cíclica: convergerá a la distribución límite (2/3 de estar en el primer estado, 1/3 de estar en el segundo), pero nunca la alcanzará, por lo que la última cifra del numerador y denominador puede variar. Tenemos que tirar de artillería pesada. Como el factor común es 50, consideramos la matriz en la que dividimos todos los valores por 50. La respuesta final será el resultado de dividir la primera posición de la matriz elevada al exponente, entre 2 elevado al exponente. Como la matriz es pequeña podemos hallar una fórmula explícita para dichos valores. Los valores propios de la matriz son 2 y -1, por lo que hay una solución de la forma a2^n+b(-1)^n. Probando valores descubrimos que a=2/3, y b=1/3. Por tanto la fórmula exacta para el numerador es {2\cdot 2^n+(-1)^n \over 3}. Además es fácil de ver que dicho número siempre es impar, por lo que el factor común con el denominador siempre será 1. Es decir, que la respuesta que buscamos es la última cifra de {2\cdot 2^n+(-1)^n \over 3} entre la última cifra de 2^n, o lo que es lo mismo, los respectivos resultados módulo 10. Sabemos que 3 es coprimo con 10, por lo que no afectará a la búsqueda de un ciclo. La última cifra de 2^n se repetirá cada \varphi(10/mcd(10,2))=4 operaciones, y la de (-1)^n también se repetirá cada \varphi(10/mcd(10,9))=4 operaciones, donde \varphi es la función phi de Euler. Por lo que tendremos un ciclo de longitud 4.

testInput casos 6, 11, 12 y 17

La matriz de los casos 6, 11, 12 y 17 contiene el artefacto encontrado en el los casos 9, 10 y 13, por eso la hemos dejado para después. La matriz y el autómata correspondientes son los siguientes:
\left[\begin{array}{cccc}100&0&0&0\\25&0&75&0\\0&0&50&50\\0&0&100&0\end{array}\right]automata4
Es decir, en el primer movimiento tenemos un 25% de probabilidades de quedarnos atrapados en el estado B, y un 75% de probabilidades de irnos al artefacto de los casos 9, 10 y 13. La probabilidad límite del estado B es del 25%, la del C de 2/3·75%, es decir, del 50%, y la del estado D del 25% restante. Es decir, que la respuesta para exponentes grandes será el estado C. ¿Y cuál es la probabilidad de estar en C? Pues es la probabilidad dada en los casos 9, 10 y 13 multiplicada por 3/4 (y reduciendo el exponente en 1, ya que partimos del estado A, pero eso no afecta a la búsqueda de un ciclo). Dijimos en el caso 9 que el numerador era {2\cdot 2^n+(-1)^n \over 3}, y el denominador 2^n. Si multiplicamos por 3/4 estaremos desplazando el denominador en 2, y eliminando el denominador /3 del numerador. Ninguna de las dos cosas afecta al ciclo, por lo que nuevamente tendremos que la longitud del ciclo es 4.

testInput casos 14 y 15

La submatriz generada por estos casos y el autómata correspondiente son los siguientes:

\left[\begin{array}{ccccc}0&40&30&30&0\\100&0&0&0&0\\0&0&0&0&100\\0&0&0&0&100\\100&0&0&0&0\end{array}\right]automata5
Aquí el estado C en realidad se corresponde con dos estados que son equivalentes a todos los efectos. Por eso la matriz tiene 5 filas pero sólo hay 4 estados. Dicho de otra forma, a cada momento hay un 40% de probabilidades de hacer un ciclo de longitud 2, y un 60% de probabilidades de hacer un ciclo de longitud 3. Eso significa que en todo momento podemos estar en cualquier estado, aunque a simple vista parece que en el límite el más probable será el A. Después de mucho buscar, no parece que haya ninguna forma de obtener ningún ciclo, y de hecho yo creo que ni siquiera existe. Si reducimos la matriz y calculamos sus valores propios obtenemos que dos de ellos son complejos. Existen formas de trabajar con números complejos en aritmética modular (por ejemplo, i es 3 módulo 10, ya que es la raíz de -1, es decir, de 9). Pero también hay divisiones entre 5, lo que sí que no está definido módulo 10. Sin embargo, los exponentes asociados a esta matriz son pequeños, así que la calcularemos directamente.

submitInput casos 1, 2, 10 y 11

Las matrices de estos casos son grandes y diferentes, pero el siguiente autómata representa conceptualmente el comportamiento de todas ellas:

automata6

Donde los estados C y E se corresponden en realidad con diferentes estados equivalentes. Es evidente que empecemos donde empecemos las probabilidades se repetirán cada cuatro movimientos, ya que habremos dado una vuelta al círculo. Por tanto la matriz tiene un ciclo de 4. De hecho dado que las probabilidades iniciales son del 50% se puede reducir el ciclo a 2.

submitInput casos 3 y 4

Estos casos se corresponden con los casos 3, 4 y 5 del testInput, aunque con un exponente mucho mayor. Como el ciclo es de longitud tres el tamaño del exponente no es importante en realidad.

submitInput caso 5

Este caso se define de la siguiente manera. Partiendo de un estado inicial, con un 80% de probabilidades vamos a parar a un artefacto como el de los casos 9, 10 y 13 del testInput, y con un 20% de probabilidades vamos a parar a un artefacto como el de los casos 1, 2, 10 y 11 del submitInput. Como tenemos un 80% de probabilidades de que suceda el primer evento, la solución final será la solución de los casos 9, 10 y 13 del testInput, pero multiplicada por 4/5. Aquí podemos aplicar una estrategia parecida a la de los casos 6, 11, 12 y 17 del testInput, pero hay una particularidad. Recordemos que la fórmula general de la secuencia del denominador era {2\cdot 2^n+(-1)^n \over 3}, y la del denominador 2^n. Al multiplicar por 4/5, por un lado dividimos el denominador entre 4, pero eso no afecta a la longitud del ciclo. Por otro lado, si el numerador es múltiplo de 5 lo dividimos entre 5, y si no multiplicamos el denominador por 5. Aquí es donde viene el problema. Como la última cifra del numerador cicla cada 4 veces, se puede comprobar que en una de cada 4 veces la última cifra será 5, y por tanto será múltiplo de 5. Y el problema es que no se puede dividir entre 5 módulo 10. Necesitamos saber más información. De hecho, para saber la última cifra del resultado de dividir entre 5 necesitamos guardar el resultado módulo 50. Por tanto, la longitud del ciclo será el mínimo común múltiplo entre el ciclo de 2^n módulo 50, y el de (-1)^n módulo 50. El ciclo de 2^n módulo 50 es el mismo que el de 2^n módulo 25, y al ser primo podemos aplicar el teorema de Euler, que nos dice que la longitud del ciclo es \varphi(25)=20. El ciclo de -1 siempre es 2. Como el ciclo del denominador es 4, el mínimo común múltiplo de todos los ciclos es 20, por lo que la respuesta se repetirá cada 20 movimientos.

submitInput caso 6

Se corresponde con los casos 7 y 8 del testInput, pero con un exponente mucho mayor. Como el ciclo es 1 el tamaño del exponente no es importante.

submitInput caso 7

Se corresponde con los casos 9, 10 y 13 del testInput, pero con un exponente mucho mayor. Como el ciclo es 4 el tamaño del exponente no es importante.

submitInput casos 8 y 9

Se corresponde con los casos 14 y 15 del testInput, pero con un exponente mayor. Como no hemos encontrado ningún patrón no hay más remedio que calcular toda la matriz. Sin embargo la matriz es pequeña, de tamaño 5×5, y el exponente es menor que los de los otros subcasos, del orden de 10^5. Esto hace que con unas pocas modificaciones de bajo nivel, como precalcular el máximo común divisor de la matriz y dividirlo antes de empezar a elevar, obtengamos la respuesta en pocos segundos.

submitInput casos 12, 13, 14 y 15

En este caso las matrices son totalmente aleatorias, y el número de ceros es pequeño. No tenemos más remedio que calcular toda la matriz. Sin embargo, la submatriz correspondiente es de tamaño mediano, de 19×19, y el exponente es bastante más pequeño que en los otros subcasos: 8.192. Eso significa que podemos obtener el resultado final en pocos segundos.

Por lo tanto, el algoritmo general que lo resolvería sería el siguiente. Si el exponente es menor que 200.000, calculamos la potencia de la matriz completa, con unas pequeñas modificaciones para que vaya algo más rápido: por un lado elevar únicamente la submatriz de estados alcanzables, y por otro calcular el máximo común divisor de dicha matriz y dividir todas las entradas por ese valor antes de empezar a elevar. Si el exponente es mayor que 200.000 hemos demostrado que en todos los casos hay un ciclo. El mínimo común múltiplo de todos los ciclos encontrados es de 60, por lo que en lugar de elevar la matriz al exponente dado, la elevaremos al exponente módulo 60, más 60 por si hay algo de ruido inicial. He hecho un programa que implementa este algoritmo, llamado 15alternative.py. Lo he subido al repositorio, y da la respuesta correcta en medio minuto. Se pueden hacer algunas modificaciones específicas más, como elevar la matriz aleatoria a 8.192 una sola vez, lo que probablemente dé la respuesta final en menos de 10 segundos, pero ya me parecía suficiente.

Espero que después de leer esto quedéis tan convencidos como yo de que la solución esperada es esta. Si existiera un algoritmo general seguramente las matrices aleatorias serían más grandes que 19×19, y el exponente sería mayor que 8.192.

Challenge 16 – Give me the password, superuser

En este problema hay un servicio ejecutándose que pide una contraseña. Para tratar de averiguarla nos dan el ejecutable que utiliza el servicio para saber si la contraseña dada es correcta o no. Nuevamente no podemos acceder a la IP que nos dan desde el navegador, sino que hay que hacerlo desde telnet o mediante un socket. Pero el resultado es el mismo: nos piden una clave, y escribamos lo que escribamos nos dice que la contraseña es inválida. Tocará desensamblar el código.

El programa es un ejecutable ELF en 64 bits. Hay cierta información sobre el programa que lo compiló, y se pueden ver algunas cadenas de texto que dan algunas pistas: /dev/urandom, socket(), solution.txt, fwrite, strlen, recv… A ver si descubrimos cómo interactúan. Al intentar ejecutar el código no se consigue ningún resultado, debe hacer una comprobación inicial que no permite pasar a la parte importante. Desensamblándolo se puede ver que hay una función que usa las funciones principales: read, write, strcmp… Debe ser esa. Vamos a intentar entenderla.

Tras usar varias herramientas para descompilarla se puede empezar a intuir lo que hace. Primero abre un socket con unas ciertas opciones que no he conseguido entender. Después lee 8 caracteres del dispositivo /dev/urandom, que por definición es aleatorio. A continuación lee la clave que le enviamos a través del socket, y compara los 8 primeros caracteres con los que ha leído al azar. Si coinciden lee el archivo solution.txt y te da la clave, aunque por otro lado hay una variable que tiene que estar a 1 para que te dejen pasar. No sé lo que es, pero de momento ya es bastante difícil tratar de adivinar una clave aleatoria. Luego vamos a ello.

En principio no hay forma de adivinar el contenido de urandom (es la gracia). Pero investigando más a fondo vemos que hay una debilidad que se puede explotar. Pese a que la clave y el contenido de urandom son de 8 bytes, ¡la función recv recibe 64 bytes de la entrada! Comprobamos que es cierto: al enviar 64 caracteres por telnet el Python nos dice que la respuesta es errónea, pero al enviar 65 se cierra antes de que podamos seguir. Vemos a qué distancia están situadas la variable con la clave enviada, y la variable con el contenido de urandom… ¡16 posiciones de memoria! Eso quiere decir que si enviamos una clave de, por ejemplo, 24 bytes, los ocho últimos sobreescribirán el contenido leído de urandom, y podremos conseguir que se compare a igual a lo que hemos enviado.

La solución, por tanto, parece que es sencilla: mandar una clave con 24 o más caracteres iguales. Pero me extraña: cualquiera podría acertarlo si se pone a enviar claves al azar, y no es lo que se espera. En efecto, al enviar 24 caracteres ‘a’ no obtenemos la respuesta que buscábamos. Ni 30, ni 60, ni 64, ni 65… algo falla… pero tiene que ser esto, por fuerza. Pensemos…

¡La variable! Había una variable que tenía que estar a 1. A ver a qué distancia está de la posición de memoria donde se recibe la clave… ¡60! ¡Lo tenemos! No sólo hay que enviar caracteres iguales, sino que que tienen que ser unos. Enviamos 60 caracteres de tipo ‘\1’… nada… ¡La variable es de tipo int! Eso quiere decir que el entero 1 es en realidad cuatro caracteres ‘\0\0\0\1’. Volvemos a enviar… nada… ¡La endianness! Enviamos secuencias de ‘\1\0\0\0’… ¡Correcto! Obtenemos la contraseña que buscábamos y avanzamos al siguiente nivel.

Challenge 17 – Mountain Trip

Volvemos a los problemas algorítmicos clásicos. En este problema tenemos un vector de enteros, que representan las alturas de una montaña, y tenemos que encontrar la ruta óptima siguiendo una serie de criterios. En seguida podemos ver de qué se trata el problema en realidad: consideramos la secuencia de las diferencias, es decir un vector de N-1 posiciones en la que la posición i es el valor absoluto de la diferencia entre las alturas i e i+1. Nuestro objetivo es dividir dicha secuencia en K subsecuencias consecutivas, de forma que se minimice la suma máxima, en caso de empate que se minimice la longitud máxima, y en caso de empate que la secuencia de longitudes sea lexicográficamente lo menor posible.

Resolveremos este problema mediante una búsqueda binaria. En primer lugar minimizaremos la suma máxima que podemos obtener, en segundo lugar minimizaremos la longitud del intervalo más largo respetando la suma máxima, y en tercer lugar obtendremos la secuencia lexicográficamente menor que respete la suma máxima y la longitud máxima.

Es fácil de ver que la propiedad de “poder dividir la secuencia en K subsecuencias consecutivas de suma menor o igual que S” es monótona en S. Eso quiere decir que si se puede para un valor de S, entonces se puede para cualquier valor mayor, y si no se puede para un valor de S, entonces no se puede para ningún valor menor. Por lo tanto existe un valor de S tal que es posible dividir la secuencia en K subsecuencias consecutivas de suma menor o igual que S, pero no es posible para ningún valor menor que S. Ese es el valor que buscamos. Para encontrarlo aplicaremos búsqueda binaria. Sabemos que para S=0 no se puede, que para s=la suma total sí se puede, así que vamos a reducir el intervalo hasta que encontremos un S con el que no se pueda, pero que con S+1 sí. La búsqueda binaria consiste en probar con un valor intermedio, por ejemplo, S/2. Si es posible entonces el intervalo de búsqueda se reduce a [0,S/2]. Si no es posible se reduce a [S/2+1,S]. Vamos ejecutando el algoritmo hasta que el intervalo sea de un solo punto, y ese es el punto que buscamos.

Falta dar un algoritmo decisional que compruebe si, dado un S, es posible dividir la secuencia en K subsecuencias consecutivas de suma menor o igual que S. Esto es posible mediante un algoritmo greedy. El primer subintervalo será tan grande como podamos. Cuando superemos la S pasamos al segundo subintervalo, y así sucesivamente hasta que lleguemos al final. Si lo hemos podido hacer en K o menos subintervalos entonces es que es posible. Si no no.

Una vez que obtenemos la mínima suma máxima, vamos a tratar de buscar la mínima longitud máxima, pero restringiendo que la suma de cada subintervalo no sea mayor que la suma que hemos encontrado. La filosofía es la misma: con longitud 0 no se puede, con longitud N se puede seguro, y vamos a tratar de encontrar el punto exacto dividiendo el intervalo cada vez en dos. Falta dar un algoritmo greedy que diga si es posible dividir el intervalo en K subintervalos de longitud menor o igual a L y suma menor o igual a S. Pero lo podemos hacer igual que antes: en este caso pasaremos al siguiente subintervalo no solo si la suma es mayor que S, sino también si la longitud es mayor que L. Si lo hemos podido hacer en K subintervalos o menos es que se puede.

Finalmente, una vez calculados S y L, falta encontrar la división de intervalos que sea menor lexicográficamente. Se puede hacer fácilmente en tiempo cuadrático, pero vamos a intentar dar un algoritmo lineal. Haremos una pasada hacia atrás y otra hacia delante. En la primera pasada calcularemos, por cada posición, el mínimo número de intervalos en el que podemos dividir lo que falta sin que ninguno sume más de S ni tenga longitud más de L. Esto se puede hacer en tiempo lineal con el mismo greedy que antes: empezando desde el final vamos hacia atrás siempre que sea posible. Si nos pasamos en suma o en longitud es que necesitaremos un subintervalo nuevo. Una vez hayamos completado la lista hacemos otro recorrido hacia delante siguiendo el criterio contrario: si podemos pasarnos a otro subintervalo nos pasamos, pero antes tenemos que comprobar que los subintervalos que hemos recorrido hasta ahora, más los que nos quedan según hemos calculado antes, sean K. Si no tenemos que seguir avanzando. La respuesta dará evidentemente la menor en orden lexicográfico, ya que si no nos hemos pasado al siguiente subintervalo es porque no ha sido posible.

Este algoritmo tiene por coste el tiempo lineal del greedy multiplicado por el logaritmo de la búsqueda binaria. Es decir, O(N\log N). Como N puede ser de hasta 5.000, mi programa resuelve la entrada muy rápidamente, en menos de una décima. Sin embargo hay otros algoritmos más sencillos, cuadráticos, que dan la respuesta en menos de un segundo, lo que también es suficiente.

Sigue aquí.