Esse sábado eu participei, junto com o Carlos Pontual e o Heraldo Carneiro, da décima segunda edição da Maratona Brasileira de Programação.
A sede do Ceará na competição ia ser em Sobral, com o pessoal da Engenharia da Computação da UFC, mas acabou sendo na Unifor. Uma pena, eu queria ter viajado pra conhecer o curso novo.
Embora antigamente eu tenha competido na OBI (OlimpÃada Brasileira de Informática), eu nunca havia competido na Maratona Brasileira de Computação. Enquanto a OBI é uma competição voltada para alunos do ensino médio e básico a maratona é voltada para alunos do ensino superior da graduação e mestrado. Pelas minhas contas já faziam aà uns 3 anos que eu não competia.
Para quem não conhece esse tipo de competição, funciona assim: uma pessoa ou uma equipe (dependendo da competição) tem um certo tempo para resolver uma série de problemas usando programação. A correção do programa é automatizada. Seu programa é testado através de uma bateria de testes e deve retornar as respostas corretas. É uma ótima forma de melhorar seus conhecimentos sobre grafos, lógica, programação dinâmica, estruturas de dados, programação etc. Também é uma ótima oportunidade para conhecer ou rever o pessoal dos cursos de computação.
Bem, vamos aos problemas que nós fizemos:
- Varetas, problema H, era um problema bem simples. Esse nós fizemos em C e foi aceito de primeira.
- Histórico, problema E, também um problema não muito complicado. Mas foi por ele que nós nos enrolamos. Nós resolvemos o problema em Java e submetemos, mas a correção deu runtime error para ele. Nós re analisamos o problema, modificamos o programa e mandamos novamente e ganhamos outro runtime error. Como nós estávamos bem confiantes que nossa resposta estava certa nós refizemos o programa em C e submetemos. Dessa vez o programa passou sem problemas. Mais Tarde ficamos sabendo que devido a um erro da correção automática, não havia como um programa em Java ter acertado essa questão. Isso fez que passemos 1 hora e 44 minutos nesse problema.
- Rouba, problema B, basicamente um problema para simular um jogo de cartas. O Heraldo pegou esse problema e fez ele em Java. Depois de 3 submissões e 3 time limit exceeded da correção automática, nós estávamos certos que nosso programa estava correto. Nós já haviamos feitas varias otimizações de velocidade no programa. Havia agora três alternativas: ou abandonar o problema e tentar outra questão ou continuar a otimizar o programa ou refaze-lo em C. Até tentamos sair do problema, mas ele não saiu da cabeça do Heraldo :). Refaze-lo em C implicaria em implementar uma série de estruturas na unha, o que iria ser muito chato e não havia certeza que isso ia resolver nossa vida.Por fim o Heraldo fez mais um última pequena otimização no programa e ele passou.
Nós ainda tentamos sem sucesso resolver os problemas Mário (o problema do armário hehehe) e o Zak.
Algumas estatÃsticas (parciais) da sede do Ceará:
| Problema |
Submissões |
Aceitos |
| Histórico |
27 |
9 (33%) |
| Rouba |
17 |
6 (35%) |
| Tubos |
1 |
0 |
| Volei |
1 |
0 |
| Zak |
6 |
2 (33%) |
| bolhas |
4 |
0 (0%) |
| caixas |
23 |
5 (22%) |
| mario |
8 |
2 (25%) |
| olimp |
0 |
0 |
| varetas |
17 |
10 (59%) |
Equipes e problemas resolvidos:
| Equipe |
Resolvidos |
Problemas |
| UECE – Camila, Tainara, Leonilia |
6 |
Rouba (7/207), mario (1/172), Histórico (1/41), caixas (1/233), varetas (1/49), Zak (2/273) |
| UECE – Die aphthe schmerzen |
5 |
Rouba (1/161), mario (2/0-), Histórico (1/47), caixas (2/223), varetas (1/35), Zak (4/186) |
| AVL Team |
5 |
Rouba (1/135), mario (1/277), Histórico (1/77), caixas (5/296), varetas (1/67) |
| Os Entrevistados |
4 |
Rouba (1/90), Tubos (1/-), Histórico (1/79), caixas (2/182), varetas (1/66) |
| GOF |
4 |
Rouba (2/73), Histórico (5/151), Caixas (5/289), Varetas (1/39) |
| Eupodiatamatando |
3 |
Rouba (4/181), Mário (4/-), Histórico (3/143), Varetas (1/39) |
| UECE – n^n |
2 |
Rouba (1/-), Histórico (1/90), caixas (1/-), varetas (2/122) |
| UECE – n! |
2 |
Histórico (2/206), varetas (1/61) |
| unifor2 |
2 |
Histórico (2/206), varetas (1/61) |
| Mazela.cpp |
1 |
Vôlei (1/-), Histórico (4/-), caixas (7/-), varetas (1/71) |
| unifor1 |
1 |
Histórico (2/-), Varetas 6 |
Observações: A equipe Singularidade de Sobral não estava presente lá, eu não sei se eles competiram. As equipes da UECE tiveram a boa idéia de colocar o nome da faculdade no nome da equipe.
Eu gostei muito dos resultados. Tivemos muitas equipes com bons resultados. Isso demonstra que os esforços, principalmente do Joel Uchôa, em divulgar e particularizar a competição estão sendo frutÃferos. Todas as universidades conseguiram bons resultados. Ano que vem eu espero ver mais universidades competindo.
Sugestões para a organização:
- Linguagens: segundo o Joel Uchôa me informou há planos para inserir novas linguagens na competição. Fica minha sugestão para que Python e Ruby sejam incluÃdas.
- Java: me parece que há um longo histórico de problemas com a correção de programas em Java, sendo inclusive o uso desta desaconselhado por alguns. Eu espero que isso seja melhorado na próxima edição. Eu e minha equipe tivemos sérios problemas por conta disso mas nem por isso tenho planos de usar outra linguagem na próxima edição.
- Distribuição: há uma distribuição GNU/Linux própria para a competição o Maratona Linux. Ele tem várias sacadas legais como redes separadas para que nenhuma equipe possa usar a Internet ou enxergar as outras equipes, boot remoto etc. Porém é necessário boot pelo disquete o que tem sido uma fonte constante de problemas. O sistema de janelas WindowMaker também é fonte de confusão com usuários iniciantes, se é realmente necessário um sistema minimalista eu recomendaria o Fluxbox, XFCE ou Icewm.
- Correção: eu não gosto do esquema de correção da Maratona. Eu prefiro o da OBI. Na OBI há varias baterias de testes, cuidadosamente preparadas para filtrar cada tipo de erro ou algoritmos. Cada acerto em uma bateria resulta em pontuação. Já na maratona ou se acerta uma questão completamente ou ela está totalmente errada. Isso impede algoritmos mais triviais, algoritmos com complexidade alta (os não polinomiais) e impede também usar técnicas de Inteligência Artificial. Acho que isso interfere muito na forma de se elaborar os problemas e de se resolver os problemas. No universo dos problemas reais, nem tudo pode ser resolvido em tempo e espaço polinomial. Esse é o universo em que vivemos.
Fotos:
bônus: um vÃdeo que eu fiz quando já estava bem cansado.
Aqui.
A Maratona Brasileira de Programação é uma realização da Sociedade Brasileira de Computação, USP, Fundação Carlos Chagas, IBM e diversas universidades e voluntários por todo o Brasi.
