domingo, 30 de agosto de 2009

Seletiva da FURB para o ICPC

Finalmente chegou o dia das seletivas da FURB para definir as equipes que participarão da fase regional do ICPC!
A prova foi ontem, 29/08, das 13h às 17h no Campus III da FURB, e contou com a presença de 5 equipes no total. A competição foi bem divertida, teve um início meio tenso, com algumas equipes resolvendo umas questões e se alternando na 'liderança', porém, depois de umas 2h de prova, a equipe que acabou em primeiro (Fureuler), com 7 das 8 questões resolvidas, se distanciou um pouco, assim como a minha equipe (GaKiDo), formada por mim, pelo Jean Kirchner e pelo Felipe Garcia. Acabamos em segundo lugar com 5 questões resolvidas, queríamos um resultado melhor, mas a classificação para a regional já valeu :-)
Quero dar os parabéns a todos que participaram da competição, e desejar melhor sorte da próxima vez aos que não conseguiram atingir os objetivos ontem.

Nosso próximo passo agora será tentar estudar um pouquinho mais e tentar corrigir os erros que cometemos nessa seletiva, para poder ir bem na regional (que acontecerá na FURB também, dia 19/09), e de preferência ficar entre os dois primeiros lugares para chegar à etapa nacional :-)

Ah! infelizmente ainda não consegui as fotos da seletiva, mas quando a FURB liberar eu ponho o link aqui no blog ;-)

terça-feira, 18 de agosto de 2009

Grandes desafios

Inicio hoje este blog para falar de um passatempo que vem tomando boa parte do meu tempo livre nas últimas semanas, e que provavelmente tomará boa parte do meu tempo futuro :)
Como desenvolvedor, duas coisas que sempre muito me facinaram foram a resolução de problemas, e o estudo de assuntos variados (algoritmos, técnicas, teorias), e as competições de programação conseguem juntar essas duas coisas de maneira brilhante (!).

Hoje consegui resolver um dos problemas mais "cabulosos" pelos quais já me defrontei nessa vida de competidor: SET. Esse probleminha, apesar do nome simples (a lógica de resolução também é relativamente simples, o que pega mesmonesse problema é a performance para chegar ao resultado ótimo), me demandou umas duas semanas de esforço (e uma ajudinha do professor Claudio Loesch, aliás, obrigado por ter respondido o e-mail do Jean, sem a sua ajuda não sei se teria conseguido resolver esse problema tão "rápido"), tentei Brute Force, um pouco de Backtracking para explorar todas as possibilidades de resolução do problema, mas tudo me gerava um retorno de tempo limite excedido, foram diversas tentativas de otimização, desde otimizar a leitura/escrita do algoritmo, e principalmente otimizar a lógica de resolução do problema, precisei utilizar inclusive uma pequena 'heurística' para obter o resultado esperado. O mais interessante é que o resultado que obtive, além de muito performático (comparado aos outros algoritmos), foi feito em Java, diferentemente da grandiosa maioria, feita em C ou C++, que geralmente é 5 vezes mais rápido, inclusive, alguns algoritmos C rodaram 5 vezes 'menos rápido' que o meu em Java:)

Abaixo seguem as "provas" desta façanha, os algoritmos foram submetidos ao UVa Online e ao br.SPOJ:




Recomendo que todo programador/desenvolvedor participe desse tipo de competição para aguçar suas habilidades e se forçar a pensar um pouco em novos caminhos...

Para quem quer iniciar ou quer dicas de sites, posso recomendar alguns links: o SPOJ (br.spoj.pl), da segunda imagem acima, é um juiz online nacional derivado de um site internacional, o interessante dele é que permite desenvolver desde linguagens de alto nível como Java e C#, passando por linguagens conhecidas como C, C++, Pascal, Perl, Assembly (!), e até mesmo linguagens mais undergrounds como Brainfuck por exemplo; o UVa Online (uva.onlinejudge.org), da primeira imagem deste post, é o meu favorito, é em inglês, mas tem pessoas do mundo todo participando, e tem um conjunto enorme de problemas a serem resolvidos, inclusive o de todas as finais mundias do ICPC (International Collegiate Programming Contest), porém só permite resolver os problemas em C, C++, Java e Pascal. E por fim, temos o Google Code Jam (code.google.com/codejam), concurso exclusivo do Google, que vem ocorrendo aproximadamente uma vez por ano, e após a ocorrência das etapas, todos os problemas ficam disponíveis para serem resolvidos por quem quiser, e na linguagem que desejar :)

Por hoje é isso... durante a semana continuarei estudando (no tempo livre), visando principalmente a eliminatória interna da FURB para o ICPC; e seguinte, o Google CodeJam, que inicia no dia dois próximo. Me deseje sorte.