Contest Delta – Editorial (Parte 2)

No contest Delta, três exercícios se destacaram pela dificuldade, e eu resolvi fazer um post separado para falar sobre eles, pois as suas soluções são um pouco mais complexas. A primeira parte do editorial pode ser encontrada aqui: [link].

Os exercícios em questão eram:
Fibonacci de Novo! [link];
Contagem de Substrings [link];
Cordas Emaranhadas [link];

Todos foram escritos pela mesma pessoa, Gabriel Dalalio, e boa parte do que eu vou disponibilizar aqui foi ele quem me passou, para que eu fizesse esse editorial.

Clique no link abaixo para ver o editorial.

Fibonacci de Novo! [link]
Com um nome atrativo, esse exercício chamou a atenção de muitos maratonistas na hora do contest, que se frustraram ao perceber que a solução era mais complexa do que esperavam.

Uma abordagem ingênua seria resolver o exercício pela fórmula proposta: Fib( Fib(N) )%M, resultando em Overflow devido ao valor elevado de Fib(N), sem falar do tempo posterior necessário para calcular Fib( Fib(N) ).

Uma observação que pode ser feita em relação aos número de Fibonacci módulo M, é que eles entram em uma espécie de ciclo, conhecido como Pisano Period [link].

Por exemplo, seja M = 4, a sequência de Fibonacci comum, e em módulo M, ficam assim:
                  0  1  2  3  4  5  6  7   8   9   10  11  12
Fibonacci Comum:  0  1  1  2  3  5  8  13  21  34  55  89  144
Fibonacci Mód 4:  0  1  1  2  3  1  0  1   1   2   3   1   0
Pisano Period  : [________________][_____________________][…

O ciclo varia de acordo com o valor M. No caso acima, o ciclo tem tamanho 6.

Isso significa que, seja C o tamanho do ciclo, temos:
Fib(K)%M  =  Fib(K%C)%M

Para se descobrir o tamanho do ciclo, a forma iterativa é suficiente. Basta gerar os valores de fibonacci até que se encontre um valor X > 1 onde Fib(X)%M = Fib(X+1)%M = 1, e então C = X-1.
No exemplo acima, X = 7, e C = 6.

Com isso, conseguimos reduzir nossa fórmula inicial para: Fib( Fib(N)%C )%M.

Para finalizar, basta calcular os dois valores de Fibonacci. Aqui o método iterativo e recursivo são muito lentos, precisamos de um método mais rápido. Há dois métodos que custam tempo O(lg N):
Fast Doubling: [link][link]
Exponenciação de Matriz: [link]

Quantas Substrings? – [link]
Este exercício requer uma maneira mais sofisticada de se contar o número de substrings sendo formadas. O número total de substrings dentro de uma string S de tamanho N é igual a N*(N+1)/2, porém muitas delas aparecem mais de uma vez.Além disso, o exercício pede que o número de strings diferentes seja contado diversas vezes, e não só ao final com uma string S fixa. Precisamos então de uma estrutura que nos auxilie no processo.

Há três estruturas candidatas:
Árvore de Sufixos; Vetor de Sufixos; e Autômato de Sufixos.

Com um pouco de experiência com alguma delas, é possível descobrir o número de substrings diferentes em tempo linear.

O Gabriel Dalalio disponibilizou seu Trabalho de Conclusão de Curso, que fala justamente sobre Strings, e faz menção a este exercício em questão. O material está muito bom, segue o link:
https://www.dropbox.com/s/yeg5eo6fthwla0h/TC103_2013.pdf?dl=0

Cordas Emaranhas[link]
O enunciado pede: a sequência é alternante ou não?

O problema é que há sequências que são “alternantes disfarçadas”, tal como no próprio exemplo dado no enunciado, onde “+-++*+”, que não é alternante, tem um resultado idêntico à sequência “+*-*”, que é alternante.

Identificar tais “alternantes disfarçadas” requer muita observação e identificação de alguns padrões. Vou citar aqui 4 padrões que, após aplicadas na sequência, revelam de fato se ela é alternante ou não. Recomendo que peguem um pedaço de papel e uma caneta para que possam compreender melhor todos os padrões citados a seguir:

1 – A subsequência “+-“ não afeta o resultado de forma alguma. Note que as crianças 1 e 2 trocam de lugar duas vezes, e a posição das cordas volta ao estado que estava antes dessa subsequência. Note que a subsequência “-+” é semelhante.
Quando essas subsequências aparecem, simplesmente remova tais movimentos.
Exemplo:  “++-” -> “+”

2 – A subsequência “**” não afeta o resultado de forma alguma. Note que as crianças girarão no sentido horário duas vezes, porém a posição das cordas não muda.
Quando essa subsequência aparecer, simplemente remova tais movimentos.
Exemplo: “+**++” -> “+++”

3 – Se o primeiro movimento da sequência completa é um “*”, então todos os movimentos de troca não afetarão o resultado de forma alguma, até que outro movimento “*” seja realizado. Note que o movimento “*” gira as crianças de tal modo que, quando elas trocam de lugar, a posição das cordas não se altera.
Quando a sequência iniciar com “*”, remova todos os movimentos da primeira posição até a segunda aparição do “*”, inclusive.
Exemplo:  “*++++–++*++” -> “++”

4 – A subsequência “+*+” tem um resultado idêntico à subsequência “*-*”. Este pode ser o padrão mais difícil de se visualizar, e inicialmente é difícil enxergar o objetivo desta troca, mas ela é importante para que, em seguida, novos padrões sejam identificados.
A subsequência “-*-“, de modo semelhante, tem resultado idêntico a subsequência “*+*”.
Quando umas das subsequências citadas aparecer, substitua-a pela sequência alternativa.
Exemplo: “+*+–” -> “*-*–“

-> Mas, porquê fazer todas essas remoções e substituições?
Como eu citei, a aplicação destes padrões revela as sequências “alternantes disfarçadas”. Se a sequência não era alternante, a sequência resultante da aplicação dos padrões será ou uma sequência vazia, ou a sequência “*”. Caso contrário, a sequência é alternante.

-> Da onde veio toda essa história?
Trata-se de um teoria sofisticada estudada a anos, e você pode ler mais a respeito aqui:
http://www.mathteacherscircle.org/assets/session-materials/JTantonRationalTangles.pdf
Espero que eu tenha sido claro o suficiente.
Caso haja alguma dúvida, sugestão ou falha minha, deixem um comentário abaixo.
Agradecimentos ao Gabriel Dalalio, por ter me explicado praticamente tudo o que escrevi aqui.

Até mais 🙂

2 ideias sobre “Contest Delta – Editorial (Parte 2)”

  1. essas estruturas Árvore de Sufixos, Vetor de Sufixos e Autômato de Sufixos são muito cabulosas pra quem nunca tinha visto ‘-‘
    estou tentando resolver o maior substring para várias strings, mas n ta saindo… vou dar uma olhada nesse tcc, talvez me ajude 😀

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *