Este espaço é destinado as atividade do grupo de estudos IFCE - CP (Competitive Programming). Nosso foco é treinar alunos para a Olimpíada Brasileira de Informática e a Maratona de Programação. No seguinte link você pode acessar nosso histórico de participações em competições.

Treinamento

Uma das principais formas de treinar para este tipo de competição é resolver muitos exercícios. A seguir temos alguns conjuntos de listas de problemas. Estes conjuntos são baseados em diferentes fontes.

• CP3: conjunto de listas com todos os problemas must try (marcados com *) do livro Competitive Programming 3.
• ITA: conjunto de listas por assunto, que cobrem a imenta da Maratona de Programação. Estas listas foram compiladas pelos alunos do ITA e a nós disponibilizadas pelo competidor Lucas França.
• OBI: conjunto de listas por assunto, compiladas pelo IFCE-CP, indexada pela imenta oficial da Olimpíada Brasileira de informática.

CP3

• Chapter 01 - Introduction
  • 1.3.3 Time to Start the Journey
  • 1.4 The Ad Hoc Problems - parte 1
  • 1.4 The Ad Hoc Problems - parte 2

ITA

• Básico
  • Pilha, fila, lista e deque
  • Sort, next_permutation e prev_permutation
  • Set, map e heap
  • Força bruta, guloso
  • Divisão e conquista
  • PDs clássicas
  • PDs não clássicas
  • DFS / BFS
  • Dijkstra e MST
  • Matemática

OBI

1. Conceitos básicos de Aritmética e Geometria
   • [J] Inteiros, operações e comparações;
   • [J] Propriedades básicas dos inteiros (sinal, paridade, divisibilidade,…)
   • [J] Frações;
   • [J] Linha, segmento de linha, ângulo, triângulo, retângulo, quadrado,circunferência;
   • [J] DistânciaEuclidiana;
   • [J] Teorema de Pitágoras;
   • [J] Números primos;
   • [N1]Ponto,vetor,coordenadasnoplano;
   • [N2]Aritimética modular básica: adição, subtração e multiplicação;
   • [N2]Polígono (vértice, aresta, convexo, área);
   • [N2]Operacões com matrizes (adição, multiplicação e exponenciação).
2. Conceitos básicos de Matemática Discreta
   • [J] Indução matemática;
   • [J] Relações (reflexão, simetria, ordem lexicográfica, etc);
   • [J] Funções (injeção, inversa, composição, etc);
   • [J] Conjuntos (inclusão/exclusão, complementos, produto Cartesiano, etc).
   • [J] Definições matemáticas recursivas;
   • [J] Princípio das casas dos pombos;
   • [N1] Contagem (regras da soma e do produto, progressão aritmética e geométrica, números de Fibonacci, etc);
   • [N1] Definições básicas de permutação e combinação;
   • [N1] Função fatorial;
   • [N1] Princípio da inclusão­/exclusão;
   • [N2] Coeficientes binomiais;
   • [N2] Triângulo de Pascal.
3. Conceitos de grafos e árvores
   • [J] Arvóres e suas propriedades básicas, árvore enraizadas;
   • [J] Grafos direcionados e não direcionados;
   • [J] Grau, caminho, ciclo, conectividade;
   • [N1] Grafos com pesos, cores ou classificações nas arestas ou vértices;
   • [N1] Grafos bipartidos;
   • [N1] Grafos com arestas múltiplas;
   • [N2] Caminho/ciclo de Euler/Hamilton.
4. Estratégias de algoritmos
   • [J] Estratégias com loop simples;
   • [J] Força bruta;
   • [J] Algoritmos gulosos;
   • [J] Divisão e conquista;
   • [J] Backtracking;
   • [N1] Programação dinâmica.
5. Algoritmos
   • [J] Algoritmo de Euclides;
   • [J] Teste de primalidade em O(√N);
   • [J] Exponeciacão eficiente;
   • [J] Arrays: máximo, mediana, soma de prefixos, histograma, etc;
   • [J] Algoritmos de ordenação em O(N²);
   • [J] Busca linear e busca binária;
   • [N1] Crivo de Eratóstenes;
   • [N1] Teoria de jogos, posições vencedoras e perdedoras, algoritmo minimax para jogo de forma ótima;
   • [N1] Algoritmos de ordenação em O(NlogN): heap sort, merge sort, etc;
   • [N2] Operações simples em inteiros de tamanho arbitrário;
   • [N2] Algoritmos de força bruta e programção dinâmica com auxílio de máscaras de bits;
   • [N2] Exponenciação de matrizes para resolver problemas de programação dinâmica;
   • [S] Quickselect para achar o k­ésimo menor elemento;
6. Algoritmos em grafos.
   • [J] Percorrer grafos com busca em largura e busca em profundidade;
   • [N1] Algoritmos de caminho mínimo (Dijkstra, Bellman­Ford, Floyd­Warshall);
   • [N1] Encontrar componentes conexas; d. [N1] Ordenação topológica;
   • [N1] Árvores geradoras mínimas;
   • [N2] Encontrar um caminho/ciclo de Euler;
   • [S] Conjunto de arestas independes em grafo bipartido (bipartite matching) em O(V E).
7. Estruturas de dados
   • [J] Não é necessário, mas é muito útil conhecer a STL usando C++;
   • [J] Pilhas e filas;
   • [J] Listas ligadas;
   • [J] Representação de grafos;
   • [J] Árvore de busca binária estática;
   • [N1] Heap binário;
   • [N1] Conjuntos disjuntos: Union­find;
   • [N1] Árvore de Fenwick (binary indexed tree) 1D;
   • [N1] Menor ancestral comum: algoritmo para responder perguntas em O(logN).
   • [N2] Árvore de Fenwick (binary indexed tree) 2D;
   • [N2] Árvore de segmentos (Segment tree);
   • [S] Estruturas de dados persistentes;
   • [S] Divisão em buckets de tamanho √N (square root decomposition);
   • [S] Árvores de busca binária balanceadas (Treaps, splay trees, etc);
   • [S] Árvore de segmentos 2D;
   • [S] Tries.
8. Geometria computacional
   • [N1] Pontos, vetores, linhas e segmentos de linhas;
   • [N1] Pontos colineares, vetores paralelos e ortgonais.
   • [N1] Interseção de duas linhas;
   • [N2] Compressão de coordenadas;
   • [N2] Convex hull em O(N log N);
   • [N2] Line sweep;
   • [S] Calcular área de um polígono;
   • [S] Checar se um polígono contém um ponto;