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).

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

Introducción a omegaUp, parte 0

Hola!

Hemos recibido varias preguntas sobre cómo se envían soluciones a omegaUp. Decidí escribir una introducción a omegaUp, antes de empezar a aprender a resolver problemas. En resumen:

  • El objetivo de los concursos es acumular más puntos que todos los demás participantes. En caso de empate, se toma en cuenta la suma de los penalties (dependiendo del concurso puede no haber penalties, ser el tiempo desde que inició el concurso hasta que enviaste la solución o el tiempo desde que abriste el problema por primera vez hasta que lo resolviste).
  • Jamás se te quitarán puntos por intentar resolver un problema: si ya habías enviado una solución con x puntos, únicamente se cambiará tu puntuación y penalty si obtienes más de x puntos.
  • Toda la entrada y salida se hace mediante entrada estándar (“teclado” y “consola”), y no debes imprimir nada que no indique el problema: no debes poner cosas como “Dame un número”. omegaUp te proporcionará la entrada tal y como viene descrita en el problema.
  • Todos los problemas de Java deben tener Main como nombre de clase. Si usas cualquier otro nombre, te regresará un Runtime error.
  • cin (en C++) y Scanner (en Java) son relativamente lentos. En problemas donde haya mucha entrada, se recomienda usar scanf (en C/C++) y BufferedReader (en Java).
  • Toda la entrada y salida está en formato Unix: las líneas terminan con “\n”, no con “\r\n”.

Primero veamos cómo luce la arena durante un concurso:

El reloj de arriba, si es negativo, te dice cuánto tiempo falta para que inicie el concurso. Cuando es positivo, te dice cuánto tiempo falta para que termine el concurso. Una vez que llega a cero, el concurso se cierra y ya no puedes enviar problemas. Hay tres pestañas en esta vista:

  • Problemas: la que está mostrada arriba
  • Ranking: te muestra con una gráfica el progreso del top 10 del concurso con respecto al tiempo y también muestra el ranking general para el concurso. Esta información se actualiza casi en tiempo real, así que si no ves un cambio en el scoreboard, ten paciencia y en un par de minutos se reflejará. Ten en cuenta que en algunos concursos, faltando poco tiempo para el final (puede ser una hora o media hora), el ranking deja de actualizarse para meter más emoción =)
  • Clarificaciones: aquí puedes pedir clarificaciones específicas a la redacción de un problema, si algo no es suficientemente claro. Este no es el lugar para preguntar por qué cierto código no funciona (ese es el chiste del concurso! que tú sepas), así que evítate la molestia porque los jueces no te responderán. A los jueces les toma un poco de tiempo leer todas las clarificaciones y responderlas adecuadamente, así que ten paciencia. Ponte a resolver otro problema mientras. Nota: a veces verás que hay una nueva clarificación sin que tú hayas pedido una. Léela, porque es una clarificación global, o los jueces están intentando avisarte de algo.

En la sección de Problemas es donde pasarás la mayor parte del concurso. En la parte de la izquierda está la lista de problemas junto con dos números (como 0 / 100). Estos números indican cuántos puntos has acumulado en ese problema y cuántos puntos vale el problema en total. A menos que los casos estén mal y los jueces hayan decidido re-juecear todos los envíos de un problema, esos puntos no pueden bajar si haces más envíos a un problema. Abajo de la lista de problemas, hay un miniranking con los mejores 10 participantes. Faltando poco tiempo antes del concurso, esta tabla dejará de actualizarse, no te apaniques.

Cuando selecciones un problema, verás la descripción de ese problema. En la mayoría de los concursos, se te agregará un penalty entre más te tardes en resolver un problema desde que inicia el concurso o lo abres por primera vez, así que trata de resolverlo lo más rápido posible. Este penalty NO te quita puntos, y solo se utiliza en caso de empates.

Hasta arriba viene una tablita con varias cosas útiles, como la cantidad de puntos máximos que te dará ese problema cuando lo resuelvas, el límite de tiempo que tienes para resolver cada caso y el límite de memoria que tienes para resolverlo. Después viene la descripción del problema (que usualmente es una pequeña historia) y le descripción formal del problema, la descripción formal del formato de la entrada, la salida y algunos ejemplos que confirman la explicación. Algunos problemas también incluyen una sección con todos los límites de las variables expuestas en la descripción del problema. Si no entiendes algo del problema, siéntete libre de escribir una clarificación. Por último, encontrarás una pequeña tablita con todos los envíos que has realizado para ese problema

Puedes ignorar el ID, se utiliza únicamente por si algún juez te lo pregunta en caso de que haya problemas con el problema y haya necesidad de rejuecear envíos. Lo importante son las columnas de Puntos y Penalty. La información que aparece en el ranking toma en cuenta el envío que hayas hecho que tenga más puntos (y en caso de empate, el que tenga menos penalty). La columna de status son dos letras que te dan una pequeña pista de qué pasó con tu envío en general:

  • AC – Accepted. Tu envío resolvió correctamente todos los casos de prueba y obtuviste la máxima cantidad de puntos. Felicidades!
  • PA – Partially Accepted. Tu envío resolvió al menos un caso de prueba, pero hay al menos un caso que no resolviste correctamente. Intenta arreglar tu programa y vuélvelo a intentar.
  • WA – Wrong Answer. Tu programa no resolvió ningún caso correctamente.
  • TLE – Time Limit Exceeded. Al menos en uno de los casos, tu programa excedió el límite de tiempo. Intenta pensar en una solución más eficiente o busca en tu código si hay algún ciclo infinito.
  • MLE – Memory Limit Exceeded. El menos en uno de los casos, tu programa excedió el límite de memoria. Intenta pensar en una solución que utilice menos memoria. En C y C++, algunos MLE se pueden reportar como RTE, sobre todo si declaraste arreglos gigantes.
  • RTE – Runtime error. En al menos uno de los casos, tu programa tuvo un error fatal: puede ser una excepción en Java, no utilizaste “Main” como nombre de clase en Java, divisiones entre cero, desbordaste el stack, te saliste de los límites de un arreglo, etc. Vuelve a leer el problema y piensa qué casos se te olvió considerar y qué entrada puede hacer que tu programa se comporte de esta manera.
  • RFE – Restricted function. En al menos uno de los casos, tu programa intentó realizar una operación prohibida. En general, no puedes abrir ningún archivo, no puedes conectarte a internet, no puedes ejecutar otros programas y no puedes comunicarte con nada del sistema fuera del problema. Limítate a resolver el problema usando algoritmos.
  • CE – Compilation error. Tu programa no pudo ser compilado. omegaUp utiliza gcc y g++ en Linux, y usamos Java 1.6, así que podrían haber incompatibilidades entre tu ambiente de desarrollo y el que usamos nosotros. Si haces click en el botón de “Ver” el código, verás tu código seguido del error del compilador.
  • JE – Judge error. Un error interno de omegaUp. Esto no debería pasar nunca, pero si te sale, alguno de los jueces ya lo vio y lo resolverá lo más rápido posible, así que no es necesario que lo reportes. Intenta otro problema mientras tanto, y ten por seguro que no serás penalizado por ese envío, porque no fue tu culpa.
Como puedes darte cuenta, varios de los status no son mutuamente exclusivos. Siempre intentaremos el error más severo (los errores más severos están en la parte de abajo de esta lista), así que por ejemplo, si un envío te marca TLE y tienes algunos puntos, en ninguno de los casos detectamos un MLE ni un RFE, tuviste algunos casos bien, pero pudiste haber tenido otros casos mal y en al menos un caso excediste el límite de tiempo.

Si crees que tu programa está resolviendo bien el problema, deténte a pensar por qué podría estar mal. El 99% de las veces, el problema está bien (sobre todo si hay alguien más que ya lo logró resolver), pero si tienes evidencia que hay algún error en el problema (por ejemplo, si dice la descripción que no habrán números mayores a 1000, y en tu programa validas esto y haces que te devuelva un veredicto como MLE), por favor pide una clarificación con esta información y tu ID de envío para que los jueces lo revisen.

Ahora sí, estás listo para continuar con la parte 1 del tutorial de omegaUp.

 

Solución a “Comesolo”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8
Autor: lhchavez
Fuente: Félix

Este problema es especial porque es el primero en omegaUp de solo salida! Usualmente lo que debes esperar cuando te enfrentes con uno de esos problemas es que sea un problema NP que no tiene una solución rápida, y usualmente te pedirán que te aproximes lo más posible a la solución óptima. Esto significa que te vas a tener que valer de técnicas ad-hoc y heurísticas para sacar puntos.

La solución del problema es bastante sencilla de explicar: haz una búsqueda en profundidad intentando todos los posibles movimientos por fuerza bruta hasta que te salga una solución aceptable e imprímela. El problema es que esta estrategia es O(n!), y como n puede valer hasta 30×30, puedes esperar que el programa corra varios milenios antes de encontrar la solución óptima. Hay tres trucos (en orden de importancia) para obtener una solución decente en un tiempo razonable:

  • No repetir estados.
  • No “clavarse” con soluciones que parece que son muy buenas, pero en realidad llevan a callejones sin salida.
  • Encontrar una manera de darle prioridad a los estados que tengan más probabilidad de llegar a una solución buena.

La estrategia que yo personalmente seguí fue que cada que encontraba un nuevo estado, obtenía su hash (que resultaba en un entero de 64 bits) y verificaba si no lo había visitado usando una tabla de hash*. Si no la había visitado, encontraba todos los estados vecinos (todos los tableros que resultaban de hacer un movimiento válido) y los guardaba en una fila de acuerdo a la cantidad de puntos (entre más puntos, más adelante en la fila). Luego, elegía aleatoriamente un estado de la fila dándole prioridad a los que estaban más adelante (pues son los que tienen mayor probabilidad de llegar a una buena solución), lo cual también me evitaba seguir un único camino donde me podría atorar. Repetí eso hasta que se me terminó la memoria de la computadora e imprimí la mejor solución.

A continuación, el pseudocódigo de la solución:

class Estado:
  int puntos = 0
  bool[N][N] tablero
  Estado padre = null

  def __init__(Estado p):
    puntos = p.puntos
    tablero = p.tablero
    padre = p

  def hash():
    # Puedes usar cualquier algoritmo que genere un entero de 64 bits
    # a partir de tablero y puntos. Este es el más sencillo.
    hash = puntos
    for i in range(0, N):
      hash = ((hash << 7) | (hash >> 53)) ^ tablero[i]
    return hash

  def siguientes(queue[300] colas):
    # Para todas las celdas (i, j) del tablero...
    for i in range(0, N):
        for j in range(0, N):
          # Si la celda tiene una pieza...
          if tablero[i][j]:
            # Para todos los vecinos contiguos (i+k, j+l)...
            for k in range(-1, 2):
              for l in range(-1, 2):
                # Asegúrate que se haya movido _algo_.
                if k == 0 && l == 0: continue
                # Y que pueda brincar dentro del tablero.
                if j + 2 * l < 0 or j + 2 * l >= N: continue
                # Y que haya brincado una pieza.
                if not tablero[i + k][j + l]: continue
                # Y que el lugar a donde brinca esté desocupado.
                if tablero[i + 2 * k][j + 2 * l]: continue
                
                hijo = new Estado(this)
                # Aumenta la puntuación del hijo
                hijo.puntos++
                # Borra la ficha original y la "comida".
                hijo.tablero[i][j] = hijo.tablero[i + k][j + l] = \
                  False
                # Agrega la ficha en su posición final.
                hijo.tablero[i + 2 * k][j + 2 * l] = True
                # Agrégala a la cola correspondiente.
                colas[hijo.puntos].push(hijo)

def elige_estado():
  # Número aleatorio entre 0 y 1.
  r = (random() / (float)RAND_MAX)
  # El índice de la última cola que estuvo llena.
  ultimolleno = -1
  # La cola que se está considerando.
  x = 0
  # Elige la cola con mayores puntos que no esté vacía como
  # primera opción.
  for i in range(0, N):
    if not colas[i].vacio():
      x = i
  # La primer cola tiene probabilidad de 31% de ser elegida.
  # La segunda cola tiene probabilidad de 21%, la tercera 14%,
  # la cuarta 10% y así sucesivamente.
  while x >= 0:
    if not colas[x].vacio():
      ultimolleno = x
    x--
    r *= 1.45
    if r >= 1 and ultimolleno != -1 break
  if ultimolleno == -1: return Null
  return colas[lastfull].pop()

queue[300] colas
hashtable estados_visitados

# lee el estado original
colas[0].push(estado_original)
Estado mejor = estado_original

while no_se_haya_terminado_la_memoria():
  Estado s = elige_estado()
  # Si ya no hay más estados por visitar,
  # encontramos la respuesta óptima en algún punto.
  if s == Null: break
  # Actualiza |mejor| si hay una respuesta mejor.
  if mejor.puntos < s.puntos: mejor = s
  # Repetir estados es malo.
  if s.hash() in estados_visitados: continue
  estados_visitados.add(s.hash())
  # Agrega todos los vecinos.
  s.siguiente(colas)

# A partir de este punto, |mejor| contiene la mejor solución. Podemos
# saber qué movimiento se hizo para llegar a él comparando las
# diferencias entre el tablero de |mejor.padre| y |mejor|. Ya solo es
# cuestión de imprimir el resultado y listo.

* Aquí mucha gente se va a quejar porque solo guardar el hash abre la puerta a que haya dos estados que puede tener hasta 900 bits que tengan el mismo hash de 64 bits (por el principio del palomar) y esté considerando que ya se visitó un estado que en realidad es nuevo. Si haces las cuentas, la probabilidad de colisión es negligible: la cantidad de estados que podía visitar en mi computadora (27 millones) es significativamente más pequeña que el número de estados necesarios para que la probabilidad de colisión sea de 1% (\approx 10^{135}, por la paradoja del cumpleaños).