Resolvendo palavras cruzadas em cores japonesas na velocidade da luz

Palavras cruzadas em japonês (também nonograms) são quebra-cabeças lógicos nos quais uma imagem de pixel é criptografada. Você precisa resolver as palavras cruzadas usando números localizados à esquerda das linhas e acima das colunas.

O tamanho das palavras cruzadas pode atingir até 150 x 150. O jogador usa lógica especial para calcular a cor de cada célula. A solução pode levar alguns minutos em palavras cruzadas para iniciantes e dezenas de horas em quebra-cabeças complexos.

Um bom algoritmo pode resolver o problema muito mais rapidamente. O texto descreve como escrever uma solução que funciona quase instantaneamente usando os algoritmos mais adequados (que geralmente levam a uma solução), bem como suas otimizações e o uso de recursos do C ++ (que reduzem o tempo de execução por várias dezenas de vezes).

Na versão móvel do Habr, as fórmulas no texto podem não ser exibidas (não em todos os navegadores móveis) - use a versão completa ou outro navegador móvel, se detectar problemas com as fórmulas

Regras do jogo

Inicialmente, a tela de palavras cruzadas é branca. Para palavras cruzadas em preto e branco, você precisa restaurar o local das células negras.

Nas palavras cruzadas em preto e branco, o número de números de cada linha (à esquerda da tela) ou de cada coluna (parte superior da tela) mostra quantos grupos de células pretas estão na linha ou coluna correspondente e os próprios números mostram quantas células mescladas cada um desses grupos contém. Conjunto de números $$$[3, 2, 5]$ significa que em uma determinada linha existem três grupos consecutivos de $$$3$ , $$$2$ e $$$5$ células pretas seguidas. Os grupos podem ser organizados em uma fileira aleatoriamente, sem violar a ordem relativa (os números especificam seu comprimento e a posição deve ser adivinhada), mas devem ser separados por pelo menos uma célula branca.

Exemplo correto

Nas palavras cruzadas em cores, cada grupo ainda tem sua própria cor - qualquer, exceto o branco, é uma cor de fundo. Grupos vizinhos de cores diferentes podem ficar lado a lado, mas para grupos vizinhos das mesmas cores, a separação por pelo menos uma célula branca ainda é necessária.

O que não é uma palavra cruzada japonesa

Cada imagem de pixel pode ser criptografada como um jogo de palavras cruzadas. Mas pode não ser possível restaurá-lo de volta - o quebra-cabeça resultante pode ter mais de uma solução ou uma solução, mas não pode ser resolvido logicamente. Em seguida, as células restantes no jogo devem ser adivinhadas usando a tecnologia xamânica usando computadores quânticos .

Tais palavras cruzadas não são palavras cruzadas, mas graphomania. Acredita-se que as palavras cruzadas corretas sejam tais que, de maneira lógica, você possa encontrar uma solução única.

O "caminho lógico" é a capacidade de restaurar cada célula uma por uma, considerando a linha / coluna separadamente ou sua interseção. Se isso não for possível, o número de opções de resposta consideradas pode ser muito, muito mais do que uma pessoa pode calcular por si mesma.

O nonograma errado é a única solução, mas é impossível resolver normalmente. Células "insolúveis" rotuladas em laranja. Retirado da Wikipedia.

Essa restrição é explicada da seguinte maneira - no caso mais geral, as palavras cruzadas japonesas são um problema de NP-completo. No entanto, adivinhar não se torna uma tarefa completa de NP, se houver um algoritmo que, a cada instante, indique inequivocamente quais células abrir mais. Todas as palavras cruzadas usadas por seres humanos (exceto pelo método Monte Carlo tentativa e erro) são baseados nisso.

A maioria das palavras cruzadas ortodoxas divide-se por 5 larguras e alturas, não há linhas que possam ser contadas instantaneamente (aquelas em que células coloridas obstruem todos os lugares ou elas não existem) e o número de cores complementares é limitado. Esses requisitos não são necessários.

As palavras cruzadas erradas mais simples:

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

Freqüentemente, a arte pixel codificada, que usa um padrão de "tabuleiro de damas" para simular um gradiente, não é resolvida ao contrário. É melhor entender se você digitar "gradiente de pixelart" na pesquisa. O gradiente é como estas palavras cruzadas 2x2 fayl.

Possíveis soluções

Temos o tamanho das palavras cruzadas, uma descrição das cores e todas as linhas e colunas. Como montar uma imagem a partir disso:

Pesquisa completa

Para cada célula, classificamos todos os estados possíveis e verificamos se é satisfatório. A complexidade dessa solução para palavras cruzadas em preto e branco $$$O (N * M * {2} ^ {N * M})$ para cor $$$O (N * M * {cores} ^ {N * M})$ . Por analogia com a classificação de palhaços, essa solução também pode ser chamada de palhaço. É adequado para o tamanho 5x5.

Backtracking

Todos os métodos possíveis de organizar grupos horizontais de células são resolvidos. Colocamos um grupo de células em uma linha, verifique se ele não quebra a descrição dos grupos de colunas. Se quebrar, colocamos mais uma célula, verificamos novamente. Set - vá para o próximo grupo. Se você não pode colocar um grupo de forma alguma, revertemos dois grupos, reorganizamos o grupo anterior e assim por diante, até colocarmos o último grupo com êxito.

Separadamente para cada linha

Esta decisão é muito melhor e é verdadeiramente verdadeira. Podemos analisar cada linha e cada coluna individualmente. Cada linha tentará revelar o máximo de informações.

O algoritmo de cada célula da linha obtém mais informações - pode ser impossível colorir a célula com alguma cor, os grupos não convergirão. Você não pode expandir completamente a linha imediatamente, mas as informações recebidas "ajudarão" a se abrir melhor para várias colunas e, quando começarmos a analisá-las, elas "ajudarão" novamente as linhas, e assim por diante por várias iterações, até que todas as células tenham uma cor possível.

Decisão verdadeiramente verdadeira

Uma linha, duas cores

A adivinhação eficaz da “linha única” em preto e branco, para a qual algumas células já adivinharam, é uma tarefa muito difícil. Ela conheceu em lugares como:

• Quartas de final do ACM ICPC 2006 - você pode tentar resolver o problema sozinho . O limite de tempo é de 1 segundo, o limite para o número de grupos é 400 e o comprimento da série também é 400. Ele possui um nível muito alto de complexidade em comparação com outras tarefas.
• Olimpíada Internacional de Informática 2016 - condição para passar a tarefa . O limite de tempo é de 2 segundos, o limite do número de grupos é 100, o comprimento da linha é 200'000. Essas limitações são um exagero, mas a solução de um problema com restrições do ACM ganha 80/100 pontos nesse problema. Aqui, também, o nível não decepcionou, crianças de todo o mundo com um nível de QI cruel treinam há vários anos para resolver truques diferentes, depois vão para esta Olimpíada (apenas 4 pessoas do país devem passar), decidem 2 rodadas de 5 horas e, no caso da vitória épica (bronze em anos diferentes, para 138-240 pontos em 600), a admissão em Oxford e, em seguida, oferece de empresas claras ao departamento de busca, uma vida longa e feliz abraçada com dakimakura.

A linha única monocromática também pode ser resolvida de diferentes maneiras e, por $$$O (N * 2 ^ N)$ (enumerando todas as opções, verificando a correção, selecionando células que têm a mesma cor em todas as opções) e, de alguma forma, menos estúpida.

A idéia principal é usar um análogo de retorno, mas sem cálculos desnecessários. Se de alguma forma configuramos vários grupos e agora estamos em algum tipo de célula, precisamos descobrir se é possível colocar os demais grupos, começando na célula atual.

 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) 

Essa abordagem é chamada de programação dinâmica . O pseudocódigo é simplificado e até os valores calculados não são armazenados lá.

As CanInsertBlack/CanInsertWhite são necessárias para verificar se é teoricamente possível colocar um grupo do tamanho certo no lugar certo. Tudo o que eles precisam fazer é verificar se não há célula “100% branca” (para a primeira função) ou “100% preta” (para a segunda) no intervalo de células indicado. Para que eles possam trabalhar $$$O (1)$ , isso pode ser feito usando valores parciais:

 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 

A mesma feitiçaria com somas parciais aguarda uma linha do formulário

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

Aqui podemos, em vez de = True aumentar o número em 1. E se precisarmos fazer muitas adições em um segmento em uma determinada matriz $$$array$ e, além disso, não usamos essa matriz antes de adições diferentes (eles dizem que essa tarefa foi "resolvida offline") e, em vez de um loop:

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

Você pode fazer isso:

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

Assim, todo o algoritmo trabalha em $$$O (k * n)$ onde $$$k$ - o número de grupos de células negras, $$$n$ É o comprimento da string. E vamos à semifinal do ACM ICPC ou obtemos o bronze do interneur. Solução ACM (Java) . Solução IOI (C ++) .

Uma linha, muitas cores

Quando mudamos para nonogramas multicoloridos, que ainda não estão claros como resolver, aprendemos uma verdade terrível - acontece que todas as colunas são magicamente afetadas por todas as colunas! Isso é mais claro através de um exemplo:

Fonte - Métodos para resolver palavras cruzadas em japonês

Enquanto os nonogramas de duas cores normalmente ficavam sem ele, eles não precisavam olhar para os amigos ortogonais.
A figura mostra que, no exemplo da esquerda, as três células da extrema direita estão vazias, porque a configuração é interrompida se você colorir essas células em aquelas cores nas quais você se pinta cor não branca.

Mas essa piada é matematicamente decidível - cada célula deve receber um número, onde $$$i$ o i-ésimo bit significa se essa célula pode ser fornecida $$$i$ ª cor. Inicialmente, todas as células têm um valor $$$2 ^ {cores} - 1$ . A decisão da dinâmica não mudará muito.

Você pode observar o seguinte efeito: no mesmo exemplo à esquerda, de acordo com a versão das linhas, a célula na extremidade direita pode ter a cor azul ou branca.
De acordo com a versão das colunas, essa célula tem a cor verde ou branca.
De acordo com a versão de senso comum, essa célula terá apenas a cor branca. E então continuamos a calcular a resposta.

Se considerarmos o bit zero como "branco", o primeiro "azul", o segundo "verde", a linha calculará o estado da última célula $$$011$ e a coluna $$$101$ . Isso significa que o estado dessa célula é 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 

Muitas linhas, muitas cores

Fazendo constantemente a atualização dos estados de todas as linhas e colunas, descritas no último parágrafo, até que não haja uma única célula com mais de um bit. Em cada iteração, após atualizar todas as linhas e colunas, atualizamos o estado de todas as células nelas por meio de AND mútuo.

Primeiros resultados

Suponha que não escrevemos o código como pica-paus, ou seja, não copiamos objetos em lugar nenhum por engano, em vez de passarmos por referência, não inventamos bicicletas em lugar algum, não inventamos bicicletas, para operações de bit usamos __builtin_popcount e __builtin_ctz ( recursos do gcc ), tudo é limpo e arrumado.

Vamos dar uma olhada na hora do programa, que lê o quebra-cabeça do arquivo e o resolve completamente. Vale a pena avaliar as vantagens da máquina na qual todas essas coisas foram escritas e testadas:

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

É claro que esse supercomputador foi escolhido porque as otimizações nele têm um efeito maior do que em uma máquina shaitan voadora.

Portanto, depois de executar nosso algoritmo no mais complicado jogo de palavras cruzadas (de acordo com nonograms.ru), obtemos um resultado não muito bom - de 47 a 60 segundos (isso inclui a leitura de um arquivo e uma solução). Note-se que a "complexidade" no site foi bem calculada - as mesmas palavras cruzadas em todas as versões do programa também foram as mais difíceis, e outras palavras-chave mais complexas, na opinião do arquivo, foram mantidas em tempo integral.

Palavras cruzadas cor número 9596, a maior dificuldade

Para testes rápidos, foi feita a funcionalidade do benchmark. Para obter dados para ele, eu usei um script especial e os salvei em um formato que o programa entende. Podemos supor que essas palavras cruzadas são uma amostra aleatória; portanto, o benchmark mostraria valores médios adequados. Além disso, o número de algumas das palavras cruzadas mais "complexas" (também as maiores em tamanho e número de cores) foi registrado em um script para carregar canetas.

Otimização

Aqui você pode ver as possíveis técnicas de otimização que foram feitas (1) durante a gravação de todo o algoritmo, (2) para reduzir o tempo de trabalho de meio minuto para uma fração de segundo, (3) as otimizações que podem ser úteis ainda mais.

No momento da escrita do algoritmo

• Funções especiais para operações de bit, no nosso caso __builtin_popcount para contar unidades em uma notação binária de um número e __builtin_ctz para o número de zeros antes da primeira unidade menor. Tais funções podem não aparecer em alguns compiladores. Para o Windows, esses análogos são adequados:

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

• Organização de matrizes - um tamanho menor é o primeiro. Por exemplo, é melhor usar a matriz [2] [3] [500] [1024] do que [1024] [500] [3] [2].
• O mais importante é a adequação geral do código e a prevenção de preocupações desnecessárias nos cálculos.

O que reduz o tempo de trabalho

• O sinalizador -O2 ao compilar.
• Para não lançar a linha / coluna completamente resolvida no algoritmo novamente, você pode definir os sinalizadores para cada linha em um std :: vector / array separado, marcá-los com uma solução completa e não deixar ir, se não houver mais nada a resolver.
• As especificidades de uma solução de repetição múltipla de um problema dinâmico sugerem que uma matriz especial que contenha sinalizadores marcando partes já "calculadas" do problema seja redefinida toda vez que uma nova solução for feita. No nosso caso, esse é um vetor / array bidimensional, em que a primeira dimensão é o número de grupos, a segunda é a célula atual (consulte o pseudocódigo EpicWin acima, onde esse array não é, mas a idéia é clara). Em vez de zerar, você pode fazer isso - vamos ter uma variável "timer", e a matriz consiste em números que mostram a última "hora" em que essa peça foi recontada pela última vez. Ao iniciar uma nova tarefa, o "timer" aumenta em 1. Em vez de verificar o sinalizador booleano, você deve verificar a igualdade do elemento da matriz e o "timer". Isso é eficaz, especialmente nos casos em que longe de todos os estados possíveis são cobertos pelo algoritmo (o que significa que zerar a matriz "já consideramos isso" leva um bom tempo).
• Substituindo operações simples do mesmo tipo (loops com atribuição, etc.) por análogos em STL ou coisas mais adequadas. Às vezes, funciona mais rápido que uma bicicleta.
• std::vector<bool> em C ++ compacta todos os valores booleanos em bits individuais em números, o que funciona no acesso um pouco mais lento do que se fosse um valor regular no endereço. Se um programa usa esses valores com muita frequência, a substituição de bool por um tipo inteiro pode ter um bom efeito no desempenho.
• Outras fraquezas podem ser buscadas através dos criadores de perfil e editá-las. Eu mesmo uso o Valgrind, sua análise de desempenho é conveniente para examinar o kCachegrind. Os criadores de perfil são incorporados a muitos IDEs.

Essas edições foram suficientes para obter esses dados no benchmark:

 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 

Você pode notar que, em média, as palavras cruzadas em preto e branco são "mais difíceis" do que as coloridas. Isso confirma as observações dos amantes de jogos, que também acreditam que a "cor" é resolvida em média com mais facilidade.

Portanto, sem alterações radicais (como reescrever todo o código em C ou inserções de assembler com chamada rápida e abaixar o ponteiro do quadro), você pode obter alto desempenho em um computador muito modesto. O princípio de Pareto pode ser aplicável às otimizações - verifica-se que a otimização menor influencia fortemente, porque esse trecho de código é crítico e é chamado com muita frequência.

Otimização adicional

Os métodos a seguir podem melhorar muito o desempenho do programa. Alguns deles não funcionam em todos os casos, mas sob certas condições.

• Reescrevendo o código no estilo C e outros 1972. Substituímos ifstream pelo equivalente analógico, vetores por arrays, aprendemos todas as opções do compilador e lutamos por cada ciclo de clock do processador.
• Paralelização. Por exemplo, no código, há uma parte em que as linhas são atualizadas seqüencialmente e as colunas:

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

Essas funções são independentes umas das outras e não possuem memória compartilhada, exceto pelo solucionador de variáveis ​​(tipo OneLineSolver), para que você possa criar dois objetos do solucionador (aqui, obviamente, apenas um é solucionador) e iniciar dois threads na mesma função. O efeito é o seguinte: nas palavras cruzadas coloridas, o “mais difícil” é resolvido duas vezes mais rápido, em preto e branco o mesmo é um terço mais rápido e o tempo médio aumentou, devido ao custo relativamente alto da criação de threads.

Mas, em geral, eu não recomendaria fazê-lo corretamente no programa atual e usá-lo com calma - em primeiro lugar, criar threads é uma operação cara, você não deve constantemente criar threads para tarefas de microssegundos e, em segundo lugar, com alguma combinação de argumentos do programa, os threads podem se referir a quais memória externa, por exemplo, ao criar imagens de uma solução - isso deve ser levado em consideração e protegido.

Se a tarefa fosse séria e eu tivesse muitos dados e máquinas com vários núcleos, iria ainda mais longe - você pode criar vários encadeamentos constantes, cada um com seu próprio objeto OneLineSolver e outra estrutura segura de encadeamento que controla a distribuição do trabalho e sob demanda fornece uma referência para a próxima linha / coluna da solução. Os threads após resolver outro problema se voltam para a estrutura novamente para resolver outra coisa. Em princípio, um problema de não programa pode ser iniciado sem concluir o anterior, por exemplo, quando essa estrutura está envolvida no AND mútuo de todas as células, e então alguns fluxos são livres e não fazem nada. Mais paralelismo pode ser feito na GPU via CUDA - há muitas opções.

• Usando estruturas de dados clássicas. Observe que, quando mostrei o pseudocódigo da solução para nonograms de cores, as funções CanInsertColor e PlaceColor não funcionam de todo $$$O (1)$ , diferentemente dos nonogramas em preto e branco. Parece que isso em um 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); } } 

Ou seja, funciona para a linha, para $$$O (N)$ (Posteriormente, haverá uma explicação do significado de um código assim).

Vamos ver como você pode obter a melhor complexidade. Tome CanPlaceColor . Esta função verifica que entre todos os números do vetor no segmento $$$[vinculado, vinculado]$ número de bit $$$cor$ definido como 1. Equivalente a isso, você pode $$$AND$ todos os números deste segmento e verifique o número do bit $$$cor$ . Usando o fato de que a operação $$$AND$ comutativa , bem como soma, mínimo / máximo, produto ou operação $$$Xou$ , para contagem rápida $$$AND$ , . :

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

.