Inverting Huffman

Pra quem não sabe, semana passada, 9 de novembro, aconteceu a fase final da maratona de programação em toda a américa latina, antecedendo apenas a fase mundial que acontecerá [em breve], e o campeão foi o time Ñtemtempabobagi, da USP.
Mais informações aqui: http://maratona.ime.usp.br/resultados13/

Nesse post vou falar sobre o exercício I da fase final, Inverting Huffman, o qual, curiosamente, ninguém resolveu.

Vocês podem baixar o PDF dele e submeter o código para teste neste link:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=615&page=show_problem&problem=4544

A codificação de Huffman trata-se de uma forma de re-codificar os caracteres de um texto, de modo que o comprimento do código de cada caractere seja proporcional ao seu número de ocorrências no texto. Por exemplo, na palavra "Abacate", a letra 'a' receberia um código curto, pois aparece várias vezes, enquanto todas as outras letras, que aparecem apenas uma vez, iriam receber um código longo.
Mais informações: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/huffman.html

Figura A

Ok, mas o que pedia o exercício I da maratona? Para se codificar um texto?

Quase. O exercício trata-se de uma variação bem criativa da codificação de Huffman, na qual, em vez de lhe passar a frequência das letras para que se monte a árvore, passa-lhe a árvore para que se descubra a frequência das letras.

O único requisito para se resolver o exercício é ter um conhecimento de como a árvore é montada, para que seja possível atribuir valores consistentes nos nós, de tal modo que a árvore pudesse ser montada pelo algoritmo de Huffman.

Ok, como ele funciona? No enunciado do exercício há uma explicação do funcionamento do algoritmo de Huffman junto com uma sequência de passos, mas eu vou citar aqui algumas considerações.

- Entenda por "valor" a frequência de ocorrência do caractere no texto. O valor de 'a' acima seria 3.

- Todos os caracteres são folhas, por mais que no exercício não nos preocupemos em si com os caracteres, mas sim com o seu valor e seu nível.

- Os nós que não são folhas são nós criados no decorrer do algoritmo, de tal modo que o seu valor é consequência do valor de ambos os filhos.

Figura B

- Na nossa lista, sempre haverá no mínimo um par de nós no nível mais abaixo da árvore, a não ser que estejamos no último nó (Figura B).

Vamos ao exercício: Como atribuir consistentemente um valor a um nó folha, de modo que a árvore seja montada da forma especificada? Basta simular o funcionamento do algoritmo!

Lembre-se que se deseja o menor valor possível paraa soma de todos os nós.

Digamos que a entrada do exercício seja:
4
1 2 3 3

A estrutura da árvore ficará assim:

Figura C

O algoritmo de Huffman cria uma lista com os valores de cada nó, e escolhe os dois com os menores valores para criar um nó pai e construir a árvore. 

Está vendo aqueles dois nós no nível 3? Se eles estão lá embaixo, devem ter sido escolhidos primeiro na execução do tal algoritmo de Huffman, e, consequentemente, o valor de seus nós deve ser baixo, bem baixo. Que tal 1?

Figura D

O algoritmo de Huffman agora monta-lhes o nó pai, sendo o valor a soma dos nós filhos.

Figura E

Os nós folhas são removidos da lista, e o nó pai adicionado. O algoritmo agora irá escolher os dois nós com o menor valor da lista, e continuar sua execução.

Atente a essa situação da árvore: Que valor poderia ser atribuído ao nó sinalizado de forma que pudéssemos conduzir o algoritmo de Huffman a montar a árvore como planejamos?

Figura F

Se atribuíssimos um valor muito baixo, talvez o algoritmo não tivesse se comportado conforme planejávamos até aquele momento. Por exemplo, se atribuíssemos o valor 2, o algoritmo, no passo anterior, não teria escolhido os nós de valor 3 e 5, mas sim os nós com valor 2 e 3, mudando a estrutura da árvore que esperávamos.

Figura G

Qual seria o menor valor que eu poderia colocar ali então?

O resto eu deixo com vocês.

O Famoso Campo Minado

Já ouviu falar desse jogo?

Se você já teve um dia ocioso no nosso amigo Windows, acho que sim.

Trata-se de um jogo nerd desafiante, que envolve observação, lógica e um pouco de sorte, todos os requisitos necessários para ser um bom maratonista.

Foi pensando nele que resolvi escrever mais um exercício, o qual você pode resolver aqui:
http://www.urionlinejudge.com.br/judge/pt/problems/view/1480

O interessante do Campo Minado é que ele é considerado um jogo da categoria NP-completo, ou seja, em alguns casos de jogo não há como escolher ou verificar se é possível encontrar todas as minas sem se basear em tentativas, sorte, ou os famosos Algoritmos Não Determinísticos (Non Deterministic), os quais podem te render uma boa grana se você desenvolvê-los.

Ajude seu General

“Porque recalcular um caminho do início, se eu já sei metade?”, eis a questão que justifica o post de hoje.

Para os interessados, eu escrevi um exercício, e o mesmo está disponível para ser resolvido no portal do URI, no seguinte link:

http://www.urionlinejudge.com.br/judge/pt/problems/view/1479

Ajude seu General foi um exercício escrito com o propósito de estimular a implementação de formas mais eficientes de se calcular o famoso caminho mínimo em um grafo, dado um devido contexto.

Figura A

Todos estamos acostumados com o contexto padrão: Temos um grafo, e nos é requisitado descobrir qual é o caminho mínimo do vértice S até o vértice D (Figura A).

Para isso usamos os nossos velhos amigos DFS, BFS, Bellman-Ford, Dijkstra, entre outros.

Mas e se o contexto mudar um pouco? E se o nosso grafo fosse dinâmico? E se as arestas pudessem sumir ou aparecer? Eis o contexto DSSSP (Dynamic Single Source Shortest Path).

Figura B.1

Conforme ilustrado pela Figura B.1, a remoção de uma aresta pode inutilizar nosso antigo caminho mínimo, nos forçando a encontrar outro, assim como a inserção de uma nova aresta (Figura B.2) pode nos apresentar um novo caminho, nos forçando a aos menos tentar encontrá-lo.

Figura B.2

A primeira vista, não parece nos restar escolha: devemos recalcular todo nosso grafo, sempre que uma aresta é inserida ou removida, pois só assim podemos ter certeza que o nosso caminho mínimo é de fato o caminho mínimo.

Uma coisa é clara: Tal solução é cara.

E mais: Muito cara.

Figura C

Note que ao remover a aresta em vermelho, temos que recalcular o caminho mínimo para todos os vértices, em especial para o vértice D, entre os N vértices do grafo. Ou seja, custo N (multiplicado pela complexidade do seu algoritmo preferido).

Note ainda que tal aresta não compunha o caminho mínimo (caminho em azul). Poxa, fomos enganados! Recalculamos todo o nosso grafo, e nem precisávamos!

Uma solução mais viável seria tentar “isolar” um conjunto de vértices que realmente fossem “afetados” pela inserção/remoção, conforme ilustrado na Figura D.

Figura D

O fato de não haver uma aresta direcionada saindo do conjunto B em direção ao conjunto A torna fácil perceber que há uma imensa diferença entre tais dois grupos:

a) O caminho mínimo para qualquer que seja o vértice do conjunto A não foi alterado.

b) O caminho mínimo para qualquer que seja o vértice do conjunto B pode ou não ter sido alterado, assim como o caminho mínimo até o vértice D.
Resumindo: Porque recalcular um caminho do início, se eu já sei metade?

Isolamos, então, um conjunto de vértices “afetados” pela remoção de uma aresta, e um recálculo sobre tal conjunto me parece uma escolha bem prudente.

A brecha foi aberta, basta explorá-la. Para isso recomendo lerem o artigo dos cientistas da computação Ramalingam e Reps, que descreve um algoritmo que aborda o tema DSSSP, e resolve o problema descrito com eficácia.

http://pages.cs.wisc.edu/~ramali/jl-algorithms.html

Soluções da Fase Regional da Maratona 2013

Venho aqui divulgar o pdf, escrito por Gabriel Dalalio (ex-maratonista e responsável por colaborar na elaboração dos exercícios desse ano) contendo dicas e resoluções dos exercícios da fase regional de 2013.

Entre os tópicos de estudo estão: Ad-Hoc (A e E), Árvore de Segmentos (B), Grafos (C e J), Força Bruta (D), Sort ou Permutação (G), Exponenciação de Matriz (H), Programação Dinâmica (I) e Árvore Geradora Mínima (com Lowest Common Antecestor) (J).

Tudo isso com mais detalhes aqui:
https://www.dropbox.com/s/q4aa8g0zctzbwnq/solucoes_regional_2013.pdf?dl=0

O pdf está bem organizado e muito bem explicado, portanto se você tem o objetivo de fazer todos os exercícios da prova (tal como eu), não deixe de dar uma olhada.

Lembrando que todos os exercícios da Fase Regional já estão disponíveis no portal do URI Online Judge.

Khan Academy

Maratonas de programação costumam exigir uma boa noção de matemática dos participantes, e por mais que os exercícios relacionados com matemática e geometria envolvam uma pequena fração da prova (geralmente 10%, ou 20% da prova), a resolução de tais exercícios pode decidir o resultado final.

Uma vez que não haja saída, só nos resta estudar matemática o/.

Encontrei faz pouco tempo esse ótimo site, Khan Academy, com video-aulas que envolvem uma área muito ampla da matemática, tal como álgebra, geometria, trigonometria, cálculo, álgebra linear, e mais alguns tópicos.

Se você entende bem inglês, aconselho assistir os vídeos originais, explicados pelo criador do site, Sal, neste link:
https://www.khanacademy.org/

Há também o esforço voluntário de alguns brasileiros dublando os vídeos originais. Então se você prefere assistir os vídeos no seu idioma nativo, siga este link:
http://www.fundacaolemann.org.br/khanportugues/

Guerreiros Etruscos Nunca Jogam Xadrez

Exercício: http://www.urionlinejudge.com.br/judge/problems/view/1308

Com um pouco de observação, notamos que o exercício utiliza o conceito de progressão aritmética.

De acordo com a wikipédia, "Uma progressão aritmética (abreviadamente, P. A.) é uma sequência numérica em que cada termo, a partir do segundo, é igual à soma do termo anterior com uma constante ", sendo 1 a constante r utilizada no exercício.

Note que a primeira linha contém um guerreiro, a segunda linha contém dois guerreiros (primeira linha mais um), na terceira linha temos três guerreiros (segunda linha mais um), e assim por diante.
O exercício ainda nos diz qual é o termo para cada linha: na linha i, temos i guerreiros.

Ok, mas o que o exercício pede então?
Ele nos pede para responder quantas linhas são necessárias para que se contenham N guerreiros.

Um simples termo não pode responder tal questão, pois sabemos apenas que a linha i comporta i guerreiros, mas não sabemos quanto à soma das i-1 linhas anteriores.

Poderíamos sair somando em uma variável auxiliar o valor i, começando com i = 1 até que a soma ultrapasse o desejado, e então i seria a resposta.
Porém essa é a solução força bruta, e precisamos de algo mais eficaz, visto que N <= 10¹⁸.

Se pesquisarmos na internet, encontraremos uma fórmula que nos diz a soma dos n primeiros termos de uma determinada progressão aritmética, que seria a seguinte:

Onde ai se referencia ao termo i (no nosso caso, quantidade de guerreiros na linha i).

Por exemplo, se quisermos saber a soma das 5 primeiras linhas de guerreiros, faríamos o seguinte:

n = 5
a1 = 1 (temos 1 guerreiro na linha 1)
a5 = 5 (temos 5 guerreiros na linha 5)

S5 = (5 * (1 + 5) ) / 2
S5 = 30 / 2 = 15

Ok, temos 15 guerreiros nas 5 primeiras linhas, mas o que o exercício pede é justamente o contrário: Visto que eu tenho N guerreiros, quantas linhas foram necessárias?

Pensem, sabemos o número de guerreiros (Sn), sabemos quantos guerreiros há na linha 1 (a1 = 1), só não sabemos quantas linhas são necessárias (n), e quantos guerreiros há na linha n (an).

Se aplicarmos tudo isso na fórmula... Bom, agora é com vocês.

Abstraindo um problema

Os enunciados dos exercícios escondem o tesouro, e você deve estar atento as pistas (mas apenas as importantes).

Nesse post vou citar um exemplo de como abstrair um exercício, ou seja, ignorar todas as informações inúteis e saber identificar os pontos chaves que nos levam à resolução. Isso inclui identificar pistas "falsas" ou "desnecessárias".

O exercício que vou usar como exemplo aqui é o Fechem as portas! (http://www.urionlinejudge.com.br/judge/problems/view/1371).

Antes de continuar, leiam o enunciado do exercício, e tirem suas conclusões iniciais.

Considerando que todas as portas estão inicialmente fechadas (todos os descendentes fecham as portas antes de descer para o jardim) e que cada descendente entra exatamente uma vez na mansão (a confusão é tão grande que não sabemos em que ordem), quais portas estarão abertas após a entrada de todos os descendentes na mansão?

Pista falsa: "(a confusão é tão grande que não sabemos em que ordem)".
A ordem em que eles entram não faz a menor diferença, visto que todos vão entrar e vão abrir (ou fechar) suas respectivas portas. Veja, se o estado da porta 3 vai ser trocado pelo descendente 1 e 3, nesta ordem, temos um total de duas trocas, e se vai ser trocado pelo descendente 3 e 1, nesta ordem, temos ainda um total de duas trocas, ou seja, a ordem é indiferente, e o total é o mesmo.

Objetivo: Descobrir quantas portas terminarão abertas.
Solução? Força bruta? Não! Veja, temos um valor máximo de 25milhões de portas e descendentes, um valor extremamente alto para se pensar em força bruta.

Pensem comigo: uma porta ou está fechada, ou está aberta, e seu estado troca de um para o outro apenas. Se inicia fechada, com uma troca de estados vai para aberta, e com duas volta para fechada. Se continuarmos nesse ritmo, notaremos que um número par de trocas de estados faz com que a porta termine fechada, e um número ímpar de trocas de estados faz com a porta termine aberta.

A porta número 3 vai ter seu estado trocado por dois descendentes. Vimos que a ordem não importa, o que nos importa mesmo é o número de vezes em que ela vai ter seu estado trocado. No caso da porta número 3, duas vezes. Como vimos no parágrafo anterior, quando o estado da porta é trocado um número par de vezes, ela terminará fechada, portanto temos uma resposta: terminará fechada.

Abstração: Descobrir o número Q de divisores de um valor N, e, com base nesse valor Q, imprimir N ou não.

Exemplo: Vamos descobrir o número de divisores dos valores de 1 até 10.
N                     Q
1: 1               = 1
2: 1, 2           = 2
3: 1, 3           = 2
4: 1, 2, 4       = 3
5: 1, 5           = 2
6: 1, 2, 3, 6   = 4
7: 1, 7           = 2
8: 1, 2, 4, 8   = 4
9: 1, 3, 9       = 3

Solução: Os valores N tal que o número Q total de divisores de N é impar -> 1, 4 e 9.

Abstraído o problema, resta encontrar uma forma eficaz de descobrir esse valor Q, mas com um pouco de observação, é fácil encontrar o padrão. Vou deixar essa tarefa pra vocês.