Aventuras en el evaluador, parte 1

Como parte de los propósitos de año nuevo, me dispuse a hacer un refactor masivo del código con el cual se evalúan y ejecutan las soluciones en omegaUp. Habían muchas motivaciones para hacer la actualización: tener un sandbox más moderno, eliminar un montón de código duplicado, mejorar las pruebas, el logging, el paralelismo en los jueces, cómo se despliega el tiempo y la memoria, el desempeño de los envíos, soportar C++11 y más lenguajes. Son muchísimos cambios, así que haré dos posts explicándolos: este post se centrará en los cambios que se hicieron en la arquitectura de jueceo y el siguiente se enfocará únicamente en el nuevo sandbox.

El primer cambio que se va a notar es que el servidor donde se hospeda la página principal ya no califica envíos! Gracias a nuestros queridos empleadores, conseguimos un par de máquinas virtuales gratuitas con Linux en Azure que se utilizarán exclusivamente para correr programas de los concursantes. Estas máquinas son menos poderosas que el servidor que usábamos antes, pero gracias a que el nuevo sandbox tiene muchísimo menos overhead, la diferencia será casi negligible. Una de las consecuencias de esto es que la página va a ser un poco más responsiva y los veredictos serán más rápidos. Esto también trae seguridad, porque aunque quisieran hacer trampa, ahora será casi imposible: las máquinas donde se ejecuta código de concursantes ya no son las mismas máquinas donde están las salidas esperadas :).

Otro cambio grande es la manera en la que se mide y reporta la memoria que consumen los programas. Antes la ejecución del programa se detenía cada cierto tiempo para poder medir exactamente cuántos bytes estaban siendo utilizados. Ahora para bajar el overhead del sandbox, la política de medición es mucho más laxa y sólamente se toman en cuenta los bytes de memoria privada del programa: esto excluye la librería de C estándar, el código ejecutable del programa, y algunas constantes. En Java, la manera en la que se establece el límite de memoria no cambió (así que cualquier envío que fuera MLE antes lo seguirá siendo), pero ahora para que se vea más bonito el reporte, se excluye de la cuenta la memoria ocupada por la máquina virtual de Java. Hablando de Java, la causa #1 de errores de compilación antes se reportaba como Runtime Error: usar un nombre de clase que no es “Main”. Ahora se reporta como error de compilación y se te indica que la clase se debe llamar Main.

Todos los runtimes y compiladores fueron actualizados. Ahora usamos GNU GCC 4.8, Java OpenJDK 7.0, Free Pascal 2.6, Ruby 1.9, Python 2.7, Glorious Glasgow Haskell Compiler 7.6 y Karel 1.1. Soportamos ahora sí todos los features de Java 7 (bienvenido sea el operador diamante), y agregamos la opción para compilar en C++11 (posiblemente en un futuro eliminemos la versión anterior de C++, gnu++03, cuando el soporte de C++11 sea lo suficientemente maduro).

El bug más feo que se arregló fue uno en el cual si habían más de 2 jueces conectados, únicamente se usaban dos, desperdiciando mucho tiempo y poder de cómputo. Esto únicamente ocurría durante concursos muy grandes, pero era bastante molesto para nosotros. También habían muchos errores con el manejo de la cola de espera, tanto de los jueces para poder compilar envíos, como la de los envíos que esperan un juez disponible. El resultado es que donde antes habían esperas de varios segundos, ahora aún en periodos donde la cola está llena las máquinas que juecean estarán esperando únicamente ~20 milisegundos entre envíos en lo que se les asigna algo para hacer.

Después de aproximadamente 80 commits en nuestros varios repositorios, espero que disfruten nuestra nueva y mejorada infraestructura (que en realidad debería ser totalmente invisible si hice bien mi trabajo).

Solución a “Químicos”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 6
Autor:  Luis Héctor Chávez (lhchavez)
Fuente: Ethan Jiménez Vargas

Éste es un problema que tiene una solución elegante y determinística pero requiere algoritmos avanzados bastante complicados. Lo bueno es que es posible aproximar a la solución utilizando fuerza bruta mediante backtracking.

El problema nos pide encontrar una manera de asignar sustancias a los tubos y después mezclarlas con las dos operaciones disponibles (suma y diferencia absoluta) para terminar con un acomodo homogéneo de sustancias: la diferencia entre el tubo con más cantidad y con menos cantidad de sustancia debe ser lo más pequeña posible. Una manera de hacerlo es proponer un intervalo [a,b] y ver si es posible asignar sustancias y aparear los tubos de manera que la cantidad de sustancia resultante de la mezcla en todos los tubos esté contenido dentro del intervalo. Para acelerar el proceso, puedes elegir los intervalos haciendo una búsqueda binaria de acuerdo a su ancho b-a, porque a fin de cuentas lo que nos pide el problema es precisamente el ancho mínimo. Para cada intervalo propuesto [a,b], podemos hacer un grafo con 2N nodos (uno para cada tubo), agregando un arco entre dos nodos A y B si A+B\in[a,b] ó |A-B|\in[a,b]. Después, buscamos un apareamiento máximo) en el grafo: buscamos el conjunto de arcos con cardinalidad máxima tal que cada nodo tenga a lo más un arco incidente. Esto se puede encontrar con el algoritmo de Edmonds (también conocido como el Blossom algorithm por la forma de los ciclos de longitud impar) en tiempo O(|2N|^4), lo cual encontraría todas las soluciones en solo un par de segundos.

Lamentablemente la implementación del algoritmo de Edmonds es bastante complicada. Como este es un problema de solo-salida y todo se vale, en vez de hacer el intento por implementarlo, utilicé la librería Boost de C++ que ya tiene muchísimos algoritmos de grafos ya implementados.

Ahora, si no se te ocurre usar el algoritmo de Edmonds o no tienes acceso a Boost, aún así puedes obtener una cantidad decente de puntos usando una heurística: podemos intentar hacer un apareamiento máximo usando fuerza bruta, rindiéndonos si el problema suena muy complicado y asumimos que no existe un apareamiento. Una fuerza bruta naïve con un contador que se decrementa cada vez que se llama la función de búsqueda es más que suficiente. Haciendo un par de modificaciones al algoritmo anterior nos da una solución que nos da el 80% de los casos bien:

Claro que si te quieres ver greedy, puedes subirle al número de intentos, pero posiblemente no haya suficiente tiempo en el concurso para que termine. Si llegas a utilizar estas técnicas “impuras”, asegúrate primero de obtener cualquier solución que te de puntos antes de subirle para encontrar mejores respuestas.

Solución a “Crucero”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 4
Autor: Saúl Germán Gutiérrez Calderón
Fuente: USACO Enero 2009 Gold

Como se puede notar, al trazar la ruta óptima del crucero se está desperdiciando mucho espacio, y daría lo mismo si expandiésemos la isla para que no se desperdiciara espacio entre la ruta y la orilla de ésta.


Si supiéramos cual es la ruta óptima del crucero para expandir la isla bastaría con hacer un Flood Fill para rellenar los espacios con agua que quedan dentro de la ruta.

Resulta que el flood fill e puede hacer aun sin conocer cuál sería la ruta óptima. Si nos ponemos a hacer todos los tipos de celdas adyacentes a la celda actual en un flood fill, nos toparemos con que solo hay 2 que permiten que la isla crezca y 1 que evita que se expanda. El resto de las celdas adyacentes no nos dice nada acerca de si tenemos que poner algo ahí o no (de momento).

Si se pone un pedazo de isla nuevo en el centro de las figura de abajo, entonces la cosa peligrosa tendría que ser rodeada de alguna manera para poder pasar, lo cual nos llevaría a tomar una ruta mas larga. Por ello, no es una buena idea poner un pedazo de isla ahí.

Si es como la de la figura de abajo,

ambos caminos tienen la misma longitud. Por ello, se puede poner un pedazo de isla ahí y esto nos simplifica el problema.

La ruta óptima no puede pasar por el cuadro del centro ya que esto sería un desperdicio de tiempo, por lo cual podemos expandir la tierra ahí.

Entonces, sólo hay que hacer todas las expansiones de tierra hasta que ya no se pueda más y después de esto se puede hacer una mano derecha para buscar la orilla de la isla que al mismo tiempo será la ruta óptima.

Solución a “Mocha Hojas”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17
Autor: Freddy Román Cepeda
Fuente: Alberto José Ramírez Valadez

Para simplificar el análisis, podemos notar que la respuesta que nos piden es igual al total de los pesos de las hojas del árbol menos el total de los pesos de las hojas del árbol ya balanceado. De ahora en adelante, trataremos el problema como si tuviéramos que conseguir este segundo valor, en vez del número de operaciones. Entonces queremos maximizar el peso total del árbol balanceado, para minimizar la cantidad de operaciones.

Consideremos el caso de un árbol con un solo nivel. Ya que sólo podemos restarle a los pesos de las hojas, evidentemente el peso máximo del árbol se alcanza cuando se emparejan todas las hojas al peso de la hoja con peso mínimo.

Ahora, consideremos un árbol con dos niveles. Si la raíz tiene k hijos, para cada hijo i sea h_i el subárbol de i, b_i el número de hojas de h_i, y c_i el peso del árbol obtenido de realizar el procedimiento del párrafo anterior a h_i. Si todas las c_i son iguales, entonces nuestro árbol está balanceado. De lo contrario, debemos restar aún más para poder balancearlo. Sin embargo, también necesitamos que cada h_i continúe estando balanceado. La única manera que le podemos restar peso a h_i sería restarle la misma cantidad de peso a cada una de sus hojas. Entonces, a cada h_i sólo podemos restarle peso en múltiplos de b_i. Como queremos maximizar el peso del árbol resultante, necesitamos encontrar el número más grande x tal que a todos los c_i les podamos restar un múltiplo de su respectivo b_i para obtener x. Notemos también que c_i es un múltiplo de b_i porque los nodos internos del árbol no tienen peso. Si m es el mínimo común múltiplo de todos los b_i, entonces x también es un múltiplo de m. Entonces, el máximo x posible es igual al múltiplo de m más grande que sea menor o igual a todos los c_i. Por lo tanto, el valor máximo obtenible del árbol completo es igual a kx. Por último, si tuviéramos que restarle más peso a este árbol pero mantenerlo balanceado, es evidente que lo menos que podemos restar para mantenerlo balanceado es km, y si seguimos restando km continuará balanceado.

De esta observación podemos obtener la solución para cualquier árbol. Reusando la notación del párrafo anterior, k es la cantidad de hijos de la raíz, h_i el subárbol del iésimo hijo, y c_i el peso del árbol obtenido de realizar recursivamente el procedimiento de éste párrafo a h_i (o el del anterior si h_i tiene 2 niveles). Ahora b_i es igual a lo mínimo que le podemos restar a h_i y que continúe balanceado. El análisis del párrafo anterior también es correcto para la nueva definición de b_i y c_i.

El código siguiente implementa esta solución:

Solución alternativa a “Decepción”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8
Autor: Freddy Román Cepeda
Fuente: Ethan Jiménez Vargas

Esta es una solución alternativa al problema. La solución pensada originalmente consiste en una búsqueda podada. Sin embargo, esta solución corre en tiempo y memoria O(N^2), mucho mejor de lo necesario para obtener todos los puntos.

Podemos dividir el problema a la mitad con una observación simple: la torre más alta debe verse desde ambos lados. Además, no dejará que el resto de las torres que ocurren después de ella se vean. Podemos aprovechar este hecho para separar el problema en dos partes: izquierda y derecha. Si f(n,m) cuenta de cuántas maneras se pueden poner n torres de tal manera de que sólo m se pueden ver de un lado, la respuesta que queremos es \sum_{i=0}^{N-1} ({N-1 \choose i} * f(i,F-1) * f(N-i-1,B-1)).

En otras palabras, esta expresión es la suma de las maneras de cumplir las condiciones originales del problema colocando la torre más alta en la posición i. Es decir, hay {N-1 \choose i} maneras de distribuir el resto de las torres a la izquierda o derecha de la torre más alta (porque la única cosa que importa es el orden relativo de las torres y todas las alturas son distintas), las cuales multiplicamos por las maneras de hacer que se cumpla la condición sobre el lado izquierdo y lo mismo con el lado derecho.

Ahora, para computar f, podemos reusar la misma observación. Cuando colocamos la torre más alta en el índice i, cualquier torre que pongamos después de i ya no se podrá ver. Del lado visible, necesitamos reordenar las torres restantes de tal manera que sólo se puedan ver m-1. Además, podemos reordenar el lado oculto de la manera que queramos. Con esto tenemos que

f(0,0) = 1
f(n,m) = \begin{cases}  0 & \text{si } m > n\\  \sum_{i=0}^{n-1}({n-1 \choose i} * f(i,m-1) * (n-i-1)!) & \text{de lo contrario}    \end{cases}

con lo que resolvemos el problema en tiempo O(N^3) y memoria O(N^2).

Esto se puede mejorar aún más observando que f(n,m) está computando los números de Stirling de primera clase, para los cuales hay una recurrencia que se puede utilizar para calcularlos en tiempo O(N^2).

Los números de Stirling de primera clase cuentan las permutaciones de n elementos con m ciclos. Considere una permutación con m ciclos de los n edificios. Cada ciclo debe tener un elemento máximo. Además podemos ordenar los ciclos entre sí por su elemento mayor. De esta manera, tenemos m edificios visibles. Ya que estamos contando todas las permutaciones con m ciclos, cada posible ordenamiento con m edificios visibles será considerada. Esto se debe a que cada ciclo tiene únicamente un ordenamiento en el cual sólo uno de sus elementos es visible: el que comienza con el edificio más grande.

Aquí está el código que implementa esta solución.

Solución a “Panoramas”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17
Autor: Miguel Ángel Covarrubias
Fuente: Miguel Ángel Covarrubias

El problema es un Steiner tree problem (un MST pero donde sólo hay que conectar un subconjunto de nodos) pero con costo por nodo en vez de por arista. El grafo de los panoramas es un árbol más un ciclo. Para un árbol una solución es poner como raíz a s_1 y para cada s_i marcar los nodos en su camino hacia la raíz. Se puede usar DP o recursión para calcular el mínimo numero de vertices que conectan todos los nodos interesantes y pasan por la raíz para cada subárbol.

\mathrm{dp}_r=\mathrm{interesante}(r)\  \mathrm{si}\ \Sigma_h\mathrm{dp}_h=0
\mathrm{dp}_r = \Sigma_h\mathrm{dp}_h+1\  \mathrm{si}\ \Sigma_c\mathrm{dp}_h>0

h es un hijo de r. La arista extra (u,v) en el ciclo c permite usar otros caminos a lo largo de c. Tales caminos deben conectar todos los nodos en c que tengan nodos interesantes en su árbol después de quitar las aristas del ciclo E-c. Etiquetemos tales nodos con un uno y los demás nodos del c con un cero. Para E-(u,v) el ciclo sólo no cubre los últimos ceros. Para encontrar la solución sólo basta encontrar la secuencia de ceros más grande.
En el siguiente diagrama, la arista que falta es (u,v). La DP sólo no usa el último cero, pero es mejor no usar los dos ceros que están adyacentes.

  0 1
 /   \
1     0
 \   /
  1-0

Este código implementa la solución.

Seguridad: IE en Windows XP

Debido a un reciente cambio para mejorar la seguridad de la conexión a omegaUp, hemos decidido dejar de soportar oficialmente IE en Windows XP, a pesar de que sabemos que aún sigue siendo el segundo sistema operativo más común a nivel mundial[1]. Si aún están obligados a usar Windows XP, por favor utilicen algún navegador moderno (Chrome, Firefox u Opera) o alguna versión portátil.

Para los interesados, el cambio consistió en hacer un par de optimizaciones para nginx[2], para reducir el tiempo de espera al primer byte, y actualizar la configuración de TLS: se quitaron SSLv2 y SSLv3 (que ya se consideran inseguros), se agregaron TLSv1.1 y TLSv1.2, se eliminó RC4 como algoritmo de cifrado, y ahora se prefiere ECDHE como algoritmo de intercambio de llaves para proveer Perfect Forward Secrecy[3].

Referencias

  1. Reporte NetMarketShare, Enero 2014:
  2. Optimizing NGINX TLS Time To First Byte (TTFB) – igvita.com
  3. Perfect Forward Secrecy – Wikipedia