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

E a maratona?

Pessoal, como profetizado, hoje eu vou voltar aos meus estudo para a maratona de programação.

Ainda faltam meses, porém há tanto conteúdo, que todo tempo é pouco.

Porém dessa vez vou fazer diferente.

Como têm visto no meu blog, estou ao mesmo tempo estudando o desenvolvimento de jogos, e pretendo dividir meu tempo entre esses dois estudos. E após pensar um pouco, decidi que não mais postarei todos os exercícios resolvidos por mim no blog, mas apenas aqueles que forem mais difíceis, complexos, interessantes, ou algo do tipo.

Resumindo: Continuarei a postar no blog os meus avanços no desenvolvimento de jogos, para utilizá-los como portfólio no futuro, e alguns exercícios particular resolvidos, porém a grande maioria dos exercícios eu não postarei.

Antes de continuar, gostaria de apresentar o site URI. Para aqueles que não conhecem, URI é mais um site com um juiz online e um arquivo com problemas de programação, no mesmo estilo do SPOJ.

O site SPOJ está um pouco "abandonado". Não quero ser grotesco, eu não sei o que aconteceu com os moderadores, mas eles estão meio ausentes, ocasionando um fluxo muito alto de spams no fórum e a inatividade do ranking no site, que era o que mais me estimulava.

Dessa vez migrarei para o URI, que me pareceu mais organizado, com algumas funções a mais, e um fórum ativo (novo, porém ativo).

Convido-os a migrar para o URI, e postar suas dúvidas no fórum. Eu procurarei ser ativo nesse fórum, portanto, entre os exercícios que resolvi, tentarei ajudá-los sempre que possível, ao mesmo tempo que pedirei ajuda para os membros do mesmo.

Aqui está o meu perfil no URI: http://www.urionlinejudge.com.br/judge/ranks/profile/1601

Resolvi até então 15 exercícios, porém a maioria estava na categoria fácil, então não contam haha.

Boa sorte, até mais.

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

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

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

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

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

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

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

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

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

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

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

#72 Exercício - Mesa da Sra Montagny!

Nome: Mesa da Sra Montagny!
Link: http://br.spoj.pl/problems/MESA/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 1.76
Memória usada: 2.7M
Colocação alcançada: 100+
Tentativas: 3

Comentário:
Mais um exercício de grafo disfarçado ai.
Se trata de verificar se o grafo é bipartido.
Pesquisem algo sobre.

Dicas:
- Pesquise algo sobre grafo e como verificar se ele é bipartido.

Clique abaixo para alguns casos de teste úteis.

#71 Exercício - Não é mais um joguinho canadense

Nome: Não é mais um joguinho canadense
Link: http://br.spoj.pl/problems/CONTAGEM/
Dificuldade: 3/10
Linguagem: C++
Tempo atingido: 0.00
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 2

Comentário:
Esse exercício pode parecer difícil, mas tem uma dica lá nos comentários dele que facilitou muito.

Dicas:
- Tentem fazer essa analogia das letras com valores binários, sendo a=0 e b=1. (Créditos a Filipe Bittencourt)
- Notem que o valor de saída pode ser alto, talvez mais alto que um simples inteiro pode aguentar.

#70 Exercício - Tesouro

Nome: Tesouro
Link: http://br.spoj.pl/problems/TESOURO2/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 2.65
Memória usada: 6.5M
Colocação alcançada: 23
Tentativas: 1

Comentário:
Pois é, 70 exercícios resolvidos no SPOJ! Pode não ser muito, mas pra mim já é bastante.
Sem falar na minha colocação na classificação, estou quase no top 200.
Agora vem a parte difícil, é preciso mutos pontos pra subir, mas vou continuar, devagar e sempre.
Voltando ao exercício, foi um pouquinho difícil, mas não muito.

Dicas:
- Façam uma DFS com listas de adjacências.
- Para cada sala visitada, é recomendável salvar um valor máximo que ela pode alcançar, assim não é preciso verificar sempre.
- Caso não entendam de grafos, pesquisem algo na internet, tem bastante conteúdo por aí.