Seletiva Interna da Maratona Unicamp 2011

O prova da seletiva aconteceu ontem, 18 de Junho. Esse ano conseguimos realizar a seletiva da maratona mais cedo. Essa sempre foi a ideia, já que esperávamos que com times formados, os alunos estivessem mais motivados a treinar nas férias.

Apesar se não estar ajudando com o treinamento, ajudei com a organização da prova, escolhendo alguns dos problemas e ficando de fiscal.

Dos competidores

Foram 23 participantes, sendo que decidimos formar por enquanto apenas 3 times. O restante dos times (2 ou 3) serão formados com base na dedicação, mas ainda não decidimos como será a seleção.

A motivação para essa nova regra é que com base em anos passados, temos que os competidores dos primeiros times são já mais experientes e comprometidos com treinamentos, enquanto o restante era um pessoal mais novo na maratona e muitos desaparecem após a regional. No fim das contas, o intuito de formar os times adicionais é justamente manter os novos competidores motivados para se tornarem bons maratonistas nos anos seguintes.

Competidores

A classificação foi a seguinte (número de problemas entre parênteses):

1. Marcelo Póvoa (9)
2. Douglas Santos (8)
3. Bruno Crepaldi (7)
4. Igor Wolff (7)
5. Ruan Silva (6)
6. Thiago Cavalcante (6)
7. Patrícia Hongo (5)
8. Mauro Lopes (4)
9. Gabriel Borges (4)
10. Victor Pompêo (3)

Comentários gerais: O Mauro desistiu por não ter tempo para treinar e então o Victor Pompêo entrou para o terceiro time.

O Marcelo, que fechou a prova, é de longe o competidor mais experiente. Ao escolhermos os problemas da prova consideramos a possibilidade dele fechá-la, mas nosso objetivo mesmo era classificar os outros competidores e por isso os problemas da prova estavam relativamente fáceis.

A briga esse ano ficou entre o Douglas, Bruno, Igor, Ruan e Thiago. Eles estiveram empatados por um tempo, até que o Douglas, Bruno e Igor despontaram no final da prova.

A revelação foi o Gabriel Borges. Me disseram que ele é bixo, mas não sei se é da Ciência ou Engenharia.

Competidores 2

Dos problemas

Os problemas foram selecionados do SPOJ:

• To and Fro
• Army Strength
• Distinct Subsequences
• Rectangles
• Cow Cars
• Street Parade
• Cleaning Robot
• Sorting Bank Accounts
• Subset sum

Os problemas mais fáceis eram para ser o “To and Fro” e “Army Strength”; Os médios-fáceis eram “Rectangles”, “Street Parade” e “Sorting Bank Accounts”; Os médios-difíceis eram “Distinct Subsequences”, “Cow Cars”, “Cleaning Robot” e “Subset sum”. No final a única diferença foi que o “Rectangles” era mais fácil do que imaginávamos e o “Army Strength” mais difícil.

Além disso, o problema City Game estava entre os problemas originais da prova mas tivemos que remover. A razão é que incluímo-no antes de implementá-lo. Nossa ideia era que uma programação dinâmica O(n^3), explicada em um treino, passasse, mas vimos que os limites exigem um algoritmo O(n^2). Não é ruim que o problema seja mais difícil do que imaginávamos, mas é péssimo o fato de que podíamos ter induzido quem foi no treino a perder tempo com uma solução que estouraria o tempo.

Do futuro

Até agora era o Igor quem estava conduzindo os treinos, mas em breve ele irá fazer um estágio no Facebook (o processo começou na seletiva do ano passado :) e defender antes do final do ano. Com isso, o Mário César, do LOCo, assumirá o cargo de técnico. Embora não tenha experiência na maratona, o Mário é doutorando em Teoria de Computação e conhece vários tópicos importantes vistos na maratona. Além do mais, ele tem acompanhado o Igor nos treinamentos para se familiarizar com a maratona, principalmente a parte de programação.

Mário, o novo coach

Vamos torcer para que a Unicamp se classifique para o mundial esse ano, que será em Varsóvia, Polônia!