Log dos treinos - 2007

Treinos

04 de outubro
Haverá dois treinos.
  1. 08:00 - 12:00
  2. 16:00 - 19:00
02 de outubro
A batalha de Waterlooser 28-09-96
15 de setembro
A batalha de ULM/04
06 de setembro
A batalha de ULM/05
31 de agosto
A batalha de ULM/07

Times e Tarefas

Time A concentre-se nos problemas de Grafos e Geometria Computacional.

Time B e C pule apenas a seção Baba.

Time D e E façam todas as tarefas.

Tarefas

Esta lista de tarefas tenta reunir boa parte dos tópicos que são encontrados nas competições de programação. Logo, se quiser obter bons resultados faça TODOS os exercícios. Mas tome cuidado, não fique submetendo um código milhões de vezes sem antes ter parado para pensar aonde está o erro. Habitue-se a passar os problemas com o mínimo de submissões (o ideal é passar de "primeira"). Ou seja, não crie o vício de: "Há!! Não consegui! Vou para o Fórum, ou pesquisar na Internet". Resumindo: Faça certo na primeira vez!

Baba!

Este conjunto de problemas é realmente fácil, e não exige nenhum conhecimento teórico. No entanto é sempre bom fazer estes problemas para poder pegar fluência na linguagem de programação.

Recomendado para: Time D e E.

Site ID Nome do Problema
uva 102 Ecological Bin Packing
uva 10071 Back to High School Physics
uva 10055 Hashmat the brave warrior
uva 136 Ugly Numbers
uva 10035 Primary Arithmetic
uva 10038 Jolly Jumpers
uva 10018 Reverse and Add
uva 10082 WERTYU
uva 101 The Blocks Problem
uva 10300 Ecological Premium
uva 575 Skew Binary
uva 160 Factors and Factorials
uva 10370 Above Average
uva 706 LC-Display
uva 10189 Minesweeper
uva 401 Palindromes
uva 591 Box of Bricks
uva 113 Power of Cryptography
uva 369 Combinations
uva 264 Count on Cantor
uva 108 Maximum Sum
uva 494 Kindergarten Counting Game
uva 492 Pig-Latin
uva 272 TeX Quotes
uva 424 Integer Inquiry
uva 10008 What's Cryptanalysis?
uva 382 Perfection
uva 458 The Decoder

Estrutura de dados

Todo Programador (Cientista da Computação) deve conhecer e saber implementar (sem olhar em anotações) as estruturas de dados básicas. Logo, este é uma um conjunto de problemas fundamental!

Pilhas

Antes de tentar resolver estes problemas consulte a seção 10.1 (pg. 163-164) do CLRS [1], e a página do Professor Paulo Feofiloff sobre pilhas[4].

Site ID Nome do Problema
uva 514 Rails
uva 551 Nesting a Bunch of Brackets
uva 673 Parentheses Balance
uva 732 Anagrams by Stack
uva 586 Instant Complexity
uva 437 The Tower of Babylon
uva 11111 Generalized Matrioshkas

Filas

Antes de tentar resolver estes problemas consulte a seção 10.1 (pág. 164-166) do CLRS [1], e a página do Professor Paulo Feofiloff[4] sobre filas.

Site ID Nome do Problema
uva 540 Team Queue
uva 362 18,000 Seconds Remaining

Árvores

Os problemas que envolvem percurso em árvore são fáceis desde que sejam modelados com uma estrutura de dados simples.

Leia a seção 6.1 - Heaps (pág. 103-104) do CLRS [1] e atente-se em como é representado o Heap, e procure usar está estrutura em alguns problemas deste conjunto. Um Heap é uma árvore binária quase completa (só o último nível pode estar incompleto).

Leia também a página sobre árvore binária e árvore binária de busca do Professor Paulo Feofiloff[4]. Nestas páginas você encontrará uma implementação genérica de árvores que pode ser muito útil.

Site ID Nome do Problema
uva 112 Tree Summing
uva 115 Climbing Trees
uva 122 Trees on the level
uva 615 Is It a Tree?
uva 10701 Pre, in and post
uva 10308 Roads in the North
uva 536 Tree Recovery
uva 548 Tree

Estruturas de dados para conjuntos disjuntos

Quando a tarefa ou subtarefa de um problema é determinar se dois elementos estão no mesmo conjunto. Um simples algoritmo que verifica isto em tempo linear pode estourar o tempo. O algoritmo Union-Find resolve este problema de forma muito eficiente.

Antes de resolver os problemas, leia a seção 21.1 até 21.3 (pág. 398-406) do CLRS [1].

Site ID Nome do Problema
uva 10158 War
uva 10583 Ubiquitous Religions
uva 10608 Friends
uva 793 Network Connections

Ordenação

Algoritmos de Ordenação são fundamentais em Computação pois constantemente usamos tais algoritmos como subrotinas para resolver outros problemas. Logo, é fundamental saber implementar um Algoritmo de Ordenação rápido. Neste conjunto de problemas você terá que implementar e criar variações de algoritmos de ordenação.

Inversões

Antes de resolver leia o Capítulo 2 (pág. 11-28) do CLRS [1] e faça os exercícios: 2.3-1, 2.3-2, 2.3-7. Problema: 2-2 e 2-4. Depois tente resolver este conjunto de problemas.

Site ID Nome do Problema
uva 10062 Tell me the frequencies!
uva 120 Stacks of Flapjacks
uva 299 Train Swapping
uva 612 DNA Sorting
uva 10698 Football Sort
uva 103 Stacking Boxes

Mergesort

Acredito que você já leu o suficiente para resolver estes problemas! =)

Site ID Nome do Problema
uva 10905 Children's Game
uva 10258 Contest Scoreboard
uva 11057 Exact Sum
uva 263 Number Chains
uva 10810 Ultra-QuickSort

Ao terminar estes exercícios leia o Capítulo 6 (pág. 106-160) do CLRS [1]. A estrutura de dados (que pode ser usada para ordenar elementos) é utilizada em alguns Algoritmos de Grafos que você terá contato logo mais.

Recursão

Leia os artigos An Introduction to Recursion, Part 1 e An Introduction to Recursion, Part 2 publicados na página de Tutoriais de Algoritmos do TopCoder [5].

Leia a página Recursão e algoritmos recursivos do Professor Paulo Feofiloff [4].

Site ID Nome do Problema
uva 598 Bundling Newspapers
uva 10063 Knuth's Permutation
uva 839 Not so Mobile
uva 155 All Squares
uva 624 CD
uva 552 Filling the Gaps
uva 725 Division
uva 638 Finding Rectangles
uva 216 Getting in Line
uva 10496 Collectiong Beepers
uva 775 Hamiltonian Cycle
uva 11140 Little Ali's Little Brother!
uva 11108 Tautology
uva 167 The Sultan's Successors
uva 10422 Knights in FEN
uva 539 The Settlers of Catan
uva 10181 15-Puzzle Problem (Difícil)

Grafos

Além do livro CLRS [1], leia também as notas do Livro Algorithms in C: Graph Algorithms de R. Sedgewick feitas pelo Professor Paulo Feofiloff.

Busca em Largura ou em Profundidade

Leia as seções 22.1 - Representação de grafos, 22.2 - Pesquisa primeiro na extensão (Busca em Largura), 22.3 - Pesquisa primeiro na profundidade (Busca em Profundidade) do Capítulo 22 - Algoritmos elementares de grafos (pág. 419-436) do CLRS [1].

Leia os artigos Section 1: Recognizing and Representing a Graph, Section 2: Searching a Graph e Section 3: Finding the Best Path through a Graph publicados na página de Tutoriais de Algoritmos do TopCoder [5].

Site ID Nome do Problema
uva 598 Bundling Newspapers
uva 10063 Knuth's Permutation
uva 839 Not so Mobile
uva 155 All Squares

Componente Fortemente Conexa

Leia a seção 22.5 - Componentes fortemente conectados (pág. 438-441) do CLRS [1].

Veja o verbete Tarjan's strongly connected components algorithm [6] no Wikipedia.

Site ID Nome do Problema
uva 598 Bundling Newspapers
uva 10063 Knuth's Permutation
uva 839 Not so Mobile
uva 155 All Squares

Ordenação topológica

Leia a seção 22.4 - Ordenação topológica (pág. 436-438) do CLRS [1].

Veja o verbete Topological Sorting [7] no Wikipedia.

Site ID Nome do Problema
uva 10305 Ordering Tasks
uva 196 Spreadsheet
uva 11174 Stand in a Line

Pontes e Pontos de Articulação

Leia a página Articulation Points & Biconnected Components (tive que colocar um link para cache do Google).

Veja o verbete Cut vertex [8], no Wikipedia.

Resolva o Problema 22.2 - Pontos de articulação, pontes e componentes biconectados (pág. 443) do CLRS [1].

Site ID Nome do Problema
uva 796 Critical Links
uva 315 Network
uva 10199 Tourist Guide
uva 10972 RevolC FaeLoN

Caminho mínimo

Única origem

Leia o Capítulo 24 - Caminhos mais curtos de única origem (pág. 459-489) do CLRS [1].

Dijkstra

Seção 24.3 - Algoritmo de Dijkstra (pág. 470-475) do CLRS [1].

Site ID Nome do Problema
uva 10959 The Party, Part I
uva 589 Pushing Boxes
uva 10603 Fill
uva 627 The Net
uva 633 A Chess Knight
uva 658 It's not a Bug, it's a Feature!
uva 10801 Lift Hopping

Bellman-Ford

Seção 24.1 - Algoritmo de Bellman-Ford (pág. 470-475) do CLRS [1].

Site ID Nome do Problema
uva 10449 Traffic
uva 558 Wormholes
uva 10557 XYZZY

Ainda sobre Caminhos mais curtos de única origem. Leia a seção 24.2 - Caminhos mais curtos de única origem em grafos acíclicos orientados (pág. 468-470) do CLRS [1]. Muitos problemas onde os grafos são acíclicos você vai conseguir adaptar este algoritmo.

Várias origens

Leia o Capítulo 25 - Caminhos mais curtos de todos os pares (pág. 490-508) do CLRS [1].

Leia a página All-Pairs Shortest Paths do Steven Halim [10]. Você encontrará diversas variações do Algoritmo de Floyd-Warshall e mais exercícios.

Site ID Nome do Problema
uva 523 Minimum Transport Cost
uva 869 Airline Comparison
uva 280 Vertex
uva 567 Risk
uva 10803 Thunder Mountain
uva 10331 The Flyover Construction
uva 423 MPI Maelstrom
uva 10792 The Orc Attack
uva 821 Page Hopping
uva 247 Calling Circles
uva 10724 Road Construction
uva 10543 Traveling Politician
uva 104 Arbitrage

Árvore geradora mínima

Leia o Capítulo 23 - Árvore geradora mínima (pág. 445-458) do CLRS [1].

Site ID Nome do Problema
uva 10816 Travel in Desert
uva 10486 Mountain Village
uva 10457 Magic Car
uva 10147 Highways
uva 10369 Arctic Network
uva 10397 Connect the Campus
uva 10034 Freckles
uva 10462 Is There A Second Way Left?
uva 10600 ACM contest and Blackout

Fluxo Máximo

Leia o Capítulo 26 - Fluxo máximo (pág. 509-554) do CLRS [1].

Visite as páginas Graphs: Maximum flow / Minimum cut (O(nm2) Ford-Fulkerson), Graphs: Maximum flow / Minimum cut (O(n2m) Dinic's algorithm)), Graphs: Minimum cost maximum flow (v. 3.0), Graphs: Minimum cost maximum flow (v. 4.0) do Igor Naverniouk [11].

Site ID Nome do Problema
uva 10330 Power Transmission
uva 820 Internet Bandwidth
uva 10779 Collector's Problem
uva 544 Heavy Cargo
uva 10480 Sabotage

Min-Cut

Leia o artigo A simple min-cut algorithm do Mechthild Stoer e Frank Wagner. (outro link).

Visite a página Graphs: Stoer-Wagner minimum cut in a weighted graph do Igor Naverniouk [11].

Site ID Nome do Problema
uva 10989 Bomb, Divide and Conquer

Geometria Computacional

Leia o Capítulo 33 - Geometria Computacional (pág. 738-762)

Visite a página Geometric routines do Igor Naverniouk. Nela você vai encontrar várias rotinas para Geometria Computacional.

Convex Hull

Site ID Nome do Problema
uva 10065 Useless Tile Packers
uva 681 Convex Hull Finding
uva 218 Moth Eradication
uva 10173 Smallest Bounding Rectangle
uva 10002 Center of Masses

Closest Pair

Visite a página Closest Pair: A Plane Sweep Algorithm do Sam Bakhtiar.

Site ID Nome do Problema
uva 10750 Beautiful Points
uva 10245 The Closest Pair Problem

Com o tempo vou atualizando e melhorando o conteúdo desta lista de Tarefas. TREINE!

Bibliografia
1. Algoritmos: Teoria e Prática, de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, tradução da 2ª edição [americana], Vandenberg D. de Souza, Ed. Campus, 2002. ISBN 85-352-0926-3.
3. Introduction to Algorithms, 2nd edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press and McGraw-Hill Book Company, 2001. ISBN 0-262-03293-7 (MIT Press); ISBN 0-07-013151-1 (McGraw-Hill).
4. Algoritmos, Paulo Feofiloff.
5. Algorithm Tutorial, TopCoder.
6. Componente fortemente conexa: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm, Wikipedia.
7. Ordenação Topológica: http://en.wikipedia.org/wiki/Topological_sorting, Wikipedia.
8. Ponto de Articulação: http://en.wikipedia.org/wiki/Cut_vertex, Wikipedia.
11. igor's code archive, Igor Naverniouk.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License