Grupo de Estudos para a
Maratona de Programação
Universidade Federal do
Pernambuco
2007
Agenda


International Collegiate Programming Contest
Maratona de Programação











Informações gerais
Comitê organizador
Histórico
Participação da UFPE no evento
Formato
Por que participar
Regras
Como se preparar
Dicas
Objetivos do Grupo de Estudo
Primeira Atividade
International Collegiate
Programming Contest
International Collegiate
Programming Contest





Conhecido mundialmente como ICPC
Surgiu em 1976
Promovido anualmente pela Association
for Computer Machinery (ACM)
Web site: http://icpc.baylor.edu/icpc/
Diretor: Dr. William B. Poucher,
Professor of Computer Science (Baylor
University)
International Collegiate
Programming Contest


A final mundial de 2006 ocorreu em
Tóquio, Japão. Neste ano, mais de 5000
times disputaram regionais em todo o
mundo.
O time da Warsaw University
(Polônia) foi a grande campeã da final
mundial de 2006, a qual ocorreu em
Tóquio.
International Collegiate
Programming Contest




A competição possui duas etapas: a etapa
regional mundial, realizada em vários países
em todos (?) os continentes, e a final mundial
A etapa regional ocorre no ano anterior à
final mundial
Por exemplo, a final mundial de 2007 irá
suceder as competições regionais que
ocorreram em 2006
Apenas um time por instituição pode
participar da final mundial
International Collegiate
Programming Contest


As competições regionais de 2006
reuniram um total de 6.099 times, de
1756 instituições de ensino
Participação de 82 países nas etapas
regionais ao redor do mundo em 2006
International Collegiate
Programming Contest
International Collegiate Programming
Contest – Regionais Latino Americanas



ACM-ICPC South America Contest within
Brazil
ACM-ICPC South America Contest
outside Brazil
ACM Mexico and Central America
Programming Contest
ACM-ICPC South America
Contest within Brazil




Conhecido no Brasil como Maratona
de Programação
Promovido pela Sociedade Brasileira de
Computação (SBC)
Web site: http://maratona.ime.usp.br
Diretor: Dr. Carlos Eduardo Ferreira,
Professor of Computer Science (IMEUSP)
Maratona de Programação
Informações Gerais
Maratona de Programação –
Informações Gerais





É um evento que nasceu das competições regionais
classificatórias para as finais mundiais do concurso
de programação da ACM
É parte da regional sul-americana do ACM ICPC
Primeira edição ocorreu em 1996
O formato adotado para a competição é o mesmo
formato do ACM ICPC
Destina a alunos de cursos de graduação e início de
pós-graduação na área de Computação
Maratona de Programação –
Informações Gerais




É dividido em duas etapas: a etapa regional,
realizada em várias sedes espalhadas pelo país, e a
etapa nacional, que reune os times classificados em
cada uma das sedes (two-tiered contest)
Um total de 30 times se classificam para a final
nacional
No máximo dois times por instituição se classificam
para a final nacional
Número de vagas para a final mundial depende do
número de total de inscritos
Maratona de Programação –
Informações Gerais

Fórmula para a distribuição de 20 vagas
para a final entre as sedes cadastradas

número_ times_ sede 

vagas_ na _ sede  arredonda 20*
número_ total _ times


Outras 10 vagas são distribuídas entre
sedes que contarem com a participação
de uma instituição medalhista na
competição do ano anterior
Maratona de Programação
Premiação
Maratona de Programação Premiação

A Maratona de Programação da SBC
oferece medalhas aos dez primeiros
colocados na fase final da competição




Ouro para os três primeiros
Prata para o quarto, quinto e sexto
Bronze para o sétimo a décimo lugares
O time campeão recebe uma cópia do
troféu "Maratona de Programação".
Maratona de Programação Premiação


O time campeão da Maratona de
Programação garante participação nas
finais mundiais do ACM-ICPC.
Caso o Brasil receba outras vagas do
comitê diretor da regional sulamericana da competição, estas serão
ocupadas pelos primeiros colocados da
final brasileira.
Maratona de Programação
Comitê Organizador
Maratona de Programação –
Comitê Organizador



A Maratona de Programação só acontece graças ao
trabalho voluntário de muitos entusiastas da idéia
Desde o ano 2000, o responsável pelo concurso no
Brasil é Carlos E. Ferreira do Depto de Ciência da
Computação do IME-USP.
Nos primeiros anos de realização a Maratona foi
organizada por Claudionor Coelho do Depto de
Ciência da Computação da UFMG e por Ricardo
Dahab, do IC da Unicamp
Maratona de Programação –
Comitê Organizador

O Comitê Diretor da Maratona de Programação é
formado por:






David Deharbe, UFRN.
Edson Norberto Caceres, UFMS.
Marcus Vinicius Poggi de Aragão, PUC-RJ.
Raul Fernando Weber, UFRGS.
Rodolfo Jardim de Azevedo, Unicamp.
O diretor da regional sul-americana do ICPC
é Ricardo Dahab, do IC da Unicamp.

http://www.ic.unicamp.br/~acmcntst/
Maratona de Programação
Histórico
Maratona de Programação Histórico

1996 - I Consun (Concurso Nacional de
Software Universitário), Belo Horizonte



Organizado pelos Prof. Claudionor Coelho (DCCUFMG) e Ricardo Dahab (IC-Unicamp)
Os três melhores classificados no Consun
competiram na Maratona de Programação
O único time brasileiro (e sul-americano)
classificado para as finais mundiais do ICPC foi o
time do IC-Unicamp, formado pelos alunos
Alexandre Oliva, Alexandre Volpim e André
Augusto Cesta e pelo técnico Prof. Ricardo Anido.
Maratona de Programação Histórico

As finais ocorreram em 2 de março de
1997 em San Jose, California.
Maratona de Programação Histórico
IC-Unicamp
Maratona de Programação Histórico

1997 - II Consun, Campinas

O único time brasileiro (e sul-americano)
classificado para as finais mundiais do ICPC
foi o time da PUC do Rio de Janeiro,
formado pelos alunos Pedro Miller
Rabinovitch, Diego Fernandes Nehab,
Newton Cunha Sanches e dirigido por
Roberto Ierusalimschy.
Maratona de Programação Histórico


As finais ocorreram no dia 28 de
fevereiro de 1998 em Atlanta, Georgia,
O time da PUC-RJ obteve a 24.
colocação na competição
Maratona de Programação Histórico
PUC-Rio
Maratona de Programação Histórico

1998 - Regional Sul-Americana do ICPC


São Paulo – Brasil, Antofagasta – Chile e Caracas
– Venezuela
Três times sul-americanos (dois do Brasil)
classificaram-se para as finais mundiais do ICPC:



Universidad de Buenos Aires: Dario Robak, Nicolas Stier
Moses, Ignacio Laplagne, e técnico Pablo E. Coll;
UFPE: Carlos Santos da Figueira Filho, Marcelo Medeiros
de Barros, Paulo Borges Oliva e técnica Katia S.
Guimarães;
IME-USP: Eduardo Garcia de Freitas, Marcio Grossi de
Almeida, Sergio Gabriel Tavares e técnico Aritanan
Borges Garcia Gruber.
Maratona de Programação Histórico


As finais ocorreram em 8 a 12 de abril
de 1999 em Eindhoven, Holanda
Os times do IME-USP e da Universidad
de Buenos Aires empataram como o
melhor colocado entre os sulamericanos, obtendo a 28. colocação
na competição

Receberam o título de campeões latinoamericano do concurso
Maratona de Programação Histórico
IME-USP
UFPE
Maratona de Programação Histórico

1999 - Regional Sul-Americana do ICPC


Rio de Janeiro, Recife (Brasil), Talca (Chile),
Buenos Aires (Argentina), Maracaibo (Venezuela)
Dois times sul-americanos (nenhum do Brasil)
classificaram-se para as finais mundiais do ICPC:


Universidad Simon Bolivar: Eduardo Jimenez, Paul
Pacheco, Rodrigo Meneses, e técnico Jose Ramirez;
Universidad de Buenos Aires: Dario Robak, Santiago
Laplagne, Ignacio Laplagne, e técnico Nicolas Stier
Moses
Maratona de Programação Histórico


As finais ocorreram em 18 de março de
2000 em Orlando, Florida
O time da Universidad de Buenos Aires
foi o melhor colocado entre os sulamericanos, obtendo a 22. colocação
na competição

Receberam o título de campeões latinoamericano do concurso
Maratona de Programação Histórico
Sem Fotos 
Maratona de Programação Histórico

Maratona de Programação 2000


São Paulo, Campina Grande, Porto Alegre (Brasil),
Santiago (Chile), Buenos Aires (Argentina), Merida
(Venezuela)
Três times sul-americanos (dois do Brasil)
classificaram-se para as finais mundiais do ICPC:



IC da Unicamp: Guilherme de Lima Ottoni, Ulisses
Furquim Freire da Silva, Vinicius José Fortuna e técnico
Ricardo Anido
Universidad de Buenos Aires: Ariel Futoransky, Alexis
Prus, Sergio Demian Lerner e técnica Irene Loiseau
IME-USP: Pedro Luis Eira Velha, Ricardo Bueno Cordeiro,
Tiago Tagliari Martinez e técnico Aritanan Gruber
Maratona de Programação Histórico


As finais ocorreram em 10 de março de
2001 em Vancouver, Canadá
O time do IME-USP foi o melhor
colocado entre os sul-americanos,
obtendo a 14. colocação na competição


Medalha de bronze
Receberam o título de campeões latinoamericano do concurso
Maratona de Programação Histórico
IC-Unicamp
IME-USP
Maratona de Programação Histórico

Maratona de Programação 2001


Campinas, Natal, Caxias do Sul (Brasil), Punta
Arenas (Chile), Buenos Aires (Argentina),
Margarita (Venezuela)
Três times sul-americanos (dois do Brasil)
classificaram-se para as finais mundiais do ICPC:



IME-USP: Pedro Luis Eira Velha, Carlos Cardonha, Marcel
Kenji de Carli Silva e técnico Aritanan Gruber;
Universidad de Buenos Aires: Dario Fischbein, Flavia
Bonomo, Sergio Florez, e coach Irene Loiseau;
UFPE: Hugo Santana, Leonardo Cunha, Igor Gatis e
técnica Katia S. Guiimarães;
Maratona de Programação Histórico


As finais ocorreram em 23 de março de 2002
em Honolulu, Hawaii
O time da Universidad de Buenos Aires foi o
melhor colocado entre os sul-americanos,
obtendo a 10. colocação na competição


Medalha de bronze
O título de campeões latino-americano do
concurso
Maratona de Programação Histórico
IME-USP
UFPE
Maratona de Programação Histórico

Maratona de Programação 2002


São Paulo, Recife, Porto Alegre (Brasil), Copiapó (Chile),
Buenos Aires (Argentina), Barquisimeto, Caracas (Venezuela)
Quatro times sul-americanos (três do Brasil) classificaram-se
para as finais mundiais do ICPC:




PUC Rio: Alexandre Correia Pinto, Juliana Abrantes Freire,
Mauricio Carneiro, e coach Marcus Poggi;
UBA: Dario Fischbein, Flavia Bonomo, Sergio Florez, e coach
Guilhermo Durán;
Unicamp: Claus Aranha, Ulisses Silva, Vinicius Fortuna, e coach
Guilherme Ottoni;
UFPE: Alessandro Almeida, Emmanuel Macedo, Pedro Castro, e
coach Sergio Queiroz.
Maratona de Programação Histórico


As finais ocorreram em 25 de março de 2003
em Los Angeles, California
O time da Universidad de Buenos Aires foi o
melhor colocado entre os sul-americanos,
obtendo a 12. colocação na competição


medalha de bronze
título de campeões latino-americano do concurso
Maratona de Programação Histórico
Maratona de Programação Histórico

Maratona de Programação 2003


Campo Grande - Brasil, Campinas - Brasil, Erechim - Brasil,
Fortaleza – Brasil, Concepción - Chile, Buenos Aires Argentina, Maracaibo – Venezuela
Quatro times sul-americanos (dois do Brasil) classificaramse para as finais mundiais do ICPC:




Universidad de Palermo: Christian Knoblauch, Félix Cuello,
Horacio Peña e coach Patricia Gonzalez;
Universidad Simon Bolivar: Carlos Henriquez, Juan José B.
Torrealba, Raimundo Mirisola e coach Vicente Yriarte;
Unicamp: Alberto Miranda, Renato Sousa, Thiago Hirai e coach
Vinicius Fortuna;
UFPE: Mayerber Carvalho, Emmanuel Macedo, Pedro Castro e
coach Katia Guimarães.
Maratona de Programação Histórico


As finais ocorreram em 30 de março de
2004 em Praga, República Checa
O time da Universidad de Palermo foi o
melhor colocado entre os sulamericanos

Receberam o título de campeões latinoamericano do concurso
Maratona de Programação Histórico
Maratona de Programação Histórico

Maratona de Programação 2004



Ocorreu em duas fases no Brasil.
A primeira fase ocorreu no dia 2 de outubro de
2004 em 14 sedes espalhadas pelo país
Trinta e quatro times brasileiros classificaram-se
para a Final Brasileira, disputada nos dias 12 e 13
de novembro de 2004 na Universidade de São
Paulo, São Paulo.
Maratona de Programação Histórico

Cinco times sul-americanos (três brasileiros) classificaram-se
para as finais mundiais do concurso do ICPC em Shanghai, Rep.
Popular da China:
 ITA: Humberto Silva Naves, Carlos Stein Naves de Brito,
Daniel Lelis Baggio e coach Armando Gouveia
 Universidad de Buenos Aires: Francisco (Pancho) Roslan,
Hernán (Pasto) Bandura, Pablo Heiber e coach Dario
Fischbein
 Universidad Simon Bolivar: Carlos Henriquez, Juán José
Bustamante, Raimundo Mirisola e coach Vicente Yriarte.
 Unicamp: Thiago Hirai, Alberto Miranda, Renato Sousa e
coach Vinicius Fortuna
 Universidade Federal do Rio de Janeiro: Debora da Silva,
Thatiana de Oliveira, Tiago Mota e coach Pedro Demasi.
Maratona de Programação Histórico

As finais ocorreram de 3 a 7 de abril de
2005 em Shanghai, República Popular
da China

O time do ITA foi o melhor colocado entre
os sul-americanos, resolvendo 4 problemas
e terminando na 29a. colocação geral.

Receberam o título de campeões latinoamericanos do concurso
Maratona de Programação Histórico
Maratona de Programação Histórico

Maratona de Programação 2005




Ocorreu em duas fases no Brasil.
A primeira fase ocorreu no dia 10 de setembro em
19 sedes espalhadas pelo país
Vinte e nove times brasileiros classificaram-se para
a Final Brasileira, disputada nos dias 11 e 12 de
novembro nas Faculdades COC em Ribeirão Preto,
São Paulo.
Um time foi eliminado por violação às regras
(PUC-Rio Paticumbum Prugurundum)
Maratona de Programação Histórico

2 Times brasileiros classificados para a
final mundial em Houston (2006)


ITA in the case, it is: Carlos Stein Naves de
Brito, Davi Figueiredo, Humberto Silva
Naves, coach Armando R. Gouveia
PUC-Rio Link-EdiSamba: Daniel Fleischman,
Fábio Dias Moreira, Roberto Cavalcante,
coach Marcus Poggi
Maratona de Programação Histórico
Maratona de Programação 2006
178 Times – 82 Instituições
100
90
80
70
60
50
40
30
20
10
0
89 90
83
34
2522
SE
S
3030
23
NE
Times/2004
Times/2005
Times/2006
17
1314
CO
11
57
N
Maratona de Programação 2005
Participação por Estado (1)
70
60
61
57
50
40
30
Times/2004
Times/2005
21
20
10 108
10
10
12
9
8
RJ
PR
0
0
SP
MG
SC
AM
4
810
79
MS
RS
Maratona de Programação 2005
Participação por Estado (2)
10
9
8
7
6
5
4
3
2
1
0
9
8
7
5 5
5
5
4 44
5
3
2
11 1
0
0
1
0 0
0
RN BA CE PB DF ES PE PA MT MA SE
Times/2004
Times/2005
Maratona de Programação 2006
Participação por Região
30
27
25
18
20
Times na Final
Nacional 2005
Times na Final
Nacional 2006
15
10
5
66
2
11
5
4
2
0
N
NE
CO
SE
S
Crescimento da Competição
161 155
178
114 119
68
13
18 21
26
40
22 26
61 60
83 81 82
39
19
96
19
97
19
98
19
99
20
00
20
01
20
02
20
03
20
04
20
05
20
06
200
180
160
140
120
100
80
60
40
20
0
Times
Escolas
Custo da Maratona
100,000
90,000
80,000
70,000
60,000
50,000
40,000
30,000
20,000
10,000
0
IBM
CNPq
Inscrições
Custo Total
2000 2001 2002 2003 2004 2005
Maratona de Programação
Participação da
UFPE no Evento
Participação da UFPE no
Evento




Primeira participação em 1996.
2º Lugar em 1997.
UFPE: Carlos Santos da Figueira Filho,
Marcelo Medeiros e Paulo Borges
Oliva, técnica: Katia Silva Guimarães;
1 Vaga para final mundial.
Participação da UFPE no
Evento



2° Lugar em 1998.
UFPE: Carlos Santos da Figueira Filho,
Marcelo Medeiros de Barros e Paulo
Borges Oliva, técnica Katia S.
Guimarães;
Participação na fase Mundial em
Eindhoven, Holanda.
Participação da UFPE no
Evento


8° Lugar em 1999.
Medalha de Bronze
Participação da UFPE no
Evento




11° Lugar em 2000.
4° e 6° lugares em 2001
O time HSIG consegue uma vaga para
fase mundial.
Hugo Santana, Leonardo Cunha e Igor
Gatis, técnica Katia S. Guimarães;
Participação da UFPE no
Evento




1° e 2° lugares em 2002
Só 1 time por instituição pode ir à fase
mundial em Los Angeles. Que pena 
AM/PM UFPE: Alessandro Almeida,
Emmanuel Macedo, Pedro Castro, e coach
Sergio Queiroz ;
HSIG UFPE: Hugo Santana, Igor Gatis,
Leonardo Cunha, e coach Mozart Araújo
Filho ;
Participação da UFPE no
Evento
Participação da UFPE no
Evento



1° em 2003.
UFPE: Mayerber Carvalho, Emmanuel
Macedo, Pedro Castro e coach Katia
Guimarães
Participação na Final Mundial em
Praga, Republica Checa.
Participação da UFPE no
Evento
Participação da UFPE no
Evento


8° em 2004.
UFPE: Gustavo Carvalho, Marcos Silva,
Renato Ferreira, coach Katia
Guimarães.
Participação da UFPE no
Evento



2005… PC Jam
1° Lugar na fase regional ( 2
problemas ) 
22° Lugar na final brasileira ( 3
problemas ) 
Participação da UFPE no
Evento
Participação da UFPE no
Evento



2006… PC Jam
2° Lugar na fase regional ( 4
problemas ) 
1 vaga para final brasileira na sede.
Maratona de Programação
Formato
Maratona de Programação –
Formato



Times compostos por três alunos e um
técnico – three contestants and a coach
Cada time pode ter no máximo um reserva, e
que pode substituir um competidor apenas
antes do início da competição
Cada time deve ter um nome. Fica a critério
do time escolhê-lo.
Nome dos Times da Final
Nacional 2005
FATEC Americana - Time
1
ICMC - IfThenElse
IME – Atlântico
ITA – 09 Dominus
ITA – In the case, it is
PUC-Rio
Link-EdiSamba
AM: Cai-Cai balão
UnB =o|
UnB =oD
USP Ciências o
quê?
IME USP A
IME USP C
URI younglings
#include “CC-UEM”
UECE - log(n)
UNESP
UFMG lamadivers
UFPE PC Jam
UFS
Cadeirinha Relâmpago
BCC/UFU 02
UFMA “LSD”
UFPA Team
DCC UFRJ DIE Judge
DCC UFRJ Frost Byte
UFRN HDD 1
UFRN JumenTeam
UFRGS 1
Unicamp
Unicamp
Esqueceram de Mim 3
The Empire strikes back
Dois baianos atrás da serra
Maratona de Programação –
Formato




Apenas um computador é alocado para
o time inteiro
Período de competição de 5 horas
Todos os times iniciam a competição
com penalidade de tempo igual a zero
O time que resolver mais problemas,
com menor tempo total como critério
de desempate, é o vencedor
Maratona de Programação –
Formato




Apenas é permitido acesso a materiais
impressos durante o contest
Para cada problema em um problem set o
time deve implementar uma solução para
resolvê-lo e submeter o código fonte aos
juízes para avaliação
As implementações devem ser em C, C++ ou
Java (a critério do time)
Cada solução aceita pelos juízes é premiada
com um balão
Maratona de Programação Formato



A cada solução aceita, o tempo decorrido desde o
início da competição até a submissão da solução
correta é somado ao tempo total do time
A cada solução rejeitada, uma penalidade de 20
minutos é somada ao tempo total do problema
Quando um problema for solucionado pelo time,
todas as penalidades acumuladas associadas ao
problema também serão somadas ao tempo total do
time
Maratona de Programação –
Formato

Cada problema contém:






Informações para contextualização
(background)
O enunciado do problema
Informações sobre a entrada (Input)
Informações sobre a saída (Output)
Exemplo de entrada (Sample Input)
Exemplo de saída (Sample Output)
Maratona de Programação –
Formato

Informações para contextualização
(background)

Contém informações gerais que servem
apenas para dar sentido ao problema,
encaixando-o no que poderia ser uma
situação real no qual o mesmo se aplica.
Maratona de Programação –
Formato

Enunciado do problema



Contém as intruções sobre que tipo de entrada
será fornecida à solução que o time propor e que
tipo de resposta é esperada para a entrada dada.
Ex: Para este problema, seu trabalho é fazer um
programa que, dados dois número N e M, retorne
a soma de todos os número inteiros entre N e M,
inclusive.
Geralmente o enunciado do problema e
background não são divididos no problema,
o que não implica em dificuldade adicional
Maratona de Programação –
Formato

Informações sobre a entrada (Input):

Informações sobre a formatação da entrada


Contém informações sobre as variáveis que devem
ser lidas pela solução submetida


Ex: N é o número inicial, M é o número final
Quais as limitações das informações de entrada


Ex: Cada caso de teste é composto por dois números, N
e M, sendo, respectivamente….
Ex: 1 < N < 1000000, 2 < M < 2000000
Informações sobre como terminar a leitura do
caso de teste

O fim de um caso de teste é indicado por N = M = 0.
Maratona de Programação –
Formato

Informações sobre a saída (Output)

Contém informações sobre como a saída
deverá ser formatada

Ex: Para cada caso de teste, seu programa
deverá implimir uma linha “Instance #i:”, onde
i é o caso de teste corrente, seguida de uma
linha com um número, indicando o somatório
dos números da entrada. Cada número deve
ser impresso em uma única linha.
Maratona de Programação –
Formato

Exemplo de entrada (Sample Input)


Contém um pequeno exemplo sobre o que
é uma entrada válida para o problema
Ex:
18
4 100
00
Maratona de Programação Formato

Exemplo de saída (Sample Output)


Contém a saída para o exemplo de entrada
(Sample Input) dado
Ex:
Instance #1:
36
Instance #2:
5044
Maratona de Programação Formato


Os juízes possuem datasets que são
utilizados para testar a solução
submetida
Esses datasets contém instâncias de
casos de testes bastante diferentes dos
exemplos contidos nos problemas do
problem set
Maratona de Programação –
Formato

Os juízes podem dar uma das seguintes
respostas a uma solução submetida por um
time:






Yes
No –
No –
No –
No –
No –
Wrong Answer
Presentation Error
Time Limit Exceeded
Runtime Error
Compile Error
Maratona de Programação –
Formato

Nenhuma outra informação será dada
ao time caso algum problema tenha
sido detectado na solução submetida. A
única informação que o time obterá dos
juízes, acerca da correção de uma
solução, será uma das respostas
mencionadas
Maratona de Programação Formato

Yes


Resposta dada pelo juíz a uma solução que
passou em todos os testes de caso, dentro
do tempo limite designado para que a
solução submetida pelo time retornasse as
respostas
O time ganha um balão ao receber um Yes
para uma solução submetida
Maratona de Programação –
Formato

No – Wrong Answer


A solução submetida pelo time não
retornou a resposta correta para um ou
mais dos testes de casos contidos no
dataset associado ao problema
O juíz não irá informar em qual teste de
caso a solução submetida pelo time falhou,
ou dar qualquer dica sobre a falha
Maratona de Programação –
Formato

No – Presentation Error




A saída da solução não obedeceu algumas regras
estabelecidas na descrição do problema (Output)
Espaços a mais (ou a menos), bem como quebras
de linhas indevidas ou faltando são os principais
responsáveis por essa rejeição
A solução submetida pelo time está 99% correta:
falta apenas verificar a formatação de saída
Por estar apenas 99% correta, o time não ganha o
balão
Maratona de Programação –
Formato

No – Time Limit Exceeded



Significa que a solução submetida pelo time
demorou mais tempo processando a entrada dos
juízes do que os juízes designaram
Cada problema possui um tempo limite associado
O tempo limite é calculado de acordo com a
complexidade do problema, e multiplicado por um
fator que reflete as capacidades do hardware no
qual o problema será corrigido, linguagem
utilizada, etc.
Maratona de Programação –
Formato

No – Runtime Error



Significa que, durante o processamento
das entradas, o programa abortou a
execução (abnormally)
Pode ocorrer devido a uma exceção não
tratada, NULL pointer, divisão por zero,
devido ao uso de chamadas inválidas, etc.
Os juízes não informarão ao time por que a
falha (Runtime Error) ocorreu
Maratona de Programação –
Formato

No – Compile Error




O código fonte da solução, submetida pelo time, não
compilou na máquina dos juízes
Pode ocorrer devido ao time ter dito que o código
fonte da solução submetida estava em C, quando na
verdade estava em Java (common mistakes)
Pode ocorrer quando o time muda um detalhe no
código fonte e esquece de testar, antes de re-enviar a
solução
Quando o time esquece de importar os headers
necessários.

Ex: #include <esqueci.h>
Maratona de Programação Formato


O time não ganhará mais pontos por
problemas 90% resolvidos, por
elegência na implementação do
algoritmo, ou por algoritmos
extremamente eficientes
The fastest programmers, as opposed
to the fastest programs, win
(programming challenges)
Maratona de Programação Formato

Durante a competição, o time terá direito a:




Imprimir o código fonte de um problema (tasks)
Solicitar esclarecimentos sobre um problema
(clarifications)
Pedir ajuda (S.O.S.)
Isso tudo é solicitado através do ambiente
computacional
Maratona de Programação
Ambiente
Computacional
Maratona de Programação –
Ambiente Computacional

O ambiente para submissão de problemas utilizado
na final nacional é o BOCA – BOCA Online Contest
Administrador



Desenvolvido por Cássio Polpo de Campos (PUC-SP)
http://maratona.ime.usp.br/manualBOCA.html
O sistema operacional utilizado é o Maratona Linux



Contém todas as ferramentas necessárias para o time
durante a competição
http://maratona.ime.usp.br/dicasLinux.html
Sistema operacional Linux adaptado por Cássio Polpo de
Campos para competições de programação
Maratona de Programação
Por que Participar?
By Vinícius Fortuna
Por que Participar?
1. Desafio

Desafios intrigam as pessoas e são uma
ótima forma de exercitar a mente. É um
grande prazer quando conseguimos vencer
um desafio difícil por nossos próprios
méritos, pois nos sentimos orgulhoso e
mais capazes.
Por que Participar?
2. Competição


Participar de uma competição saudável é
sempre uma diversão. Pode ser também um
motivo de orgulho, pois você está lá defendendo
sua universidade, sua cidade, ou mesmo seu
estado, contra equipes do país inteiro.
Além disso também tem sempre aquela rivalidade
característica de competições entre equipes de
uma mesma cidade ou que costumam ficar
próximas na classificação. É muito recompensador
saber que após o esforço de dedicar um tempo à
competição você chegou na frente de rival.
Por que Participar?
3. Desenvolvimento Pessoal


Programar em competições de
programação envolve estar sempre
encontrando problemas novos.
Dessa forma, com a prática, o competidor
consegue desenvolver uma habilidade de
programar muito mais refinada que o
programador mediano.
Por que Participar?

O competidor consegue:






Programar muito mais em menos tempo.
Escrever códigos mais enxutos.
Desenvolver programas mais eficientes.
Reduzir drasticamente o número de erros em seus
programas.
Tornar-se "fluente" em sua linguagem de programação.
Isso é algo a ser valorizado, pois com essas
habilidades o competidor certamente se torna
mais capaz para trabalhar tanto no mercado
quanto na universidade.
Por que Participar?
4. Currículo


A participação em uma competição nacional de
programação pode ser uma boa propaganda para
seu currículo (inclusive para pós-graduação).
De forma similar à idéia de Bill Poucher, diretor da
ACM ICPC, só de alguém estar na universidade já
está entre os melhores. Ser o representante da
universidade é estar entre os "melhores dos
melhores". Passar para a final nacional é estar
entre os "melhores dos melhores dos melhores", e
por aí vai.
Por que Participar?
5. Novos Contatos


Participar da Maratona de Programação é uma boa
oportunidade de conhecer novas pessoas de
diferentes universidades, cidades e mesmo de
outros estados.
E daí pode surgir inclusive novas amizades.
Também é uma chance de fazer novos contatos e
passar a trocar idéias sobre projetos que abordam
temas comuns ou para uma eventual pósgraduação ou mesmo um emprego.
Por que Participar?
6. Prêmios


É claro, toda competição tem sempre seus
prêmios, o que não deixa de ser um estímulo.
Tanto na Maratona de Programação quanto na
OBI a maior parte dos prêmios são medalhas. Na
Maratona há medalhas para os 10 primeiros
colocados. O campeão também ganha um troféu.
Geralmente também há medalhas ou outros
prêmios locais para os melhores do site, por
exemplo.
Por que Participar?

Além das medalhas, os melhores colocados da Maratona
recebem da IBM Internacional umas lembrancinhas tipo
feirinha do Paraguai:





Relógio
Caneta
Agenda eletrônica de 6Kb
Webcam (que só funciona razoavelmente à luz do sol (!) e é
incompatível com WinXP e Linux...)
Infelizmente, apesar de ser uma gigantesca empresa de
informática, seus prêmios não são como os notebooks
entregues em outras competições nacionais como o Desafio
Sebrae… Mas não deixam de ser prêmios.
Por que Participar?
7. Viagens



Viajar é muito bom e eu gosto. A menos que o
competidor seja da cidade do site, ele vai acabar
viajando logo na primeira fase da Maratona.
Normalmente essa viagem é curta e com gastos
bancados pela própria universidade (há exceções).
Se a equipe se classifica para a final nacional, aí é
outra viagem, dessa vez maior.
Por que Participar?
8. Mundial

Na minha opinião o maior estímulo que
alguém pode ter é ir para o Mundial. Mas
esse não é um estímulo para grande parte
dos competidores, pois apenas o primeiro
e provavelmente o segundo da Maratona
vão para o Mundial.
Por que Participar?


No entanto se sua equipe estiver bem
preparada então vale à pena se esforçar
para conseguir ir ao Mundial. É uma
viagem inesquecível ao exterior onde se
entra em contato com pessoas e culturas
do mundo inteiro.
Além disso a emoção de estar
representando o Brasil no exterior entre os
melhores do mundo é incomparável.
Por que Participar?
9. Áreas de Pesquisas Afins
(by Weverton Cordeiro)

Os conhecimentos adquiridos durante os
treinamentos para a Maratona de Programação,
tais como Programação Dinâmica, Backtracking,
Geometria Computacional, etc, podem ser
extremamente úteis caso você decida seguir uma
linha de pesquisa afim, tal como Bioinformática,
Computação Gráfica, Otimização Combinatória,
entre outras.
Por que Participar?
Ex-Maratonistas
(by Carlos E Ferreira)









Alexandre Oliva (Unicamp): sistemas distribuídos
Guilherme Ottoni (Unicamp): concorrência
Rodrigo Schmidt (unicamp): Inteligência Artificial
Pedro Eira (IME): Computação Gráfica
Tiago Martines (IME): Interface homem-máquina
Carlos Cardonha (IME): teoria da computação
Pedro Demasi (UFRJ): linguística computacional
Diego Nehab (PUC-Rio): linguagens de programação
Paulo Oliva (UFPE): IA.
Maratona de Programação
Regras da
Competição
Maratona de Programação Regras





No máximo três times por instituição de ensino ou
departamento
Todos os times de uma mesma instituição ou
departamento devem competir na mesma sede
No máximo dois times de uma mesma instituição ou
departamento se classificam para a final nacional
No máximo um time de uma instituição de ensino se
classifica para a final mundial
Um time só se qualifica à final se resolver no mínimo
dois problemas na regional
Maratona de Programação Regras


Prazo para a inscrição de times deve ser
obedecido
Pedido de inscrição será atendido por ordem
de chegada



uma sede comporta no máximo 50 times
O coach de uma instituição pode ser o coach
de todos os times
O coach deve ser um docente, ou então ser
indicado por um representante da instituição,
mediante preenchimento de um formulário
Maratona de Programação Regras



Qualquer comunicação entre o coach e o time,
durante a competição, é proibida
Bem como a utilização de qualquer dispositivo
eletrônico e material on-line
Times compostos por três competidores oficiais mais
um reserva


O reserva apenas pode substituir um competidor antes do
início da competição
Há certas condições que devem ser satisfeitas por
todos os integrantes do time (exceto coach) para um
time ser considerado elegível
Maratona de Programação Regras



Os membros do time devem ter participado de no
máximo uma final mundial do concurso da ACM
e…
De no máximo 4 (quatro) regionais sul-americanas
do concurso e…
E (adaptado para as competições de 2007)…


Ter iniciado seus estudos universitários no ano de 2002
ou anos posteriores (a contar do início do primeiro curso
universitário do aluno)
Ou ter nascido em 1983 ou anos posteriores
Maratona de Programação Regras

Se (adaptado para as competições de 2007)




Então


o competidor já participou de duas finais mundiais
ou
o competidor já participou de cinco regionais ou
(o competidor iniciou seus estudos após o fim do
ensino médio no ano 2002 ou anos anteriores e o
competidor nasceu em 1983 ou anos anteriores)
o competidor não é elegível
se não

o competidor é elegível
Maratona de Programação
Como se Preparar?
Maratona de Programação –
Como se Preparar?

Para o competidor








Escolher a linguagem.
Noções de Complexidade de Algoritmos
Dominar as estruturas de dados básicas.
Dominar Entrada e Saída
Ficar à vontade com Recursão e Backtracking.
Aprender Grafos.
Aprender Programação Dinâmica.
Aprender técnicas para resolução de problemas
envolvendo geometria computacional
Maratona de Programação –
Como se Preparar?

Para o time


Conhecer as habilidades e fraquezas de
cada um dos colegas
Treinar simulando as mesmas condições
que a competição real (um computador,
caderno de problemas, tempo limitado,
etc.)
Maratona de Programação –
Como se Preparar?

Há sites na Internet com Juízes Online
(Online robot judges), que podem ser
utilizados para treinamento individual ou do
time




http://www.programming-challenges.com
http://acm.timus.ru (Ural State University)
http://acm.uva.es (Universidade de Valladolid)
Lista de discussão

[email protected] (Lista de
Discussão Nacional)
Maratona de Programação
Dicas
Maratona de Programação Dicas

A Maratona de Programação é uma
competição de criação e implementação de
Algoritmos.


Tratamento de erros (quando o escopo da entrada
é bem definido) e Interfaces com o usuário são
detalhes com os quais os competidores não
precisam se preocupar (e não devem)
É melhor escrever nomes de variáveis e
funções sugestivos do que escrever
comentários no código
Maratona de Programação Dicas


O caderno de problemas possui problemas
fáceis, moderados e difíceis. Se um problema
parecer de difícil implementação, considere
abordar outro problema
Entretanto, alguns problemas podem parecer
difíceis, e outros podem parecer fáceis

Ex: Dados dois polígonos, encontrar a área de
intersecção. Simples?
Maratona de Programação Dicas


Certifique-se de que o problema realmente foi
entendido, amntes de partir para a
implementação
Certifique-se de que o programa está correto,
antes de submeter ao juíz. Uma penalidade
pode custar mais caro que 10 minutos
verificando o problema

Após tentar as entradas e saídas de exemplo, crie
instâncias de entrada que exploram os valores
limites especificados no problema
Maratona de Programação Dicas

Procure sempre evitar o processamento
desnecessário de dados, tais como a expansão de
todos os ramos de uma árvore.


Procure definir papeis para cada um dos integrantes
do time durante a competição


Típico erro quando se aprender a programar: testar (i == j)
para se varrer os elementos da diagonal principal de uma
matriz
Times cujos competidores brigam pelo terminal durante a
competição não vão a lugar nenhum
Há apenas um computador disponível, portanto,
procure utilizar o mesmo apenas para digitação de
soluçoes, e maximizar o uso do mesmo
Maratona de Programação Dicas

Caso a sua solução para um problema
receba uma das respostas No – Wrong
Answer ou No – Time Limit
Exceeded por duas vezes seguidas,
considere entregar o problema a outra
pessoa para lê-lo, entendê-lo e
implementá-lo
Maratona de Programação Dicas


Verifique periodicamente o standing. Ele conterá
informações valiosas sobre problemas fáceis e
difíceis. Se vários times acertaram um problema que
seu time ainda não estudou, seria o caso de
considerar estudar esse problema
Entretanto, evite implementar o “algoritmo da
formiga”. Muitas vezes, os times saem resolvendo
problemas na ordem em que aparecem no caderno,
ao invés de utilizar a baixa complexidade do
problema como critério. Assim, seu time pode ter a
falsa sensação de que um problema é fácil, se seguir
os passos de outro time.
Maratona de Programação Dicas


Adicione um loop para estouro de tempo ou então implemente
uma divisão por zero em trechos onde você imagina que seu
programa possa estar falhando, caso seu time receba sucessivas
vezes a resposta No – Wrong Answer. Seu time obterá um bit
de informação, porém em troca de uma penalidade de 20
minutos
Não adianta iniciar um problema nos minutos finais da
competição, uma vez que geralmente os problemas que faltam
ser resolvidos são de compexidade maior. É melhor modelar
alguns problemas no início ou utilizar os minutos finais para a
depuração de problemas já implementados, mas que ainda não
foram aceitos pelo juízes
Maratona de Programação Dicas


Procure adotar uma estratégia para seu time
 Estratégia simples: cada integrante do time pega um
problema para resolver
 Terminal Man: uma única pessoa fica encarregada do
terminal, enquanto os outros dois elaboram os algoritmos e
casos de testes
 Think Tank: todos os problemas são modeloados pelo time,
para finalmente serem definidos os problemas que serão
implementados
Estratégias possuem pontos positivos e negativos, e nem
sempre são adequadas a todos os times. Procure elaborar uma
estratégia que explore ao máximo as capacidades individuais
Grupo de Estudos da UFPE para a
Maratona de Programação
Objetivos do Grupo de Estudos
Objetivos do Grupo de
Estudos



Criar a cultura na UFPE de participação na
Maratona de Programação
Promover a discussão entre os integrantes
sobre a Maratona de Programação
Propor o estudo conjunto de




Estruturas de dados
Ordenação
Aritmética e Álgebra
Análise Combinatória
Objetivos do Grupo de
Estudos







Teoria dos Números
Backtracking
Algoritmos para Busca em Grafos
Programação Dinâmica
Geometria
Propor atividades de pesquisa e
apresentações dos temas acima mencionados
Simulados nos moldes da Maratona de
Programação
Grupo de Estudos da UFPE para a
Maratona de Programação

http://www.cin.ufpe.br/~time-ufpe




Disponibilização de Apresentações
Problem sets
Datasets
Materiais de suporte (livros, apostilas, etc.)
Grupo de Estudos da UFPE para a
Maratona de Programação
Primeira Atividade
(Valendo Nota… )
Grupo de Estudos da UFPE para a
Maratona de Programação

Primeira Atividade do Grupo






Comecem a praticar para o primeiro treino.
Data a ser definida (depende de alocação de
laboratório)
A principio treinos individuais (sem necessidade de
técnico)
Melhores colocados farão parte do time.
Nosso problem set não irá requerer
conhecimento teórico ou técnicas avançadas de
programação …
… mas que irá exigir raciocínio lógico, e uma boa
estratégia.
Outros Grupos de Estudos e
Competições Internas

Grupo de Estudos da Universidade Estadual
do Ceará


CPU – Clube de Programação UCPel


http://cpu.ucpel.tche.br/
Maratona de Programação – DCC UFRJ


http://larces.uece.br/~maratona
http://www.dcc.ufrj.br/~maratona/tiki-index.php
Maratona de Programação dos Alunos do
IME-USP

http://www.ime.usp.br/~cef/maratona.html
Agradecimentos



Vinícius José Fortuna
Carlos Eduardo Ferreira
E às pessoas que, mesmo sem saber,
contribuíram para a elaboração desta
apresentação… 
Referências

The ACM-ICPC Web Site


Competições de Programação


http://maratona.ime.usp.br
Common Mistakes in Online and Real-time Contests


http://lampiao.ic.unicamp.br/maratona
Site oficial da Maratona de Programação


http://icpc.baylor.edu
http://www.math.luc.edu/~anh/281/basics.html
Programming Challenges

http://www.programming-challenges.com
Obrigado