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

Contest Delta - Editorial (Continuação)

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

[An English version can be found here:]
http://crbonilha.hostei.com/contest-delta-editorial-pt2/?lang=en

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.

Contest Delta - Editorial (English Version)

Hey, today occurred tha second open contest at URI, the Contest Delta, where I wrote 5 from the 13 problems available at the contest. I thank Ricardo Oliveira for reviewing my problems. The other problems were written by Neilor Tonin, Lucas Negri, Márcio Oshiro and Gabriel Dalalio.

[Se você fala Português, venha aqui:]
http://crbonilha.blogspot.com/2014/02/contest-delta-editorial.html

Congratulations to the winners of the contest:
1st place: Fernando Fonseca
2nd place: Igor Wolff
3rd place: Márcio Barbosa

The winners got the following shirt:
https://www.dropbox.com/s/t973nyp3cl98khz/1901876_621867837882912_1664611302_n.png
Cool, no?

I wrote less than half of the problems in this contest, so my editorial will be incomplete for an undetermined time. After the contest ends, I will try to make the other problems, and then I will share my solution here, but I don't know how long it is going to take.
Click at the link below to see the editorial.

Contest Delta - Editorial

Olá, hoje ocorreu o segundo contest aberto do URI, o Contest Delta, onde eu escrevi 5 dos 13 problemas disponíveis na competição. Agradeço ao Ricardo Oliveira por revisar meus problemas. Os outros problemas foram escritos pelo Neilor Tonin, Lucas Negri, Márcio Oshiro e Gabriel Dalalio.

[For those who only speak English, come here:]
http://crbonilha.blogspot.com/2014/02/contest-delta-editorial-english-version.html

Parabéns aos ganhadores da competição:
1⁰ lugar: Fernando Fonseca
2⁰ lugar: Igor Wolff
3⁰ lugar: Márcio Barbosa

Os ganhadores levaram pra casa esta camiseta:
https://www.dropbox.com/s/t973nyp3cl98khz/1901876_621867837882912_1664611302_n.png
Bacana, não?

Agora vamos ao que interessa: eu escrevi menos da metade dos exercícios deste contest, portanto o meu editorial estará incompleto por um tempo indeterminado. Após o contest acabar, vou tentar fazer os exercícios, e então eu compartilho com vocês minha solução, mas não sei quanto tempo isso pode levar.
Clique no link abaixo para ver o editorial.

Contest Delta

Saudações.

Esse sábado vai rolar o segundo contest aberto do URI, onde eu escrevi 6 dos 13 exercícios inéditos que estarão disponíveis :)

Dia: 22/02/2014
Horário: das 14:00 até as 18:00 (para diferentes fuso horários: http://timeanddate.com/s/2j9k)
Se inscrevam em: http://www.urionlinejudge.com.br/judge/login, na aba Contests.

Vou tentar disponibilizar um editorial sobre os exercícios, mas como não sou o único escritor deste contest, talvez eu não consiga resolver todos os exercícios.

Participem, e até mais.

Contest Bonilha - Editorial (English version)

Hi programmers! I had the honor of writing the exercises for the first open to the public contest at URI, entitled "Contest Bonilha". I thank the opportunity to the portal staff, specially to the support given by Neilor and Jean, and also to the programmer Ricardo Oliveira, who revised all the exercises and eventually corrected the exercise and/or the files of some of them.

Se você quer ver a versão em Português do editorial, venha aqui.

Congratulations to the best placed programmers:
Marcos Kawakami
dilsonguim
Hasan0540

For those who couldn't participate, the exercises are already available at the URI site.

I am going to write a small editorial with some resolution tips for the exercises. I advise you to read the editorial only after thoroughly tries of solving the problems, and I ask you to correct me if I say something non-sense.

Click at the link below to see the editorial.

Contest Bonilha - Editorial

Olá maratonistas! Tive a honra de escrever os exercícios para o primeiro contest aberto ao público do URI, entitulado "Contest Bonilha". Agradeço a oportunidade ao pessoal do portal, em especial ao apoio do Neilor e do Jean, e também ao maratonista Ricardo Oliveira, por revisar todos os exercícios e eventualmente corrigir o enunciado e/ou os arquivos de alguns deles.

For those who only speak English, come here.

Parabéns aos melhores colocados do contest:
Marcos Kawakami
dilsonguim
Hasan0540

Pra quem não pode acompanhar, os exercícios já estão disponíveis no portal.

Vou escrever um pequeno editorial com algumas dicas de resolução dos exercícios. Aconselho que leia o editorial apenas após tentar exaustivamente resolvê-los, e peço que me corrijam caso eu fale alguma bobagem.

Clique no link abaixo para ver o editorial.

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

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.

Gerador de Casos de Teste

Um dos grandes desafios envolvidos em resolver um exercício da maratona de programação é pensar em um caso de teste onde seu programa vai falhar.
Os casos de teste oferecidos na descrição do exercício geralmente cobrem a parte mais simples e superficial do mesmo, mas quando chega a hora de submeter o código, ele deve passar por casos de testes gigantescos e complexos, os quais você nem de longe tratou.

Nesse post vou dar um breve exemplo de como criar um gerador de casos de teste, o qual pode lhe ajudar a testar o programa e verificar por si mesmo em quais casos seu programa está falhando.

Aqui está o código que eu montei para exemplificar esse post:
https://github.com/crbonilha/codes/blob/master/Exemplo%20Gerador%20Casos%20de%20Teste

(Linha 6 do código):
Caso esteja programando na linguagem C ou C++ (meu caso), será necessário utilizar alguns metodos responsáveis por manipular arquivos externos, tais como arquivos .txt, ou arquivos sem extensão alguma, mas que contenham nele apenas valores que serão usados no seu programa.
Esses metodos manipulam variáveis do tipo FILE, que serão responsáveis por representar seu arquivo externo. Quem ainda não tem muita familiaridade com essa abordagem, procure estudar algo na internet, em especial o método "fopen()" e "fprintf()", que, para o nosso caso, é mais do que o suficiente.

Voltando ao contexto da maratona, para que você pense em como gerar um caso de teste, primeiro você tem que entender a "hierarquia" de cada caso de teste, por exemplo, no exercicio Bilhetes Falsos (http://www.urionlinejudge.com.br/judge/problems/view/1318), cada caso de teste contém dois inteiros, N e M, e logo após, M inteiros. Seu gerador será responsável por gerar os dois inteiros iniciais (N e M), e logo após, M inteiros. Sim, é bobagem, mas é importante (Linhas 15 e 21).
Outro detalhe que pode passar em branco é que dentre todos os M valores gerados, todos devem estar no intervalo de 1 a N, portanto cuidado na hora de chamar o método de valores aleatórios (Linha 19).

Eu costumo deixar a parte do N e M por minha conta (Linha 13), assim eu decido se quero um caso de teste grande ou pequeno, porém esses mesmos valores poderiam facilmente serem gerados aleatoriamente, como os outros.

Ok, após todos os valores gerados, basta adaptar seu programa que resolve o exercício para ler as entradas do arquivo de teste que você gerou, em vez de ler da entrada padrão como estamos acostumados. Para isso estudem o método "fscanf()".

Agora é possível criar milhares de casos de teste e fazer seu programa rodar todos em segundos. A última parte é saber identificar, dentre milhares de saidas, qual está errada. Restam-lhe duas alternativas: na internet é possivel encontrar os casos de teste de entrada e suas saidas utilizados nas maratonas anteriores, portanto basta encontrá-los e compará-los ao teu; o site com juiz online do URI tem uma ferramenta chamada toolkit, e com ele é possível entregar um caso de teste gerado por você e verificar qual seria a saída de um programa que está funcionando corretamente.

Obviamente, ambas as formas de comparar a saida com algum recurso da internet não lhe será útil na hora da maratona, porém bugs nos quais o seu programa aparentemente para de funcionar, ou estoura o tempo limite, podem ser visivelmente notados com esse tipo de abordagem.

A ferramenta está aí, basta saber quando e como usá-la...

#10 Update

Eae, como estão?

Vim fazer um post rápido só pra anunciar que cheguei a marca de 100 exercícios resolvidos no site URI. Isso mesmo, uma centena deles, resolvidos.

Ainda não conhece o URI? Veja o post que fiz sobre ele aqui: http://crbonilha.blogspot.com.br/2013/03/e-maratona.html

Falta pouco para a maratona, então bora estudar.

Quem precisar de mim, estarei semi-ativo no fórum do URI.

Até mais.

As famosas Pilhas

Você já ouviu falar de pilhas? (me refiro a estrutura de dados)

A estrutura de dados pilha pode parecer simples e inofensiva, porém em certos contextos, principalmente em problemas específicos da maratona de programação, a implementação de uma pilha pode ser fatal.
Um exercício aparemente difícil se torna fácil com uma pilha.

Uma prova? O exercício Ácido Ribunocléico Alienígena é um problema que caiu na maratona alguns anos atrás, e é um dos tópicos mais acessados deste blog, por viajantes do google a procura de resoluções do mesmo. Na época, eu não conhecia a implementação em pilhas, e nem eu lembro como resolvi, mas garanto que hoje eu resolveria algo parecido em metade do tempo só implementando uma pilha.

O link do exercicio, caso esteja curioso, é esse: http://www.urionlinejudge.com.br/judge/problems/view/1242

Meu objetivo não é explicar aqui como funciona o conceito de pilhas, mas sim dizer que esse conceito existe.
Tem bastante material na internet, então procurem um pouco, e saibam que esse exercício pode ser resolvido, de forma ridiculamente fácil, utilizando pilhas.

Alguns outros exercícios que utilizam pilhas podem ser encontrados no site URI, na aba de estrutura de dados dos problemas.

Por hoje é só, estudem!

O Algoritmo de Dijkstra

Já ouviu falar do algoritmo de Dijkstra?

O algoritmo de Dijkstra é famoso por resolver o problema de caminhos mínimos em um tempo bem considerável. Haviam outros algoritmos com o mesmo objetivo antes dele, e surgiram mais após ele, mas em questão de complexidade de implementação e testes com o pior caso, ele continua sendo o mais conveniente.

Mas vamos ao que interessa. Em maratonas de programação, é crucial conhecer esse algoritmo e saber implementá-lo em pouco tempo, pois, como diz Steven Halim (uma espécie de gênio, reconhecido por participações na maratona de programação), não basta "lembrar do algoritmo, mas não saber implementá-lo". Um bom maratonista conhece N algoritmos e implementa todos em uma velocidade alta, para que não haja perda de tempo com coisas simples, e sobre mais tempo para os problemas mais difíceis da maratona.
Portanto, você que diz conhecer o algoritmo, se desafie a implementá-lo em em menos de 5 minutos, e caso não consiga, pratique.

Agora, para quem não conhece, trate de estudar. Esse algoritmo cai em muitos exercícios, e sua lógica é muito peculiar, uma vez que abre um novo ponto de vista para quem o aprende.

Aqui estão alguns exercícios do site URI que envolvem o algoritmo Dijkstra:
Fácil:
http://www.urionlinejudge.com.br/judge/problems/view/1148
Médio:
http://www.urionlinejudge.com.br/judge/problems/view/1123
Difícil:
http://www.urionlinejudge.com.br/judge/problems/view/1085

Nota:
Nenhum problema vai estampar na cara que utiliza o algoritmo de Dijkstra, e raramente vai ser uma simples implementação de Dijkstra. Um bom problema vai envolver um pouco de interpretação de contexto, e pequenas modificações em como os grafos são representados e corridos. As vezes também será necessário uma modificação no próprio algoritmo de Dijkstra, como no terceiro caso.

Nota 2:
O algoritmo de Dijkstra faz a busca pelo grafo. A forma como o grafo é montado, é outra história. Nos primeiros dois exercícios citados, os grafos são montados com peculiaridades diferentes, porém o Dijkstra funciona da mesma maneira nos dois casos, uma vez que o grafo está montado.
Em relação ao terceiro exercício, o grafo fica ainda mais complexo, e acredito que uma modificação no Dijkstra se faça necessário. Não tenho certeza, pois ainda não resolvi, mas me disseram que o Dijkstra resolve, então vamos lá.

Por hoje é isso, estudem o Dijkstra, é importante, e no Google tem material sobrando.
Até mais.

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.