Brasil ganha ouro inédito na Olimpíada Internacional de Informática

O estudante brasileiro Felipe Abella Cavalcante Mendonça de Souza conquistou a primeira medalha de ouro do país na Olímpiada Internacional d...

O estudante brasileiro Felipe Abella Cavalcante Mendonça de Souza conquistou a primeira medalha de ouro do país na Olímpiada Internacional de Informática.


[Foto: Unicamp]

A Olímpiada Internacional de Informática (International Olympiad in Informatics ou somente IOI) é uma das Olimpíadas Internacionais de Ciências. Tendo a UNESCO como um de seus patrocinadores, a IOI é uma das competições de ciência da computação mais prestigiadas do mundo. Sendo realizada anualmente desde 1989 e é destinada a alunos do Ensino Médio ou que o tenham cursado no ano anterior.

A competição consiste de dois dias de provas, que consistem de problemas computacionais de natureza algorítmica. Os estudantes competem individualmente, com até quatro compondo a delegação de cada país presente no evento (além dos quatro competidores a delegação pode ter até dois líderes). Os estudantes que compõem as delegações nacionais são selecionados através de torneios nacionais de computação.

Os competidores não podem ter mais de 20 anos e devem ter cursado uma instituição de ensino médio durante o período de setembro a dezembro do ano anterior ao ano da IOI da qual eles estão participando.


Foto da IOI 2011 na Tailândia

Aos competidores são dados quatro três problemas computacionais, para cada um dos dois dias de competição, os quais eles têm que resolver em cinco horas.

Cada estudante trabalha individualmente, com um computador e sem ajuda externa, como por exemplo livros, professores, etc. Para resolver os problemas os competidores têm que criar programas em uma das linguagens permitidas (C, C++ e Pascal) e submetê-los antes do final do período de cinco horas.

Após terminar a prova os programas são testados com diversos casos de teste para avaliar sua eficiência e capacidade de gerar respostas corretas, pontos são dados para cada caso de teste acertado.

Felipe, que ingressou na Universidade Federal de Campina Grande (UFCG), foi o terceiro classificado entre mais de 300 participantes, conseguindo 598 de 600 pontos possíveis (há uma medalha de outro para cada 12 participantes). Outros três competidores da equipe brasileira conquistaram medalhas de bronze: Renato Ferreira Pinto Júnior (Colégio Objetivo, São Paulo), Caíque Porto Lira (Colégio Farias Brito, Fortaleza) e Marcos Massayuki Kawakami (Colégio Etapa, São Paulo). Com o resultado, o Brasil ficou à frente de países como Inglaterra, França, Canadá e Alemanha.

A equipe brasileira foi selecionada entre os alunos melhores classificados da Olimpíada Brasileira de Informática (OBI), competição promovida anualmente pela Sociedade Brasileira de Computação (SBC) e organizada, desde 1999, pelo Instituto de Computação (IC) da Unicamp. Em 2011, a OBI contou com cerca de 20 mil inscritos, entre alunos de escolas de nível fundamental e médio de todos os estados do país.

Felipe representa o Colégio Geo, de João Pessoa (PB), e será premiado no encerramento da IOI no dia 28 de julho.

Exemplo real de uma tarefa da Olimpíada

Race
Em conjunto com a IOI, a Cidade de Pattaya sediará uma corrida: a International Olympiad in Racing (IOR) 2011. Como anfitriões, nós temos que encontrar o melhor percurso para a corrida.

Na área metropolitana de Pattaya-Chonburi existem N cidades conectadas por uma rede de N-1 estradas. Cada estrada é bidirecional, conecta duas cidades diferentes e tem um comprimento inteiro em quilômetros. Além do mais, existe exatamente um único caminho possível conectando qualquer par de cidades. Isto é, existe exatamente uma forma de viajar de uma cidade para outra por uma seqüência de estradas sem visitar nenhuma cidade duas vezes.

A IOR tem regras específicas que requerem que o comprimento total de um percurso seja de exatamente K quilômetros, começando e terminado em cidades diferentes. Obviamente, para evitar colisões, nenhuma estrada (e conseqüentemente nenhuma cidade) pode ser usada duas vezes em um percurso. Para minimizar o tráfego, o percurso deve conter um número mínimo de estradas.

Tarefa
Escreva uma função best_path(N,K,H,L) que recebe os seguintes parâmetros:
 N – o número de cidades. As cidades são numeradas de 0 a N-1.
 K – a distância requerida para o percurso da corrida.
 H – uma matriz bidimensional representando as estradas. Para 0 ≤ i < N-1 temos que a estrada i conecta as cidades H[i][0] e H[i][0].
 L – um vetor representando os comprimentos das estradas. Para 0 ≤ i < N-1, o comprimento da estrada i é L[i].
Você pode assumir que todos os valores na matriz H estão entre 0 e N-1, inclusive, e que as estradas descritas nesta matriz conectam todas cidades como mencionado acima. Você pode também assumir que todos os valores no vetor L são inteiros entre 0 e 1 000 000, inclusive.

Sua função deve devolver o menor número de estradas em um percurso válido de comprimento exatamente K. Se não existir tal percurso sua função deve devolver -1.

Exemplo:

Considere o caso ilustrado na Figura 1 onde N=4, K=3.



O percurso pode começar na cidade 0, ir para cidade 1 e terminar na cidade 2. Seu comprimento é de exatamente 1 km + 2 km = 3 km e consiste de duas estradas. Este é o melhor percurso possível; portanto best_path(N,K,H,L) deve devolver 2.

Para ver mais informações sobre esse e os outros problemas aplicados na IOI 2011 visite a página oficial do evento.

Resultados da participação brasileira na IOI

Ano	País-sede	Ouro	Prata	Bronze
1999	Turquia	0	0	0
2000	China	0	0	0
2001	Finlândia	0	1	1
2002	Coreia do Sul	0	0	2
2003	Estados Unidos	0	0	1
2004	Grécia	0	0	2
2005	Polônia	0	0	2
2006	México	0	0	2
2007	Croácia	0	1	2
2008	Egito	0	0	4
2009	Bulgária	0	1	2
2010	Canadá	0	1	2
2011	Tailândia	1	0	3

Fonte: Wikipedia, Unicamp
[Via BBA]