Resolvi mudar o meu blog, levá-lo um pouco mais a sério, e dispor de um pouco mais de recursos.
O novo endereço do meu blog é este:
http://crbonilha.com
Layout novo, host novo e até domínio novo!
Os posts que eu julgava mais interessantes foram e alguns ainda serão transferidos para lá.
Não farei mais nenhum post aqui, apenas lá.
Considerem este blog aposentado.
Não vou excluí-lo, porém, pois há bastante conteúdo bacana aqui ainda.
Vejo vocês lá.
Mostrando postagens com marcador Exercício. Mostrar todas as postagens
Mostrando postagens com marcador Exercício. Mostrar todas as postagens
segunda-feira, 17 de março de 2014
sexta-feira, 15 de novembro de 2013
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
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.
- 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:
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.
quarta-feira, 30 de outubro de 2013
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 jogonerd 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.
Se você já teve um dia ocioso no nosso amigo Windows, acho que sim.
Trata-se de um jogo
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.
domingo, 13 de outubro de 2013
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.
Figura A
Para os interessados, eu escrevi um
exercício, e o mesmo está disponível para ser resolvido no portal
do URI, no seguinte link:
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?
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
domingo, 25 de agosto de 2013
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.
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.
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.
segunda-feira, 26 de novembro de 2012
#87 Exercício - Fazenda
Nome: Fazenda
Link: http://br.spoj.pl/problems/FAZENDMG/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 3.30
Memória usada: 12M
Colocação alcançada: 32
Tentativas: 4
Comentário:
Tinha até esquecido a sensação de receber um "aceito".
Dicas:
- Pensem em uma matriz grande. Agora preencham. Agora pensem em um modo de verificar quando há ou não uma cerca em determinado lado de determinada posição. Pronto.
- Prestem atenção para não verificar se a posição que você está verificando se há cerca não está fora da própria matriz. Se sim, há cerca.
Link: http://br.spoj.pl/problems/FAZENDMG/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 3.30
Memória usada: 12M
Colocação alcançada: 32
Tentativas: 4
Comentário:
Tinha até esquecido a sensação de receber um "aceito".
Dicas:
- Pensem em uma matriz grande. Agora preencham. Agora pensem em um modo de verificar quando há ou não uma cerca em determinado lado de determinada posição. Pronto.
- Prestem atenção para não verificar se a posição que você está verificando se há cerca não está fora da própria matriz. Se sim, há cerca.
terça-feira, 30 de outubro de 2012
#86 Exercício - TV da Vovó
Nome: TV da Vovó
Link: http://br.spoj.pl/problems/TV/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 1.14
Memória usada: 6.5M
Colocação alcançada: 100+
Tentativas: 2
Dicas:
- O que seria mais eficaz, mudar cada valor da matriz, ou mudar a ordem com que cada valor da matriz será impressa? Imaginem o seguinte: Será impressa a linha 1, e após a linha 2. E se você mudasse, em vez do valores, apenas a ordem: seria impressa a linha 2, e depois a linha 1.
- Notem que o valor que indica quantas posições uma linha/coluna será movida pode ser maior que a própria matriz. Se eu mover 10 colunas a direita, numa matriz com 3 colunas, quantas posições as colunas moveriam de fato?
Link: http://br.spoj.pl/problems/TV/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 1.14
Memória usada: 6.5M
Colocação alcançada: 100+
Tentativas: 2
Dicas:
- O que seria mais eficaz, mudar cada valor da matriz, ou mudar a ordem com que cada valor da matriz será impressa? Imaginem o seguinte: Será impressa a linha 1, e após a linha 2. E se você mudasse, em vez do valores, apenas a ordem: seria impressa a linha 2, e depois a linha 1.
- Notem que o valor que indica quantas posições uma linha/coluna será movida pode ser maior que a própria matriz. Se eu mover 10 colunas a direita, numa matriz com 3 colunas, quantas posições as colunas moveriam de fato?
quinta-feira, 25 de outubro de 2012
#85 Exercício - Companheiros de Exército
Nome: Companheiros de Exército
Link: http://br.spoj.pl/problems/ARMY11/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 1.12
Memória usada: 4.1M
Colocação alcançada: 20
Tentativas: 1
Dicas:
- Pensem em quem está a esquerda e a direita de cada soldado. Quem ficará a direita do soldado que estava a esquerda de quem foi morto? E quem ficará a esquerda do soldado que estava a direita de quem foi morto? Só isso.
Link: http://br.spoj.pl/problems/ARMY11/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 1.12
Memória usada: 4.1M
Colocação alcançada: 20
Tentativas: 1
Dicas:
- Pensem em quem está a esquerda e a direita de cada soldado. Quem ficará a direita do soldado que estava a esquerda de quem foi morto? E quem ficará a esquerda do soldado que estava a direita de quem foi morto? Só isso.
#84 Exercício - Sistema Cipoviário
Nome: Sistema Cipoviário
Link: http://br.spoj.pl/problems/CIPO/
Dificuldade: 8/10
Linguagem: C++
Tempo atingido: 8.20
Memória usada: 33M
Colocação alcançada: 100+
Tentativas: 5
Comentário:
Ta aí, mais um exercício de busca de caminho em grafos.
Dessa vez é pra encontrar a Árvore geradora mínima.
Eu estudei dois métodos, entre eles o algoritmo de Prim e o de Kruskal.
O de Prim acabou dando zebra, porque, de acordo com o que disseram nos comentário e também no fórum, o grafo é desconexo, diferente do que diz o enunciado.
Em um grafo desconexo o algoritmo de Prim não encontrará todas as arestas.
Portanto foi necessário utilizar o algoritmo de Kruskal.
O resultado, portanto, deve ser a soma da árvore geradora mínima de todas as árvores.
Dicas:
- Estudem o algoritmo de Kruskal.
- Estudem Union-Find, para melhor aplicar o algoritmo de Kruskal.
- Notem que há apenas três valores, portanto a ordenação pode ser feita de uma maneira bem otimizada.
Link: http://br.spoj.pl/problems/CIPO/
Dificuldade: 8/10
Linguagem: C++
Tempo atingido: 8.20
Memória usada: 33M
Colocação alcançada: 100+
Tentativas: 5
Comentário:
Ta aí, mais um exercício de busca de caminho em grafos.
Dessa vez é pra encontrar a Árvore geradora mínima.
Eu estudei dois métodos, entre eles o algoritmo de Prim e o de Kruskal.
O de Prim acabou dando zebra, porque, de acordo com o que disseram nos comentário e também no fórum, o grafo é desconexo, diferente do que diz o enunciado.
Em um grafo desconexo o algoritmo de Prim não encontrará todas as arestas.
Portanto foi necessário utilizar o algoritmo de Kruskal.
O resultado, portanto, deve ser a soma da árvore geradora mínima de todas as árvores.
Dicas:
- Estudem o algoritmo de Kruskal.
- Estudem Union-Find, para melhor aplicar o algoritmo de Kruskal.
- Notem que há apenas três valores, portanto a ordenação pode ser feita de uma maneira bem otimizada.
quarta-feira, 24 de outubro de 2012
#83 Exercício - Fusões
Nome: Fusões
Link: http://br.spoj.pl/problems/JOAOMG/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 1.47
Memória usada: 4.2M
Colocação alcançada: 83
Tentativas: 2
Comentário:
Union-Find, é isso que foi preciso estudar.
Não é tão difícil, existem alguns métodos bons na internet, basta pesquisar.
Dicas:
- Estudem Union-Find.
Link: http://br.spoj.pl/problems/JOAOMG/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 1.47
Memória usada: 4.2M
Colocação alcançada: 83
Tentativas: 2
Comentário:
Union-Find, é isso que foi preciso estudar.
Não é tão difícil, existem alguns métodos bons na internet, basta pesquisar.
Dicas:
- Estudem Union-Find.
terça-feira, 23 de outubro de 2012
#82 Exercício - João e o pé de feijão
Nome: João e o pé de feijão
Link: http://br.spoj.pl/problems/JOAOMG/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.15
Memória usada: 2.6M
Colocação alcançada: 65
Tentativas: 2
Comentário:
Bem bolado esse exercício.
Pra resolver basta ter uma noção de manipulação de strings.
Dicas:
- Estudem algo sobre manipulação de strings.
- Vale notar que o quadrado de n pode ser um valor alto.
Link: http://br.spoj.pl/problems/JOAOMG/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.15
Memória usada: 2.6M
Colocação alcançada: 65
Tentativas: 2
Comentário:
Bem bolado esse exercício.
Pra resolver basta ter uma noção de manipulação de strings.
Dicas:
- Estudem algo sobre manipulação de strings.
- Vale notar que o quadrado de n pode ser um valor alto.
#81 Exercício - Achando os assentos
Nome: Achando os assentos
Link: http://br.spoj.pl/problems/ASSENTOS/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 2.11
Memória usada: 3.1M
Colocação alcançada: 36
Tentativas: 4
Comentário:
Esse é um exercício interessante.
Trata-se de encontrar não a submatriz com maior soma, porém a submatriz com uma soma de resultado X de menor tamanho.
Eu estudei um algoritmo chamado Kadane 2D e Kadane 1D, porém a aplicação e o objetivo do mesmo é outro. De qualquer maneira dá pra tirar proveito da ideia utilizada.
O tutorial que segui do Kadane eu encontrei aqui:
http://marathoncode.blogspot.com.br/2012/09/algoritmo-de-kadane-2d.html
Repito: O objetivo do Kadane é outro, porém dá para adaptar a esse exercício.
Dicas:
- Procurem transformar os caracteres em valores, são mais manipuláveis.
- Uma boa ideia é transformar a matriz bidimensional em unidimensional, fazendo assim uma verificação linear. Vale notar que será preciso verificar cada linha, e cada linha somada com cada linha adjacente.
- Para uma maior precisão na procura pelo tamanho certo serão necessários dois índices, um para manipular o começo da submatriz e outro para manipular o final. Apenas um índice não será suficiente.
Link: http://br.spoj.pl/problems/ASSENTOS/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 2.11
Memória usada: 3.1M
Colocação alcançada: 36
Tentativas: 4
Comentário:
Esse é um exercício interessante.
Trata-se de encontrar não a submatriz com maior soma, porém a submatriz com uma soma de resultado X de menor tamanho.
Eu estudei um algoritmo chamado Kadane 2D e Kadane 1D, porém a aplicação e o objetivo do mesmo é outro. De qualquer maneira dá pra tirar proveito da ideia utilizada.
O tutorial que segui do Kadane eu encontrei aqui:
http://marathoncode.blogspot.com.br/2012/09/algoritmo-de-kadane-2d.html
Repito: O objetivo do Kadane é outro, porém dá para adaptar a esse exercício.
Dicas:
- Procurem transformar os caracteres em valores, são mais manipuláveis.
- Uma boa ideia é transformar a matriz bidimensional em unidimensional, fazendo assim uma verificação linear. Vale notar que será preciso verificar cada linha, e cada linha somada com cada linha adjacente.
- Para uma maior precisão na procura pelo tamanho certo serão necessários dois índices, um para manipular o começo da submatriz e outro para manipular o final. Apenas um índice não será suficiente.
domingo, 21 de outubro de 2012
#80 Exercício - Zak Galou
Nome: Zak Galou
Link: http://br.spoj.pl/problems/ZAK/
Dificuldade: 9/10
Linguagem: C++
Tempo atingido: 1.40
Memória usada: 22M
Colocação alcançada: 89
Tentativas: 10
Comentário:
Ta aí um exercício "combo" dos últimos exercícios que resolvi.
O exercício Zak Galou explora o 'problema da mochila' (knapsack) e a BFS (Busca em Amplitude).
É usado o problema da mochila para descobrir a quantidade de mana necessária para matar o monstro. Nesse caso o dano seria o o valor, e a mana o peso.
Após descoberto o custo para se chegar a cada sala, é só aplicar uma BFS. Recomendo o algoritmo do Dijkstra.
Dicas:
- Estudem o "problema da mochila" (knapsack problem). Recomendo atenção ao método por programação dinâmica.
- Estudem um algoritmo para fazer um BFS. Recomendo o Dijkstra.
- O valor resultante pode chegar na casa do bilhão.
Link: http://br.spoj.pl/problems/ZAK/
Dificuldade: 9/10
Linguagem: C++
Tempo atingido: 1.40
Memória usada: 22M
Colocação alcançada: 89
Tentativas: 10
Comentário:
Ta aí um exercício "combo" dos últimos exercícios que resolvi.
O exercício Zak Galou explora o 'problema da mochila' (knapsack) e a BFS (Busca em Amplitude).
É usado o problema da mochila para descobrir a quantidade de mana necessária para matar o monstro. Nesse caso o dano seria o o valor, e a mana o peso.
Após descoberto o custo para se chegar a cada sala, é só aplicar uma BFS. Recomendo o algoritmo do Dijkstra.
Dicas:
- Estudem o "problema da mochila" (knapsack problem). Recomendo atenção ao método por programação dinâmica.
- Estudem um algoritmo para fazer um BFS. Recomendo o Dijkstra.
- O valor resultante pode chegar na casa do bilhão.
sábado, 20 de outubro de 2012
#79 Exercício - Pedido de Desculpas
Nome: Pedido de Desculpas
Link: http://br.spoj.pl/problems/DESCULPA/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.24
Memória usada: 2.8M
Colocação alcançada: 100+
Tentativas: 3
Comentário:
Demorei um pouco, mas consegui.
Pra quem não conhece esse exercício trata de um problema famoso da área, o problema da mochila (knapsack problem).
Esse problema é um NP-Completo, portanto não há um método "perfeito" de resolvê-lo.
Entre as soluções estudadas até então estão a força bruta, a programação dinâmica e um método guloso.
A força bruta estourou o tempo quando eu tentei. Então estudei a programação dinâmica e deu certo.
O método guloso eu não cheguei a testar, mas fica a dica pra quem quiser.
Dicas:
- Estudem o problema da mochila (knapsack problem). Recomendo o método por programação dinâmica.
Link: http://br.spoj.pl/problems/DESCULPA/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.24
Memória usada: 2.8M
Colocação alcançada: 100+
Tentativas: 3
Comentário:
Demorei um pouco, mas consegui.
Pra quem não conhece esse exercício trata de um problema famoso da área, o problema da mochila (knapsack problem).
Esse problema é um NP-Completo, portanto não há um método "perfeito" de resolvê-lo.
Entre as soluções estudadas até então estão a força bruta, a programação dinâmica e um método guloso.
A força bruta estourou o tempo quando eu tentei. Então estudei a programação dinâmica e deu certo.
O método guloso eu não cheguei a testar, mas fica a dica pra quem quiser.
Dicas:
- Estudem o problema da mochila (knapsack problem). Recomendo o método por programação dinâmica.
domingo, 14 de outubro de 2012
#78 Exercício - Estrada romana
Nome: Estrada romana
Link: http://br.spoj.pl/problems/ROMANA07/
Dificuldade: 8/10
Linguagem: C++
Tempo atingido: 0.54
Memória usada: 3.5M
Colocação alcançada: 3
Tentativas: 8
Comentário:
E pra variar, mais um exercício baseado em grafos.
Desta vez é uma árvore geradora mínima.
O que assusta um pouco nesse exercício é que os pesos de cada aresta não são dados de bandeja, porém você deve calcular cada um.
Eu demorei um pouco, mas descobri um meio de descobrir a quantidade de combinações de uma forma bem eficiente.
Dicas:
- Estudem árvore geradora mínima.
- Entendam o conceito de programação dinâmica, e tentem aplicar no modo de descobrir o peso das arestas.
- Note que a saída pode ser um pouco alta.
Link: http://br.spoj.pl/problems/ROMANA07/
Dificuldade: 8/10
Linguagem: C++
Tempo atingido: 0.54
Memória usada: 3.5M
Colocação alcançada: 3
Tentativas: 8
Comentário:
E pra variar, mais um exercício baseado em grafos.
Desta vez é uma árvore geradora mínima.
O que assusta um pouco nesse exercício é que os pesos de cada aresta não são dados de bandeja, porém você deve calcular cada um.
Eu demorei um pouco, mas descobri um meio de descobrir a quantidade de combinações de uma forma bem eficiente.
Dicas:
- Estudem árvore geradora mínima.
- Entendam o conceito de programação dinâmica, e tentem aplicar no modo de descobrir o peso das arestas.
- Note que a saída pode ser um pouco alta.
#77 Exercício - Desvio de rota
Nome: Desvio de rota
Link: http://br.spoj.pl/problems/DESVIO/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.10
Memória usada: 4.0M
Colocação alcançada: 30
Tentativas: 6
Comentário:
Pois é, mais um exercício que usa o algoritmo de Dijkstra.
Esse foi um pouco mais chato que o do Engarrafamento, pois há uma restrição adicional.
Dicas:
- Estudem algum algoritmo para encontrar o "caminho de menor custo", recomendo o Dijkstra.
- Vale notar que há casos onde o resultado é igual a 0, visto que o valor do pedágio pode ser 0.
- A cidade onde o carro foi consertado nunca está inicialmente na rota.
- Após entrar em qualquer ponto da rota, deve-se seguir a rota cidade por cidade e na ordem.
Link: http://br.spoj.pl/problems/DESVIO/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.10
Memória usada: 4.0M
Colocação alcançada: 30
Tentativas: 6
Comentário:
Pois é, mais um exercício que usa o algoritmo de Dijkstra.
Esse foi um pouco mais chato que o do Engarrafamento, pois há uma restrição adicional.
Dicas:
- Estudem algum algoritmo para encontrar o "caminho de menor custo", recomendo o Dijkstra.
- Vale notar que há casos onde o resultado é igual a 0, visto que o valor do pedágio pode ser 0.
- A cidade onde o carro foi consertado nunca está inicialmente na rota.
- Após entrar em qualquer ponto da rota, deve-se seguir a rota cidade por cidade e na ordem.
sábado, 13 de outubro de 2012
#76 Exercício - Engarrafamento
Nome: Engarrafamento
Link: http://br.spoj.pl/problems/ENGARRAF/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.05
Memória usada: 4.7M
Colocação alcançada: 100+
Tentativas: 6
Comentário:
Faz um tempo que eu ouvia falar do algoritmo de Dijkstra (segundo o que eu li, se lê "dêcstra"), sobre como encontrar o caminho de menor custo, e finalmente consegui implementar.
Requer um conhecimento sobre grafos, e um pouco sobre ordenação, portanto recomendo para os mais experientes.
Aliás, um abraço pro meu nome amigo José, que me deu umas dicas sobre esse exercício.
Dicas:
- Estude algum algoritmo sobre encontrar o caminho de menor custo. Recomendo o Dijkstra para os mais experientes. Não tenho certeza se força bruta passa no tempo desse exercício, mas da pra tentar também.
Link: http://br.spoj.pl/problems/ENGARRAF/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.05
Memória usada: 4.7M
Colocação alcançada: 100+
Tentativas: 6
Comentário:
Faz um tempo que eu ouvia falar do algoritmo de Dijkstra (segundo o que eu li, se lê "dêcstra"), sobre como encontrar o caminho de menor custo, e finalmente consegui implementar.
Requer um conhecimento sobre grafos, e um pouco sobre ordenação, portanto recomendo para os mais experientes.
Aliás, um abraço pro meu nome amigo José, que me deu umas dicas sobre esse exercício.
Dicas:
- Estude algum algoritmo sobre encontrar o caminho de menor custo. Recomendo o Dijkstra para os mais experientes. Não tenho certeza se força bruta passa no tempo desse exercício, mas da pra tentar também.
terça-feira, 9 de outubro de 2012
#75 Exercício - Batalha naval
Nome: Batalha naval
Link: http://br.spoj.pl/problems/BATALHA2/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 0.06
Memória usada: 2.9M
Colocação alcançada: 57
Tentativas: 5
Comentário:
Exercício de um joguinho que todo mundo conhece, batalha naval.
Não chega a ser difícil, basta ir marcando as jogadas e depois verificar se todas as partes de cada navio foi atingida.
Dicas:
- Certifiquem-se de verificar se todas as partes do navio em questão foram atingidas.
Link: http://br.spoj.pl/problems/BATALHA2/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 0.06
Memória usada: 2.9M
Colocação alcançada: 57
Tentativas: 5
Comentário:
Exercício de um joguinho que todo mundo conhece, batalha naval.
Não chega a ser difícil, basta ir marcando as jogadas e depois verificar se todas as partes de cada navio foi atingida.
Dicas:
- Certifiquem-se de verificar se todas as partes do navio em questão foram atingidas.
domingo, 7 de outubro de 2012
#74 Exercício - Recuperação
Nome: Recuperação
Link: http://br.spoj.pl/problems/RECUPERA/
Dificuldade: 2/10
Linguagem: C++
Tempo atingido: 0.01
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 2
Comentário:
Exercício simples, recomendado para iniciantes.
Dicas:
- Prestem atenção no enunciado.
Link: http://br.spoj.pl/problems/RECUPERA/
Dificuldade: 2/10
Linguagem: C++
Tempo atingido: 0.01
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 2
Comentário:
Exercício simples, recomendado para iniciantes.
Dicas:
- Prestem atenção no enunciado.
sábado, 6 de outubro de 2012
#73 Exercício - Você pode dizer 11
Nome: Você pode dizer 11
Link: http://br.spoj.pl/problems/ONZE/
Dificuldade: 4/10
Linguagem: C++
Tempo atingido: 0.07
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 3
Comentário:
Esse exercício pode parecer fácil no começo, porém ao se deparar com um número de até 1000 dígitos é preciso pensar duas vezes antes de resolvê-lo.
O interessante é que nem foi tão difícil. Eu dei uma olhada nos comentários, como sempre, e me deparei com esses "Critérios de divisibilidade", que o Cleber Adriani mostrou, que eu nunca imaginei que existiam.
Deem uma olhada: http://pt.wikipedia.org/wiki/Crit%C3%A9rios_de_divisibilidade
Com isso fica mais fácil resolver o exercício.
Dicas:
- Estudem critérios de divisibilidade.
- Notem que a entrada deverá ser uma cadeia de caracteres, e, independente do método escolhido, será necessário converter os valores para inteiros. Eu sempre uso a tabela ASCII (http://www.asciitable.com/) para converter.
Link: http://br.spoj.pl/problems/ONZE/
Dificuldade: 4/10
Linguagem: C++
Tempo atingido: 0.07
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 3
Comentário:
Esse exercício pode parecer fácil no começo, porém ao se deparar com um número de até 1000 dígitos é preciso pensar duas vezes antes de resolvê-lo.
O interessante é que nem foi tão difícil. Eu dei uma olhada nos comentários, como sempre, e me deparei com esses "Critérios de divisibilidade", que o Cleber Adriani mostrou, que eu nunca imaginei que existiam.
Deem uma olhada: http://pt.wikipedia.org/wiki/Crit%C3%A9rios_de_divisibilidade
Com isso fica mais fácil resolver o exercício.
Dicas:
- Estudem critérios de divisibilidade.
- Notem que a entrada deverá ser uma cadeia de caracteres, e, independente do método escolhido, será necessário converter os valores para inteiros. Eu sempre uso a tabela ASCII (http://www.asciitable.com/) para converter.
Assinar:
Postagens (Atom)