Competição de Pré-Outono 03 - Individual

Olá pessoal,

Chegamos à última competição que será feita antes da continuação dos assuntos novos no treinamento e ela foi baseada nas edições passadas do ACM-ICPC Latin America, ou seja, da classificatória da América Latina para o ICPC (final mundial da Maratona). Nela foram resgatadas algumas questões simples de competições anteriores para que os participantes tivessem um contato razoável com o estilo de questão abordado. Sabemos que não é possível continuarmos sempre em um nível baixo, então esperem que as próximas competições virão com um alto nível e, sempre que possível, com os comentários de cada questão também! =D

Início: 2012-03-09 8h30min. Término: 2012-03-09 11h30min.

Problemas:

• A: Dice (LA 2881)
• B: Odd or Even (LA 3656)
• C: He is Offside! (LA 3934)
• D: Bingo! (LA 4806)
• E: Flowers Flourish From France (LA 4810)

Ranking online

Competição de Pré-Outono 02 - Individual

Olá pessoal,

Chegamos ao segundo treino de pré-outono, enquanto ainda não haviam começado as aulas da UFRN e, consequentemente, as aulas da disciplina de Treinamento para Competições de Programação, as quais nos guiarão parcialmente durante os assuntos de cada semana. Nessa competição, foram revisitados os problemas de busca exaustiva, um assunto bem importante de se ter domínio na Maratona, principalmente na fase regional e o resultado foi bem interessante.

Início: 2012-02-24 9h. Término: 2012-02-24 12h30min.

Problemas:

• A: Maximum Product (UVa 11059)
• B: Checking the N-Queens Problem (UVa 932)
• C: 23 out of 5 (UVa 10344)
• D: Numerical Maze (UVa 868)
• E: The New Rule in Euphomia (UVa 10742)
• F: Internal Rate of Return (UVa 11881)

Ranking online

Competição de Pré-Outono 01 - Individual

Olá pessoal,

O treinamento de verão foi finalizado, contudo nós não podemos parar e, por isso, criamos 3 competições do chamado pré-outono, ou seja, as quais ainda estão parcialmente baseadas no assunto do verão, contudo não irão servir para nenhum tipo de ranking. Essa primeira abordou o tema de busca exaustiva e ainda inseriu problemas de buscas mais avançadas, os quais não foram resolvidos por ninguém e, assim, ainda serão revisitados posteriormente.

Início: 2012-02-17 7h30min. Término: 2012-02-17 12h30min.

Problemas:

• A: The broken pedometer (UVa 11205)
• B: Checking the N-Queens Problems (UVa 932)
• C: 15-Puzzle Problem (UVa 10181)
• D: Editing a Book (UVa 11212)
• E: LED Test (UVa 416)
• F: Grid Game (UVa 11553)
• G: Jaguar King (UVa 11163)

Ranking online

Ranking - Competições de Verão 2012

Olá pessoal,

Nesse post será mostrado o ranking final das competições de verão do treinamento, sabendo-se que as pontuações foram atribuídas da seguinte maneira: para competições individuais tinha-se 39 pontos para o 1º e decrescia de 2 em 2 pontos, sendo que os ausentes recebiam a pontuação equivalente à posição abaixo do último presente; nas em equipe a primeira recebia também 39 pontos, contudo decrescia-se de 6 em 6 pontos, com a mesma regra para ausentes.

OBS: Tivemos um problema em medir realmente o desempenho de cada, pois durante as férias foi bem complicado de todos comparecerem. =/

Link para a planilha

POS	Competidor	Total	01	02	03	04	05	06	07	08
1	Helton Duarte	306	39	39	33	39	39	39	39	39
2	Zailton Sachas	292	37	39	35	33	39	37	37	35
3	Erikson Silacier	268	31	33	27	39	39	31	33	35
4	Emerson Carvalho	266	35	39	31	27	31	33	35	35
5	Lucas Daniel	252	23	23	37	27	39	35	29	39
6	Edwyn Luis	242	33	33	25	27	31	29	29	35
6	Micael Felipe	242	25	21	29	39	31	29	33	35
8	Argus Halley	236	23	21	39	33	31	25	29	35
9	Lucas Tomé	232	23	33	25	27	31	29	29	35
10	Caio Santos	226	27	27	25	27	31	25	29	35
11	Isaac Newton	222	29	21	25	27	31	25	29	35

Competição de Verão 08 - Individual

Olá pessoal,

Essa foi a última competição de verão realizada durante o treinamento da UFRN 2012, contudo nossos treinos continuarão durante as aulas. Novamente, realizamos a competição baseada em um Single Round Match (SRM) do Top Coder e todos os que participaram foram considerados empatados em primeiro lugar.

Problemas:

• Top Coder SRM 532

POS	Competidor	Pontuação
1	Helton	39
1	Lucas Daniel	39

Competição de Verão 07 - Individual

Olá pessoal,

Apesar do dia que foi realizada essa competição, seu conteúdo tem mais a ver com o assunto de estruturas de dados, exigindo algum conhecimento de árvores e conjuntos disjuntos.

Início: 2012-03-21 8h30min. Término: 2012-02-07 11h30min.

Problemas:

• A: The Spot Game (UVa 141)
• B: Request for Proposal (UVa 10141)
• C: Stern-Brocot Tree (UVa 11350)
• D: Money Matters (UVa 11690)
• E: Permutation (UVa 11525)
• F: Galactic Bounding (UVa 11966)

POS	Competidor	Resultado	Pontuação	A	B	C	D	E	F
1	Helton Duarte	4 (396)	39	+6		+0	+0		+0
2	Zailton Sachas	3 (372)	37			+4	+0		+1
3	Emerson Carvalho	2 (412)	35			+6			+0
4	Erikson	0 (0)	33		-2	-1
4	Micael Felipe	0 (0)	33			-1

Material para Estudo - Semana 04

Olá pessoal,

A abordagem mais comum em problemas que pedem para contar o número de soluções ou minimizar alguma função é o ataque por busca exaustiva, ou seja, testar todas as soluções possíveis e realizar o que é pedido no problema para cada uma delas. Todavia, esse paradigma de resolução não é muito eficiente e pode levar a muitos TLEs (Time Limit Exceeded), portanto é bom saber em quais situações usá-lo e também maneiras de aumentar a eficiência.

Assunto: Busca Exaustiva

Bibliografia principal:

• Competitive Programming, capítulo 3 (3.2) - Complete Search
• Introduction to Algorithms, apêndice A - Summations
• Top Coder - Computational Complexity: Section 2
• Top Coder - An Introduction to Recursion, Part 1
• Top Coder - An Introduction to Recursion, Part 2

Bibliografia complementar:

• Matemática Concreta, capítulo 2 - Somas
• Introduction to Algorithms, capítulo 3 - Growth of Functions

Problemas sugeridos:

•  UVa 435 (Block Voting): gerar todos os subconjuntos.
• UVa 11205 (The Broken Pedometer): simulação bem interessante, mas deve ser feita com cuidado.
• UVa 624 (CD): problema clássico da mochila, só que com pouquíssimos itens, podendo simular totalmente.
• UVa 11195 (Another n-Queen Problem): melhor problema de busca exaustiva, pois não aceita a solução simples das 8 rainhas, sendo essencial uma boa noção de "escovar bits".

Competição de Verão 06 - Individual

Olá pessoal,

Agora fizemos uma competição para testar a rapidez de resolução de cada um, disponibilizando 15 problemas de 5 juízes online diferentes para serem resolvidos em 3h30min. Esse teste é de grande importância para os participantes de competições, pois resolvendo os problemas fáceis em pouco tempo haverá sobra maior para os mais difíceis! O resultado não foi tão satisfatório, já que nenhum participante conseguiu resolver mais da metade dos problemas, mas o treino continua.

Início: 2012-02-02 8h30min. Término: 2012-02-02 12h.

Problemas:

• A: Reduced ID Numbers (LA 3413)
• B: Simple Encryption (LA 2070)
• C: Encrypted SMS (LA 4095)
• D: Factorial! You Must be Kidding (UVa 10323)
• E: Risk (UVa 567)
• F: Word-Search Wonder (UVa 422)
• G: Find the Clones (SPOJ 2881)
• H: A Bug's Life (SPOJ 3377)
• I: Parket (SPOJ 8374)
• J: Skew Binary (PKU 1565)
• K: Mobile Phones (PKU 1195)
• L: Calling Extraterrestrial Intelligence Again (PKU 1411)
• M: Goat in the Garden (Timus 1084)
• N: Fuses (Timus 1327)
• O: Phone Numbers (Timus 1002)

POS	Competidor	Resultado	Pontuação	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O
1	Helton Duarte	7 (684)	39		+0	+0	-1			+0	+1	+0	+0				+1
2	Zailton Sachas	5 (729)	37	+1			-6			+0	+1	+1	+2
3	Lucas Daniel	2 (195)	35							+0	-5		+0
4	Emerson	2 (294)	33						-5	+0			+4
5	Erikson	1 (177)	31	-2			-1			-2		-3	+0	-2			-1
6	Lucas Tomé	0 (0)	29				-3
6	Micael Felipe	0 (0)	29				-1

Competição de Verão 05 - Individual

Olá pessoal,

A competição desse dia foi realizada juntamente com um Single Round Match do Top Coder, uma competição com 2 divisões na qual os competidores possuem 1h15min para resolver 3 problemas e ainda 15 minutos para desafiar o código dos demais participantes. Tivemos uma baixa participação, todavia não iremos parar o treinamento! Além disso, todos os participantes foram considerados como tendo a mesma colocação, já que havia alguns da 1a e alguns da 2a divisão.

Início: 2012-01-31 9h. Término: 2012-01-31 10h35min.

Problemas:

• Top Coder SRM 531

POS	Competidor	Pontuação
1	Erikson	39
1	Helton	39
1	Lucas Daniel	39
1	Zailton	39

Material para Estudo - Semana 03

Olá pessoal,

Durante essa semana foram estudadas estruturas de dados mais complexas que as anteriores, possibilitando todos a resolverem problemas mais complexos. Destacamos a importância de cada equipe ter as estruturas implementadas e bem testadas para levar no dia de qualquer prova!

Assunto: Estruturas de Dados - Parte 2

Bibliografia principal:

• Competitive Programming, capítulo 2 (2.3.2, 2.3.3 e 2.3.4) - Union-Find, Segment Tree e Fenwick Tree
• Top Coder - Disjoint Set Data Structures
• PEGWiki - Segment Tree
• SPOJ - Lazy Propagation
• Top Coder - Range Minimum Query and Lower Common Ancestor
• Top Coder - Binary Indexed Trees

Bibliografia complementar:

• Introduction to Algorithms, capítulo 17 - Amortized Analysis
• Introduction to Algorithms, capítulo 21 - Data Structures for Disjoint Sets
• Introduction to Algorithms, capítulo 12 - Binary Search Trees
• Introduction to Algorithms, capítulo 13 - Red-Black Trees
• Introduction to Algorithms, capítulo 14 - Augmenting Data Structures
• Top Coder - An Introduction to Binary Search and Red-Black Trees

Problemas sugeridos:

• UVa 793 (Network Connections): boa prática de union-find.
• SPOJ BR 8382 (Banco do Faraó): Segment Tree sem Lazy Propagation; é o exemplo do PEGWiki de maximum/minimum subvector sum.
• UVa 11402 (Ahoy, Pirates!): Segment Tree com Lazy Propagation
• UVa 12086 (Potentiometers): exemplo básico de Fenwick Tree.

Competição de Verão 04 - Equipe

Olá pessoal,

Essa segunda competição em equipe realizou uma competição passada de uma das sedes estadounidenses e, por sorte, foi uma prova bem fácil, comparado ao nível normalmente encontrado em seletivas para o ICPC. O tempo do placar não está sendo mostrado porque o placar usado na hora caiu, então só foi pego a quantidade de problemas resolvidos por equipe.

Início: 2012-01-25 8h. Término: 2012-01-25 13h.

Problemas

• A: Mispelling (SPOJ 2523)
• B: Conversions (SPOJ 2524)
• C: Encoding (SPOJ 2525)
• D: Decoding (SPOJ 2526)
• E: Flipping Burned Pancakes (SPOJ 2527)
• F: Monkey Vines (SPOJ 2528)
• G: Model Rocket Height (SPOJ 2529)
• H: Tiling a Girl with Dominoes (SPOJ 2530)
• I: Spatial Concepts Test (SPOJ 2531)

POS	Competidor	Resultado	Pontuação	A	B	C	D	E	F	G	H	I
1	Erikson, Helton e Micael	6 (???)	39	+0	+0	+1	+0	+0	+3
2	Argus e Zailton	5 (???)	33	+0	+1	+1	+1		+0

Competição de Verão 03 - Individual

Olá pessoal,

Essa é a primeira competição com um assunto específico para estudar e, portanto, que cobrou algo mais complexo dos maratonistas. Praticamente todos os problemas dela estão no material de estudo da semana 02, a qual deu a indicação de vários materiais para ajudar a resolvê-los. No mais, vejamos os problemas e resultados.

Início: 2012-01-24 9h45min. Término: 2012-01-24 12h.

Problemas

• A: ID Codes (UVa 146)
• B: Rails (UVa 514)
• C: Hardwood Species (UVa 10226)
• D: Graph Construction (UVa 10720)
• E: The Forrest for the Trees (UVa 599)
• F: Ferry Loading III (UVa 10901)
• F: Argus (UVa 1203)

POS	Competidor	Resultado	Pontuação	A	B	C	D	E	F	G
1	Argus Halley	3 (553)	39	+0		+2		+0
2	Lucas Daniel	2 (234)	37	+0		+0	-3			-2
3	Zailton Sachas	2 (243)	35	+0		+0	-8
4	Helton Duarte	2 (245)	33	+0	-2	+0	-4
5	Emerson Carvalho	2 (356)	31	+0						+0
6	Micael Felipe	1 (191)	29	+1
7	Erikson Silacier	0 (0)	27	-1

Material para Estudo - Semana 02

Olá pessoal,

Nessa semana nós focamos na base das estruturas de dados, ou seja, aprender a usar bem a STL de C++, a qual pode dar um grande impulso no poder de implementação de um competidor, além de termos a base de grafos para resolver problemas (sem nenhum algoritmo específico ainda). Espero que todos realmente estudem o assunto da semana, pois começa a ficar essencial!

Assunto: Estruturas de Dados - Parte 1

Bibliografia principal:

• Competitive Programming, capítulo 2 (2.1, 2.2 e 2.3.1) - Data Structures with Built-in Libraries e Graph
• Introduction to Algorithms, capítulo 10 - Elementary Data Structures
• Top Coder - Power-up C++ with Standard Template Library: Part 1
• Top Coder - Power-up C++ with Standard Template Library: Part 2
• Introduction to Algorithms, capítulo 6 - Heapsort
• Top Coder - Introduction to graphs and their data structures: Section 1

Bibliografia complementar:

• Top Coder - Computational Complexity: Section 1
• Introduction to Algorithms, capítulo 11 - Hash Tables
• Top Coder - Data Structures

Problemas sugeridos:

• UVa 146 (ID Codes): use o next_permutation da STL.
• UVa 514 (Rails): simule a chegada usando uma pilha.
• UVa 1203 (Argus): nem precisa usar a priority_queue, mas é bom para treinar.
• PKU 1002 (487-3279): usar map ou ordenar tudo no final.
• UVa 599 (The Forest for the Trees): somente teoria dos grafos; não precisa de DFS.
• UVa 10720 (Graph Construction): problema bem específico de implementação do Teorema de Erdos-Gallai, mas que pode ser diferencial em competição.

Competição de Verão 02 - Equipe

Olá pessoal,

Uma competição em equipe com problemas passados: não há forma melhor de treinar! Foi muito boa para sentir as capacidades de cada um, lembrando que as equipes foram montadas de acordo com o resultado da competição individual anterior.

Início: 2012-01-20 08h20min. Término: 2012-01-20 13h20min.

Problemas:

• A: The Agency (LA 5780)
• B: Chain of Fools (LA 5781)
• C: Condorcet Winners (LA 5782)
• D: Everyone out of the Pool (LA 5783)
• E: The Banzhaf Buzz-Off (LA 5784)
• F: GPS I Love You (LA 5785)
• G: Have You Driven a Fjord Lately? (LA 5786)
• H: Mobile (LA 5787)
• I: Wally World (LA 5788)

POS	Competidor	Resultado	Pontuação	A	B	C	D	E	F	G	H	I
1	Emerson, Helton e Zailton	2 (211)	39		-3		+2					+0
2	Edwyn, Erikson e Lucas Tomé	2 (538)	33		+3	-4	+0
3	Caio César	0 (0)	27			-2

Competição de Verão 01 - Individual

Olá pessoal,

Nossa primeira competição começou com problemas de diversos juízes online, a fim de todos os participantes criarem contas neles. O nível presente aqui é baixo, sendo a maioria dos problemas 100% Ad hoc, ou seja, problemas que não se enquadram em categorias específicas.

Início: 2012-01-18 09h30min. Término: 2012-01-18 12h30min.

Problemas:

• A: 1, 10, 100, 1000... (Timus 1209)
• B: Mother Bear (UVa 10945)
• C: 487-3279 (PKU 1002)
• D: 2D-Nim (UVa 10707)
• E: Alaska (UVa 11850)
• F: Number Steps (SPOJ 1112)
• G: Zeros and Ones (UVa 10324)
• H: Java vs. C++ (SPOJ 1163)

POS	Competidor	Resultado	Pontuação	A	B	C	D	E	F	G	H
1	Helton Duarte	7 (633)	39	+1	+0	+0		+1	+0	+0	+1
2	Zailton Sachas	4 (520)	37	+2	+0			+8	+0		-4
3	Emerson Carvalho	3 (389)	35	-1	+0			+4	+0
4	Edwyn Luis	2 (118)	33	-2	+0	-2		-4	+0
5	Erikson Silacier	1 (72)	31	-2				-6	+0	-2
6	Isaac Newton	1 (120)	29						+1
7	Caio Santos	1 (139)	27		-1				+0
8	Micael Felipe	0 (0)	25	-1

Competições de Verão

Olá pessoal,

Vamos treinar? Durante o verão nós realizamos diversas competições para treinar nossas habilidades e aprimorar nossos conhecimentos. Aqui disponibilizaremos todos os links para os problemas das competições além de discutirmos sobre eles e darmos dicas para vocês. As competições foram divididas entre individuais e em equipe e, juntamente com elas, foram elaborados os rankings, para promover uma maior competitividade entre os participantes. O resultado de tudo foi bem legal e esperamos continuar nos dedicando por todo o ano!

As pontuações seguirão um esquema de pontos baseado nos Desafios de Programação no Verão, realizado na USP em 2011, para treinar as equipes para o ACM-ICPC World Finals. Dessa forma, seguirá assim: cada competição individual terá a pontuação dada de 39 a 17 pontos, da posição 1 a 12, decrescendo 2 pontos por posição e, depois dessas, todos receberão 9 pontos; cada competição em equipe dará de 39 a 21 pontos, da posição 1 a 4, decrescendo 6 pontos por posição e, depois dessas, todos receberão 9 pontos. Os ausentes receberão pontuação equivalente a terem ficada 1 posição atrás do último colocado a participar da respectiva competição.

Material para Estudo - Semana 01

Olá pessoal,

Começamos nosso treinamento introduzindo os problemas de competições de programação e, portanto, durante essa semana veremos apenas aspectos básicos. Contudo, temos diversos textos bem interessantes para serem lidos!

Assunto: Introdução a problemas de competições

Bibliografia principal:

• Competitive Programming, capítulo 1 - Introduction
• Top Coder - The Importance of Algorithms
• Introduction to Algorithms, capítulo 1 - The Role of Algorithms in Computing
• Introduction to Algorithms, capítulo 2 - Getting Started
• Top Coder - Planning an Approach to a Top Coder Problem: Section 1
• Top Coder - Planning an Approach to a Top Coder Problem: Section 2

Bibliografia complementar:

• Top Coder - How to Find a Solution
• Top Coder - How to Dissect a Top Coder Problem Statement
• Top Coder - The Best Questions for Would-be C++ Programmers: Part 1
• Top Coder - The Best Questions for Would-be C++ Programmers: Part 2

Problemas sugeridos:

• UVa 11459 (Snakes and Ladders): simulação de jogo usando um array.
• UVa 893 (Y3K Problem): problema com datas, todavia se avançar dia por dia dá TLE.
• UVa 11221 (Magic Square Palindromes): palíndromos e matrizes, lembrando que o tamanho tem que ser quadrado perfeito e não precisa montar a matriz explicitamente.
• UVa 10015 (Joseph's Cousin): faça o crivo de Eratóstenes e percorra somente nos primos encontrados, simulando a operação.
• UVa 278 (Chess): fórmulas fechadas para todas as peças do xadrez.

Material de Estudo para o Treinamento

Olá pessoal,

Durante todo o nosso treinamento postaremos dicas e indicações do material usado rumo ao AMC ICPC South America 2012 e World Finals 2013. Para o estudo em geral, iremos nos basear no material abaixo, contudo sempre que necessário iremos buscar fontes alternativas para complementar o aprendizado. Você que tem dicas sobre algum material interessante, comente abaixo que tentaremos disponibilizá-lo também aqui.

• Introduction to Algorithms [CLRS]
• Concrete Mathematics [CM]
• Competitive Programming [CP]
• Top Coder Algorithm Tutorials [TC]

Seja Bem-Vindo ao Treinamento UFRN 2012

Esse blog é destinado a apresentar os resultados do treinamento da UFRN para a Maratona de Programação 2012. Nele, estarão sempre atualizados os rankings dos competidores, as provas das competições realizadas como treinamento (juntamente com dicas para cada um dos problemas) e relações de sites e material importante para treinamento. Esperamos uma boa participação de alunos para que a UFRN volte a ter um lugar de destaque nas competições de programação.

Quem quer participar dessa jornada?