Matcom Online Grader

MOG Round #4 - Sketches by rlac 11 years, 10 months ago

Durante la 4ta competencia del MOG surgieron algunos inconvenientes:

1. Los juegos de datos del problemas F estaban mal. Mala mía, lo que pasó fue que los generadores de los juegos de datos no comprobaban que los puntos de entrada estuvieran sobre el borde del rectángulo.

2. Error en el enunciado del problema D. En la descripción del problema dice "Como se puede ver, solamente dos de sus hijos (1 y 4) van a poder heredar el trono.", cuando en realidad los hijos son (2 y 4). Por suerte, este error no causó problemas.

3. El problema C tenía demasiados ejemplos de prueba. Debido a esto, puede que algunos concursantes mandaran soluciones correctas sin saber por qué funcionaban en realidad.

Espero que para próximas competencias no ocurran estas cosas.

Por otra parte, ocurrieron hechos sobresalientes:
1. Tenemos el primer concursante rojo, leandro , resolviendo 5 de 6 problemas obtuvo el primer lugar de la competencia. Muchas felicidades para él, en verdad se lo merece.

2. El usuario Sandor puso un nuevo record de envíos incorrectos al mismo problema (14). Creo que va a ser difícil superar esto :).

3. Llegamos a la cifra de 20 usuarios que han competido al menos una vez en el sitio. Espero que en próximas competencias estos números aumenten considerablemente.

A continuación se exponen algunas ideas para resolver los problemas. Lejos de ser demostraciones formales, lo que se quiere es que cuando vean los códigos de las soluciones oficiales, sepan cual es la idea que se está implementando.

Detector de id
La idea en este problema no es tratar de encontrar todos los posibles errores que pueda tener una cadena para que no sea válida, sino que debemos ir reconociendo cada una de las partes del identificador. Es un poco complicado explicar en detalle cómo hacer esto y además la solución oficial está bastante clara, por lo que se puede coger la idea mirando el código.
Solución en C++

Conjuntos disjuntos
Este fue, sin dudas, el problemas más difícil; no tuvo ni un intento de solución durante la competencia. Ahora se presentan soluciones que van a aportarle mucho a todos.

Solución 1 (Array persistente)
De manera general, una estructura de datos persistente es una estructura que no se modifica. En el caso de un array, si queremos cambiar el valor que hay en una posición determinada de un array persistente, el array original no se modifica, sino que se devuelve otro array con los mismos valores que el inicial. Por ejemplo:

a1 = {2, 5, 1, 7}

y queremos cambiar el 2do elemento por un 4, entonces tendremos:

a1 = {2, 5, 1, 7}
a2 = {2, 4, 1, 7}

Si tenemos esta estructura de datos implementada eficientemente, entonces el problema se reduce a implementar una estructura de conjuntos disjuntos clásica, solo que el array sobre el cual va a operar va a variar por las distintas versiones del array persistente que tenemos.

Una explicación detallada de cómo implementar esta estructura sería demasiado larga, por lo que solamente voy a dejar algunas ideas para que después puedan entender el código.

La idea es representar un array como un árbol binario, donde cada nodo va a tener 2 campos, y a cada una de las hojas va a corresponder un índice del array:

lch: hijo izquierdo
rch: hijo derecho
val: en caso de ser una hoja, este es el valor del array en el índice que le corresponde al nodo. Cabe destacar que en la implementación que se da en la solución oficial este campo no existe, sino que cuando un nodo es una hoja, lch = rch = al valor correspondiente a val.

Creo que esta información es suficiente para que entiendan el código.
Solución en C++

Solución 2 (dfs)

¿dfs, en serio? ¿dfs en qué?
Si pensamos un poco (o bastante), podemos ver que las versiones forman un "árbol dirigido", si consideramos como vértices las versiones y va a existir una arista dirigida de v1 a v2 si la versión v2 se obtuvo a partir de la versión v1.
En este árbol, a cada vértice podemos añadirle como campo la lista de preguntas que se hacen sobre la versión que le corresponde.

La idea entonces es hacer un dfs sobre la raiz del árbol (correspondiente a la versión 0), responder las preguntas sobre esta versión y después hacer un dfs por cada uno de sus descendientes. La invariante que se debe mantener en este dfs es que en el momento en el que se está procesando una versión determinada, el array sobre el cual se hacen las operaciones de la estructura de conjuntos disjuntos esté en el estado correcto.
A continuación se exponen dos soluciones que implementan esta idea, pero la primera de ellas da TLE. Si observamos detenidamente, la única diferencia entre ellas dos es la forma en la que se representa el árbol, y sin embargo la diferencia de tiempo es abismal. Moraleja, los vectores de C++ son bastante lentos!!! , así que traten de usarlos lo menos posible.

Solución1 en C++
Solución2 en C++

Dibujando triángulos
La casilla superior izquierda se puede colorear de 4 formas. Cuando se fija esa primera casilla, cada una de las casillas que se encuentran a su derecha (en la primera fila) se puede colorear de 2 maneras, al igual que cada una de las casillas que se encuentran debajo de ella (en la primera columna). Una vez que se fijan la primera fila y la primera columna, entonces queda determinada la forma en la que se deben pintar los restantes triángulos, por lo que la solución final es 4 * 2 ^ (n - 1) * 2 ^ (m - 1) que es lo mismo que 2 ^ (n + m).
Solución en C++

Descendencia del rey
En este problema lo que se necesita es calcular la cantidad de sufijos propios de una cadena que son menores que ella.

La primera solución que se nos puede ocurrir es ordenar los sufijos utilizando cualquiera de la estructuras que existen para ello. Por supuesto, aquí se está computando información adicional ya que para resolver el problema no se necesita conocer el orden relativo de cada uno de los sufijos. Para evitar que pasen soluciones con esta idea se pusieron restricciones bastante grandes. Ni siquiera un suffix array en O(n) puede pasar los juegos de datos en tiempo.

Sea s la cadena de entrada, la solución final es:

Supongamos que tenemos computada una tabla 'pref' tal que:
pref[i] = prefijo común más largo entre el i-ésimo sufijo (sufijo que comienza en la posición i) y la cadena completa.

Como se puede ver, la relación de orden entre el i-ésimo sufijo y la cadena completa se puede describir por la relación de orden entre los símbolos s[pref[i]] y s[i + pref[i]]. Utilizando la observación anterior, tenemos que para calcular la cantidad de sufijos que son menores que la cadena completa podemos iterar por cada uno de ellos y contar la cantidad que sean menores.

La tabla 'pref' es conocida en la literatura como z-function. Para aprender como computarla en O(n), pueden consultar en la sección Documentación del sitio el libro Algorithms on Strings by M. Crochemore, C. Hancart and T. Lecroq a partir de la página 42 (52 del pdf).

El costo de la solución final es O(n)
Solución en C++

Tablero I
Es bastante complicado escribir una explicación formal para este problema, por lo que solamente voy a hacer una breve descripción (bastante incompleta) de la solución oficial.

Primeramente, como el tamaño del valor n es relativamente pequeño (hasta 12), podemos utilizar máscaras para resolver este problema, utilizando un entero mask que representa el estado de una columna del tablero (1 en el i-ésimo bit de su representación binaria indica que la i-ésima casilla ya está ocupada y 0 que está libre)

Podemos definir la siguiente tabla:
d[i][mask] = la cantidad de formas en que se pueden rellenar las primeras i columnas del tablero con las siguientes restricciones:

1. Todas las casillas de las primeras i - 1 columnas han sido cubiertas completamente.
2. En la i-ésima columna no hay fichas de dominó verticales.
3. La i-ésima columna está determinada por la máscara mask.
4. A la derecha de la columna i no hay ninguna casilla cubierta.

El caso base sería
dp[1][mask] = {1 si mask == 0; 0 en otro caso}

La función de transición sería algo así como (i > 1):
dp[i][mask] = sum(dp[i - 1][tmask]) para todo valor de tmask tal que tmask y mask sean compatibles.

Decimos que tmask y mask son compatibles si desde una configuaración del tablero en la que las primeras i - 1 columnas están completamente cubiertas y la i-ésima columna está representada por tmask (para un valor arbitrario de i, es decir, la compatibilidad de las máscaras es independiente del número de la columna), se puede llegar a una configuaración del tablero en la cual las primeras i columnas estén completamente cubiertas y la (i + 1)-ésima columna va a estar representada por mask (para esto puede que sea necesario rellenar los espacios vacíos de la i-ésima columna poniendo fichas verticales).

La respuesta final quedaría en dp[m + 1][0].

La cantidad de operaciones que se realizan está en el orden de O(m * 4 ^ n)
Solución en C++

Puntos sobre el rectángulo
Primeramente enumeramos los puntos con coordenadas enteras sobre el borde del rectángulo, a partir del punto (0,0) en contra del sentido de las manecillas del reloj. Se define id(p) como el número correspondiente al punto p en la enumeración. Ahora bien, para dos puntos p1 y p2 existe un camino que pasa por el punto (0,0) y otro que no (a menos que uno de los dos puntos sea el (0, 0).

La distancia del camino que no pasa por el (0, 0) es:
d1 = |id(p1) - id(p2)|   (|x| representa el valor absoluto de x)

La distancia del camino que pasa por el (0, 0) es:
d2 = 2 * (n + m) - d1

La respuesta al problema entonces es min(d1, d2). Como se puede ver, cada una de las preguntas se puede responder  en O(1)
Solución en C++

Bueno, esto es todo. Si quieren discutir alguna solución en particular, si tienen quejas o sugerencias, o etc, pueden poner comentarios con sus ideas.