Resolver crucigramas japoneses a la velocidad de la luz

Los crucigramas japoneses (también nonogramas) son acertijos lógicos en los que se encripta una imagen de píxeles. Debe resolver el crucigrama utilizando números ubicados a la izquierda de las líneas y encima de las columnas.

El tamaño de los crucigramas puede alcanzar hasta 150x150. El jugador usa una lógica especial para calcular el color de cada celda. La solución puede tomar un par de minutos en crucigramas para principiantes y decenas de horas en rompecabezas complejos.

Un buen algoritmo puede resolver el problema mucho más rápido. El texto describe cómo escribir una solución que funcione casi instantáneamente utilizando los algoritmos más adecuados (que generalmente conducen a una solución), así como sus optimizaciones y el uso de características de C ++ (que reducen el tiempo de ejecución en varias decenas de veces).

En la versión móvil de Habr, es posible que no se muestren las fórmulas en el texto (no en todos los navegadores móviles): use la versión completa u otro navegador móvil si observa problemas con las fórmulas

Reglas del juego

Inicialmente, el lienzo de crucigramas es blanco. Para los crucigramas en blanco y negro, debe restaurar la ubicación de las celdas negras.

En los crucigramas en blanco y negro, el número de números para cada fila (a la izquierda del lienzo) o para cada columna (parte superior del lienzo) muestra cuántos grupos de celdas negras hay en la fila o columna correspondiente, y los números mismos muestran cuántas celdas combinadas contiene cada uno de estos grupos. Conjunto de números $$$[3, 2, 5]$ significa que en una determinada fila hay tres grupos consecutivos de $$$3$ , $$$2$ y $$$5$ celdas negras en una fila. Los grupos se pueden organizar en una fila al azar, sin violar el orden relativo (los números especifican su longitud y se debe adivinar la posición), pero deben estar separados por al menos una celda blanca.

Ejemplo correcto

En los crucigramas de color, cada grupo aún tiene su propio color; cualquiera, excepto el blanco, es un color de fondo. Los grupos vecinos de diferentes colores pueden estar uno al lado del otro, pero para los grupos vecinos de los mismos colores, aún es necesaria la separación de al menos una célula blanca.

¿Qué no es un crucigrama japonés?

Cada imagen de píxel se puede cifrar como un crucigrama. Pero puede que no sea posible restaurarlo de nuevo: el rompecabezas resultante puede tener más de una solución o tener una solución, pero no se puede resolver lógicamente. Luego, las celdas restantes en el juego tienen que adivinarse usando tecnología chamánica usando computadoras cuánticas .

Tales crucigramas no son crucigramas, sino grafomanía. Se cree que el crucigrama correcto es tal que de manera lógica puede llegar a una solución única.

La "ruta lógica" es la capacidad de restaurar cada celda una por una, considerando la fila / columna por separado, o su intersección. Si esto no es posible, el número de opciones de respuesta consideradas puede ser mucho, mucho más de lo que una persona puede calcular por sí misma.

El nonograma incorrecto es la única solución, pero es imposible de resolver normalmente. Naranja marcada con células "insolubles". Tomado de Wikipedia.

Esta restricción se explica de la siguiente manera: en el caso más general, el crucigrama japonés es un problema de NP completo. Sin embargo, adivinar no se convierte en una tarea completa de NP, si hay un algoritmo que en cada instante de tiempo indique inequívocamente qué celdas abrir más. Todos los crucigramas utilizados por humanos (excepto el método Montecarlo prueba y error) se basan en esto.

En la mayoría de los crucigramas ortodoxos, el ancho y la altura se dividen entre 5, no hay filas que se puedan contar instantáneamente (aquellas en las que las celdas de color obstruyen todos los lugares o no existen en absoluto), y el número de colores complementarios es limitado. Estos requisitos no son obligatorios.

El crucigrama equivocado más simple:

|1 1| --+---+ 1| | 1| | --+---+ 

A menudo, el pixel art codificado, que usa un patrón de "tablero de ajedrez" para simular un gradiente, no se resuelve al revés. Es mejor entender si escribe "gradiente pixelart" en la búsqueda. El gradiente es como este crucigrama fayl de 2x2.

Posibles soluciones

Tenemos el tamaño del crucigrama, una descripción de los colores y todas las filas y columnas. ¿Cómo puedo armar una imagen de esto:

Búsqueda completa

Para cada celda, clasificamos todos los estados posibles y verificamos que sean satisfactorios. La complejidad de tal solución para un crucigrama en blanco y negro $$$O (N * M * {2} ^ {N * M})$ para color $$$O (N * M * {colores} ^ {N * M})$ . Por analogía con la clasificación de payasos, esta solución también se puede llamar payaso. Es adecuado para tamaño 5x5.

Retroceso

Todos los métodos posibles para organizar grupos horizontales de celdas se ordenan. Ponemos un grupo de celdas en una fila, verificamos que no rompa la descripción de los grupos de columnas. Si se rompe, ponemos más en 1 celda, verificamos nuevamente. Establecer: ir al siguiente grupo. Si no puede poner un grupo de ninguna manera, retrocedemos dos grupos, reorganizamos el grupo anterior, y así sucesivamente, hasta que colocamos con éxito el último grupo.

Por separado para cada fila

Esta decisión es mucho mejor y es verdaderamente cierta. Podemos analizar cada fila y cada columna individualmente. Cada fila intentará revelar la información máxima.

El algoritmo para cada celda de la fila aprende más información; puede resultar que sea imposible colorear la celda de algún color, los grupos no convergerán. No puede expandir completamente la fila de inmediato, pero la información recibida "ayudará" a abrirse mejor en varias columnas, y cuando comencemos a analizarlas, nuevamente "ayudarán" a las filas, y así sucesivamente durante varias iteraciones, hasta que todas las celdas tengan un color posible.

Decisión verdaderamente verdadera

Una línea, dos colores

Adivinar eficazmente la "línea única" en blanco y negro, para la cual algunas celdas ya han adivinado, es una tarea muy difícil. Se conoció en lugares como:

• Cuartos de final de ACM ICPC 2006 : puede intentar resolver el problema usted mismo . El límite de tiempo es de 1 segundo, el límite en el número de grupos es de 400 y la longitud de la serie también es de 400. Tiene un nivel de complejidad muy alto en comparación con otras tareas.
• Olimpiada Internacional de Informática 2016 - condición para pasar la tarea . El límite de tiempo es de 2 segundos, el límite del número de grupos es de 100, la longitud de la fila es de 200'000. Dichas limitaciones son excesivas, pero resolver un problema con restricciones ACM gana 80/100 puntos en este problema. Aquí, también, el nivel no decepcionó, los escolares de todo el mundo con un nivel de coeficiente intelectual cruel han estado entrenando durante varios años para resolver diferentes trucos, luego van a esta Olimpiada (solo deben pasar 4 personas del país), deciden 2 rondas de 5 horas y en el caso de una victoria épica (bronce en diferentes años por 138-240 puntos de 600), admisión a Oxford, luego ofertas de compañías claras al departamento de búsqueda, una vida larga y feliz abrazada con dakimakura.

La línea simple monocroma también se puede resolver de diferentes maneras y para $$$O (N * 2 ^ N)$ (enumerando todas las opciones, verificando la corrección, seleccionando celdas que tengan el mismo color en todas las opciones), y de alguna manera menos estúpidas.

La idea principal es utilizar un análogo de retroceso, pero sin cálculos innecesarios. Si de alguna manera configuramos varios grupos y ahora estamos en algún tipo de celda, entonces necesitamos averiguar si es posible colocar los grupos restantes, comenzando desde la celda actual.

 def EpicWin(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertBlack(cell, len[group]) #    and CanInsertWhite(cell + len[group], 1) #    and EpicWin(group + 1, cell + len[group] + 1): #    win = True can_place_black[cell .. (cell + len[group] - 1)] = True can_place_white[cell + len[group]] = True; #         if CanInsertWhite(cell, 1) and EpicWin(group, cell + 1): win = True can_place_white[cell] = True return win EpicWin(0, 0) 

Este enfoque se llama programación dinámica . El pseudocódigo se simplifica e incluso los valores calculados no se almacenan allí.

Las CanInsertBlack/CanInsertWhite son necesarias para verificar si es teóricamente posible colocar un grupo del tamaño correcto en el lugar correcto. Todo lo que necesitan hacer es verificar que no haya una celda "100% blanca" (para la primera función) o "100% negra" (para la segunda) en el rango de celdas indicado. Para que puedan trabajar para $$$O (1)$ , esto se puede hacer usando cantidades parciales:

 white_counter = [ 0, 0, ..., 0 ] #   n def PrecalcWhite(): for i in range(0, (n-1)): if is_anyway_white[i]: # 1,  i-  100%  white_counter[i]++ if i > 0: white_counter[i] += white_counter[i - 1] def CanInsertBlack(cell, len): #     [cell, cell + len - 1] ans = white_counter[cell + len - 1] if cell > 0: ans -= white_counter[cell - 1] #  ans -     cell  (cell + len - 1) return ans == 0 

La misma hechicería con sumas parciales espera una línea de la forma.

 can_place_black[cell .. (cell + len[group] - 1)] = True 

Aquí podemos en lugar de = True aumentar el número en 1. Y si necesitamos hacer muchas adiciones en un segmento en una determinada matriz $$$array$ , y además no usamos esta matriz antes de diferentes adiciones (dicen sobre esto que esta tarea se "resuelve sin conexión"), luego en lugar de un bucle:

 #     for i in range(L, R + 1): array[i]++ 

Puedes hacer esto:

 #     array[L]++ array[R + 1]-- #    for i in range(1, n): array[i] += array[i - 1] 

Por lo tanto, todo el algoritmo funciona en $$$O (k * n)$ donde $$$k$ - el número de grupos de células negras, $$$n$ Es la longitud de la cuerda. Y vamos a la semifinal del ACM ICPC o conseguimos el bronce del interneur. Solución ACM (Java) . Solución IOI (C ++) .

Una línea, muchos colores

Cuando cambiamos a nonogramas multicolores, que todavía no están claros de cómo resolver, aprendemos una verdad terrible: ¡resulta que cada columna se ve mágicamente afectada por todas las columnas! Esto es más claro a través de un ejemplo:

Fuente - Métodos para resolver crucigramas japoneses

Si bien los nonogramas de dos colores normalmente no existían, no necesitaban mirar hacia atrás a los amigos ortogonales.
La imagen muestra que en el ejemplo de la izquierda, las tres celdas de la extrema derecha están vacías, porque la configuración se rompe si colorea estas celdas en esos colores en los que pintarte color no blanco

Pero esta broma es matemáticamente decidible: cada celda debe tener un número, donde $$$i$ el bit i-ésimo significará si esta celda se puede dar $$$i$ th color. Inicialmente, todas las celdas tienen un valor $$$2 ^ {colores} - 1$ . La decisión de la dinámica no cambiará mucho.

Puede observar el siguiente efecto: en el mismo ejemplo de la izquierda, según la versión de las filas, la celda del extremo derecho puede tener color azul o blanco.
Según la versión de las columnas, esta celda tiene color verde o blanco.
Según la versión de sentido común, esta celda tendrá solo color blanco. Y luego continuamos calculando la respuesta.

Si consideramos el bit cero "blanco", el primer "azul", el segundo "verde", entonces la línea calcula el estado de la última celda $$$011$ y la columna $$$101$ . Esto significa que el estado de esta celda es real $$$011 \ & 101 = 001$

 source = [...] #   result = [0, 0, ..., 0] #   len = [...] #    clrs = [...] #    def CanInsertColor(color, cell, len): for i in range(cell, cell + len): if (source[i] & (1 << color)) == 0: #     color    return False; return True def PlaceColor(color, cell, len): for i in range(cell, cell + len): result[i] |= (1 << color) #   color  OR def EpicWinExtended(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertColor(clrs[group], cell, len[group]) #    and SequenceCheck() #       ,  #         and EpicWin(group + 1, cell + len[group]): #    win = True PlaceColor(clrs[group], cell, len[group]) PlaceColor(0, cell + len[group], 1) #   -    #         #   -  0 if CanInsertWhite(0, cell, 1) and EpicWinExtended(group, cell + 1): win = True PlaceColor(0, cell, 1) return win 

Muchas lineas, muchos colores

Realizando constantemente la actualización de los estados de todas las filas y columnas, descritas en el último párrafo, hasta que no haya una sola celda con más de un bit. En cada iteración, después de actualizar todas las filas y columnas, actualizamos el estado de todas las celdas en ellas a través de AND mutuo.

Primeros resultados

Supongamos que no escribimos el código como pájaros carpinteros, es decir, no copiamos objetos en ningún lugar por error en lugar de pasarlos por referencia, no inventamos bicicletas en ningún lugar, no inventamos bicicletas, para operaciones de bits usamos __builtin_popcount y __builtin_ctz ( características de gcc ), todo está limpio y ordenado.

Veamos el momento del programa, que lee el rompecabezas del archivo y lo resuelve por completo. Vale la pena evaluar las ventajas de la máquina en la que todo esto fue escrito y probado:

 RAM - 4GB  - AMD E1-2500,  1400MHz  L1 - 128KiB, 1GHz  L2 - 1MiB, 1GHz  - 2,  - 2   « SoC   »   2013    28  

Está claro que se eligió tal supercomputadora porque las optimizaciones en ella tienen un efecto mayor que en una máquina shaitan voladora.

Entonces, después de ejecutar nuestro algoritmo en el crucigrama más complicado (de acuerdo con nonograms.ru), obtenemos un resultado no muy bueno: de 47 a 60 segundos (esto incluye la lectura de un archivo y una solución). Cabe señalar que la "complejidad" en el sitio se calculó bien: el mismo crucigrama en todas las versiones del programa también fue el más difícil, otros crucigramas más complejos en la opinión del archivo se mantuvieron en el tiempo máximo.

Color crucigrama número 9596, la mayor dificultad

Para pruebas rápidas, se realizó la funcionalidad para el punto de referencia. Para obtener datos para él, utilizo 4683 crucigramas en color (de 10906 ) y 1406 en blanco y negro (de 8293 ) de nonograms.ru (este es uno de los archivos de nonogramas más grandes en Internet) usando un script especial y los guardé en un formato que el programa entiende. Podemos suponer que estos crucigramas son una muestra aleatoria, por lo que el punto de referencia mostrará valores promedio adecuados. Además, los números de un par de docenas de los crucigramas más "complejos" (también el más grande en tamaño y número de colores) se registraron en un script para cargar con bolígrafos.

Optimización

Aquí puede ver las posibles técnicas de optimización que se realizaron (1) durante la escritura de todo el algoritmo, (2) para acortar el tiempo de trabajo de medio minuto a una fracción de segundo, (3) aquellas optimizaciones que pueden ser útiles aún más.

Al momento de escribir el algoritmo

• Funciones especiales para operaciones de bit, en nuestro caso __builtin_popcount para contar unidades en una notación binaria de un número, y __builtin_ctz para el número de ceros antes de la primera unidad más pequeña. Dichas funciones pueden no aparecer en algunos compiladores. Para Windows, tales análogos son adecuados:

 #ifdef _MSC_VER # include <intrin.h> # define __builtin_popcount __popcnt #endif 

• Organización de matriz: un tamaño más pequeño es lo primero. Por ejemplo, es mejor usar la matriz [2] [3] [500] [1024] que [1024] [500] [3] [2].
• Lo más importante es la adecuación general del código y evitar preocupaciones innecesarias para los cálculos.

Lo que reduce el tiempo de trabajo.

• El indicador -O2 al compilar.
• Para no volver a arrojar la fila / columna completamente resuelta en el algoritmo, puede establecer los indicadores para cada fila en un std :: vector / array separado, marcarlos con una solución completa y no soltarlos si no hay nada más que resolver.
• Los detalles de una solución de repetición múltiple de un problema dinámico sugiere que una matriz especial que contiene marcas que marcan partes del problema ya "calculadas" debe restablecerse cada vez que se crea una nueva solución. En nuestro caso, esta es una matriz / vector bidimensional, donde la primera dimensión es el número de grupos, la segunda es la celda actual (vea el pseudocódigo EpicWin arriba, donde esta matriz no lo es, pero la idea es clara). En lugar de poner a cero, puede hacer esto: permítanos tener una variable de "temporizador", y la matriz consta de números que muestran la última "hora" cuando esta pieza se contó por última vez. Al comenzar una nueva tarea, el "temporizador" aumenta en 1. En lugar de verificar el indicador booleano, debe verificar la igualdad del elemento de matriz y el "temporizador". Esto es efectivo especialmente en casos en los que el algoritmo cubre todos los estados posibles (lo que significa que poner a cero la matriz "¿ya consideramos esto?" Lleva una buena cantidad de tiempo).
• Reemplazar operaciones simples del mismo tipo (bucles con asignación, etc.) con análogos en STL o cosas más adecuadas. A veces funciona más rápido que una bicicleta.
• std::vector<bool> en C ++ comprime todos los valores booleanos en bits individuales en números, lo que funciona en el acceso un poco más lento que si fuera un valor regular en la dirección. Si un programa usa tales valores muy, muy a menudo, reemplazar bool con un tipo entero puede tener un buen efecto en el rendimiento.
• Se pueden buscar otras debilidades a través de los perfiladores y editarlas. Yo mismo uso Valgrind, su análisis de rendimiento es conveniente para mirar a través de kCachegrind. Los perfiladores están integrados en muchos IDEs.

Estas ediciones resultaron ser suficientes para obtener esos datos en el punto de referencia:

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source2/ -e [2018-08-04 22:57:40.432] [Nonograms] [info] Starting a benchmark... [2018-08-04 22:58:03.820] [Nonograms] [info] Average time: 0.00497556, Median time: 0.00302781, Max time: 0.215925 [2018-08-04 22:58:03.820] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 22:58:03.820] [Nonograms] [info] 0.215925 seconds, file 9596 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.164579 seconds, file 4462 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.105828 seconds, file 15831 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.08827 seconds, file 18353 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0874717 seconds, file 10590 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0831248 seconds, file 4649 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0782811 seconds, file 11922 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0734325 seconds, file 4655 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.071352 seconds, file 10828 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0708263 seconds, file 11824 

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source/ -e -b [2018-08-04 22:59:56.308] [Nonograms] [info] Starting a benchmark... [2018-08-04 23:00:09.781] [Nonograms] [info] Average time: 0.0095679, Median time: 0.00239274, Max time: 0.607341 [2018-08-04 23:00:09.781] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 23:00:09.781] [Nonograms] [info] 0.607341 seconds, file 5126 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.458932 seconds, file 19510 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.452245 seconds, file 5114 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.19975 seconds, file 18627 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.163028 seconds, file 5876 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.161675 seconds, file 17403 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.153693 seconds, file 12771 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.146731 seconds, file 5178 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.142732 seconds, file 18244 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.136131 seconds, file 19385 

Puede notar que, en promedio, los crucigramas en blanco y negro son "más difíciles" que los de color. Esto confirma las observaciones de los amantes de los juegos, que también creen que el "color" se resuelve en promedio más fácilmente.

Por lo tanto, sin cambios radicales (como reescribir todo el código en C o insertos de ensamblador con una llamada rápida y bajar el puntero del marco), puede lograr un alto rendimiento en una computadora muy modesta. El principio de Pareto puede ser aplicable a las optimizaciones: resulta que la optimización menor influye fuertemente, porque este código es crítico y se llama con mucha frecuencia.

Mayor optimización

Los siguientes métodos pueden mejorar en gran medida el rendimiento del programa. Algunos de ellos no funcionan en todos los casos, pero bajo ciertas condiciones.

• Reescribiendo el código en estilo C y otros 1972. Reemplazamos ifstream con la contraparte analógica, vectores con matrices, conocemos todas las opciones del compilador y luchamos por cada ciclo de reloj del procesador.
• Paralelización Por ejemplo, en el código hay una pieza donde las filas se actualizan secuencialmente, luego las columnas:

  ... if (!UpdateGroupsState(solver, dead_rows, row_groups, row_masks)) { return false; } if (!UpdateGroupsState(solver, dead_cols, col_groups, col_masks)) { return false; } return true; 

Estas funciones son independientes entre sí y no tienen memoria compartida, a excepción del solucionador de variables (tipo OneLineSolver), por lo que puede crear dos objetos de resolución (aquí, obviamente, solo uno es solucionador) e iniciar dos subprocesos en la misma función. El efecto es este: en los crucigramas de color, el "más difícil" se resuelve el doble de rápido, en blanco y negro, el mismo es un tercio más rápido, y el tiempo promedio ha aumentado, debido al costo relativamente alto de crear hilos.

Pero, en general, no recomendaría hacerlo correctamente en el programa actual y usarlo con calma: en primer lugar, crear subprocesos es una operación costosa, no debe crear constantemente subprocesos para tareas de microsegundos, y en segundo lugar, con alguna combinación de argumentos del programa, los subprocesos pueden referirse a qué memoria externa, por ejemplo, al crear imágenes de una solución; esto debe tenerse en cuenta y asegurarse.

Si la tarea fuera seria y tuviera muchos datos y máquinas multinúcleo, iría aún más lejos: puede crear varios subprocesos constantes, cada uno tendrá su propio objeto OneLineSolver y otra estructura segura para subprocesos que controla la distribución del trabajo y bajo demanda le da una referencia a la siguiente fila / columna para la solución. Los hilos después de resolver otro problema vuelven a la estructura para resolver otra cosa. En principio, un problema de nonograma puede iniciarse sin completar el anterior, por ejemplo, cuando esta estructura se involucra en el AND mutuo de todas las celdas, y luego algunos flujos son libres y no hacen nada. Se puede hacer más paralelización en la GPU a través de CUDA: hay muchas opciones.

• Utilizando estructuras de datos clásicas. Tenga en cuenta que cuando mostré el pseudocódigo de la solución para los nonogramas de color, las funciones CanInsertColor y PlaceColor no funcionan en absoluto $$$O (1)$ , a diferencia de los nonogramas en blanco y negro. Se ve así en un programa:

 bool OneLineSolver::CanPlaceColor(const vector<int>& cells, int color, int lbound, int rbound) { // Went out of the border if (rbound >= cells.size()) { return false; } // We can paint a block of cells with a certain color if and only if it is // possible for all cells to have this color (that means, if every cell // from the block has color-th bit set to 1) int mask = 1 << color; for (int i = lbound; i <= rbound; ++i) { if (!(cells[i] & mask)) { return false; } } return true; } void OneLineSolver::SetPlaceColor(int color, int lbound, int rbound) { // Every cell from the block now can have this color for (int i = lbound; i <= rbound; ++i) { result_cells_[i] |= (1 << color); } } 

Es decir, funciona para la línea, para $$$O (N)$ (Más adelante habrá una explicación del significado de tal código).

Veamos cómo puedes obtener la mejor complejidad. Tome CanPlaceColor . Esta función verifica que entre todos los números del vector en el segmento $$$[lbound, rbound]$ número de bit $$$color$ establecido en 1. Equivalente a esto, puede tomar $$$Y$ todos los números de este segmento y verifique el número de bit $$$color$ . Usando el hecho de que la operación $$$Y$ conmutativo , así como suma, mínimo / máximo, producto u operación $$$X o$ , para un conteo rápido $$$Y$ , . :

1. SQRT-. $$$O(\sqrt{N})$ , $$$O(\sqrt{N})$ . .
2. . $$$O(N\log{N})$ , $$$O(\log{N})$ . .
3. (Sparse Table). $$$O(N\log{N})$ , $$$O(1)$ . .

, - ( $$$O(N)$ , $$$O(1)$ ) , , , $$$\ varphi$ , $$$\varphi(\alpha, \beta) \in \{\alpha, \beta\}$ , — (, ...)

SetPlaceColor . . SQRT- ( " "). - .

- — .

, — , ? :

1. . $$$\log$ , , — ( magic number , ). , $$$N=10^{5}$ , $$$O(N^2)$ 10 , $$$O(N\log{N})$ 0.150 , $$$N$ , . , ( ): $$$O(N\sqrt{N})$ versus $$$O(N\log^2{N})$ . $$$N$ ( ) — 15-30.
2. , .

— , - — $$$N$ , . , ~25% ~11% , . - , , , .

— , . .

• . , , - . : , , "" ? , , ! . , .
• (, 1337 1000x1000) . std::bitset , — , .

, . "" . , C++ ( rope , ), hashtable , 3-6 / 4-10 /, unordered_map. , boost.

ROFL Omitting Format Language

, , , -.

ROFL — , "GNU's Not Unix". , , , , , . Omitting — (, , : — ).

, Matroska — 4 [52][4F][46][4C], , , , 3 , — , .

, MIT, — , .

GitHub . , , (, ). Magick++ args .

, ( ). nonograms.ru , , .

nonograms.ru .. KyberPrizrak , , , ! nonograms.ru, .

.