Blog Novo!

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

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

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

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

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

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

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

#66 Exercício - Plágio musical

Nome: Plágio musical
Link: http://br.spoj.pl/problems/PLAGIO/
Dificuldade: 8/10
Linguagem: C++
Tempo atingido: 0.46
Memória usada: 3.3M
Colocação alcançada: 55
Tentativas: Várias

Comentário:
Caramba, essa foi difícil.
Mas depois de pensar e repensar estratégias, deu pra resolver.
Aliás, os músicos levam uma vantagem ai pra poder identificar a entrada. Caso não estejam compreendendo, pensem nas notas como um sequência que se repete, e tente calcular o intervalo entre cada nota.

Dicas:
- O primeiro passo é converter a entrada em valores inteiros. Eu converti a entrada entre valores de 1 a 12, que é o total de notas musicais.
- Uma dica é calcular as diferenças entre cada nota adjacente, para então poder comparar com as diferenças da melodia original.
- Outra dica é encontrar um modo de não ficar voltando ao começo da melodia. Tentem ir sempre em frente, verificando e voltando o mínimo possível.

#65 Exercício - Competição de chocolate

Nome: Competição de chocolate
Link: http://br.spoj.pl/problems/CHOCPJ09/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.01
Memória usada: 2.6M
Colocação alcançada: 45
Tentativas: 3

Comentário:
Pois é, depois de um tempinho sem fazer nada, resolvi resolver um exercício difícil do spoj.
Quando vi esse exercício, julguei que fosse extremamente difícil. Porém depois de um tempão estudando os valores, as possibilidades, cheguei a uma simples resolução, coisa de duas linhas.

Dicas:
- Ambos os jogadores jogam bem, portanto é preciso verificar cada possibilidade.
- A Paula começa o jogo, portanto ela tem uma clara vantagem.
- Note que a Paula tem a possibilidade de "manipular" o Carlos, pensem nisso.

#50 Exercício - Moedas

Nome: Moedas
Link: http://br.spoj.pl/problems/MOEDAS/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.20
Memória usada: 3.1M
Colocação alcançada: 51
Tentativas: 8

Comentário:
Muito interessante este exercício, pode parecer simples mas um algoritmo ingênuo estoura o tempo facilmente.
Para resolvê-lo eu usei algo parecido com BFS, só que um pouco objetivo.
A ideia eu tirei deste tópico aqui, do blog do péricles.
Também é possível resolver com PD (Programação Dinâmica), como me ensinou meu parceiro Fúlvio Abrahão. Agradeço a ajuda.

Dicas:
- Testar todos os casos com todas as possibilidades é suicídio, o tempo vai estourar, portanto nem tente.
- Uma boa técnica é criar um vetor para armazenar, no indice valor, a quantidade mínima de moedas para se chegar lá. Por exemplo: no vetor m[] de índice 10, visto que eu tenho posse de moedas de 2 e de 5 centavos, é possível chegar lá com 2 moedas de 5 centavos, portanto m[10]=2. Agora usem a imaginação.

#40 Exercício - Duende perdido

Nome: Duende perdido
Link: http://br.spoj.pl/problems/DUENDE/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.04
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 1

Comentário:
Já faz um tempo que eu tava de olho nesse problema, hoje eu descobri a saída.
Eu montei uma função recursiva, que pra minha surpresa deixou o algoritmo bem enxuto e objetivo.

Eu recomendo que pesquisem algo sobre o pathfinding.
Existem algum tipos de pathfinding, e eu não tenho certeza se algum deles se aplicam neste exercício.
Acontece que existem os pathfindings "gulosos", que escolhem o melhor caminho no momento e vão seguindo. Acontece que esse melhor caminho no momento, pode ser o caminho errado se olhado de uma maneira geral. Digamos que o atalho as vezes não valha a pena. Então esse algoritmo guloso traria a resposta errada, visto que ele só verifica este caminho.
Já um algoritmo não guloso verificaria todos os caminhos, sem excessão, e portanto trará a resposta certa (se implementado corretamente).

Pesquisem e identifiquem se o algoritmo é guloso ou não. Eu não tenho certeza, pode ser que o guloso por sorte encontre sempre o caminho correto nos casos de teste do spoj. Vocês é que sabem.

Este exercício pode também ser resolvido com uma BFS (breadth first search), que foi o que eu escolhi.

Dica:
- Pesquisem pathfinding, e BFS.
- Pensem numa maneira de mapear a matriz com pontos de distância.
- Tomem cuidado com as casas já visitadas, e também prestem atenção nelas, pode haver um jeito mais econômico de chegar nelas.

Casos de teste úteis

#34 Exercício - Escalonamento ótimo

Nome: Escalonamento ótimo
Link: http://br.spoj.pl/problems/ESCALO11/
Dificuldade: 9/10
Linguagem: C++
Tempo atingido: 4.31
Memória usada: 5.1M
Colocação alcançada: 22
Tentativas: Várias

Comentário:
Ufa, eu não menti pra vocês, faz mais de uma semana que eu estava tentando resolver este exercício.
Tentei de inúmeras maneiras, utilizei de todas as cartas que eu tinha na manga, e só hoje eu vi a dica de um amigo e descobri uma maneira de fazê-lo passar.
O problema sempre esteve no tempo limite, visto que a quantidade de números e de ligações é enorme.
Pra resolver eu estudei um algoritmo chamado fila de prioridade com heap, onde você cria uma lista e vai eliminando os itens que tem menor prioridade. Sempre que um é eliminado, você reorganiza a fila e verifica se estão eliminação permitiu que mais itens entrassem nela. É um pouco complicado mas dá pra fazer.
Eu recomendo pra quem tem certa experiência.

Dicas:
- Estudem fila de prioridade heap, assim como heap sort.
- Organizem a fila com os itens que não nenhuma dependência, e também aqueles em que a depência já foi resolvida.

#24 Exercício - Bolhas e baldes

Nome: Bolhas e baldes
Link: http://br.spoj.pl/problems/BALDES/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 1.32
Memória usada: 3.4M
Colocação alcançada: 100+
Tentativas: 2

Comentário:
Este exercício parece extremamente simples, porém o tamanho da cadeia de valores faz com que um algoritmo ingênuo estoure o tempo.
Trata-se de mais um exercício de ordenação, com foco na quantidade de trocas realizadas.
Porém a cadeia de até 100mil valores faz com que um simples Bubble Sort estoure o tempo, e o fato de que só são possíveis trocas de valores adjacentes na cadeia faz com que o Quick Sort seja inútil.
Portanto o que nos resta é o Merge Sort, modificado para retornar a quantidade de trocas.
Eu não conhecia o Merge Sort até ontem, e fiquei impressionado com sua complexidade.
Mas pesquisem, vale a pena.

Dicas:
- Estudem o algoritmo Merge Sort e modifiquem-o para retornar a quantidade de trocas.
- Notem que só são possíveis trocas de valores adjacente na cadeia, ou seja, valores que estão lado a lado.

#8 Exercício - MegaDamas

Nome: MegaDamas
Link: http://br.spoj.pl/problems/MEGADAMA/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.93
Memória usada: 2.6M
Colocação alcançada: 28
Tentativas: 7

Comentário:
(Refeito em 13/10).
Exercício um pouco complexo, que envolve uma espécie de grafo.
Pesquisem algo sobre funções recursivas, são bem úteis, um pouco difícil de aprender, porém após o domínio elas são bem mais fáceis de escrever.

Dicas:
- Procurem transformar os dados iniciais em um tabuleiro. A entrada com os valores da peças devem ser colocados em seus devidos lugares, de acordo com as normas de um tabuleiro de damas.
- Estudem algoritmos recursivos, e talvez um Backtracking.

#1 Exercício - Gols!

Nome: Gols!
Link: http://br.spoj.pl/problems/GOLSMG/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 4.04
Memória usada: 6.4M
Colocação alcançada: 4
Tentativas: 8

Comentário:
Ufa, essa eu passei um sufoco, mas com muita paciência em procurar os erros mínimos e crucias eu consegui resolvê-lo.
Esse foi o primeiro exercício a ser resolvido por mim após iniciar o blog, e pensei nesse modelo de postagem para auxiliar quem deseja saber algo a respeito da minha tentativa de solução, e também para meu próprio arquivo.

Dicas:
- Esse exercício pode exigir um pouco de experiência e lógica apurada do programador, portanto recomendo para quem já é mais experiente na área.
- Eu não utilizei de nenhum algoritmo ou estudo conhecido para resolvê-lo, e se alguém souber de algum pode comentá-lo aqui para que todos saibamos.
- O exercício utiliza este sistema de janelas para delimitar a área de busca do menor e maior valor, o que por um lado pode parecer facilitar as coisas, por outro lado pode acabar com o seu tempo limite, que foi o que aconteceu comigo no início.
- O principal truque é não fazer a busca completa quando não necessário. Pensem bem nisso, e descubram quando é ou não necessário fazer a busca completa pela janela. Essa é uma dica essencial para não estourar o tempo.
- O espaço da memória também foi um problema, talvez só para mim que não saiba lidar muito com isso. Aconteceu que em meu computador a memória faz com que o programa trave, por isso eu diminui o tamanho máximo de de partidas apenas em meu computador, e quando postei eu aumentei para o tamanho pedido.