Classes de Problemas na Programação Competitiva

A Programação Competitiva abrange uma vasta gama de tópicos da Ciência da Computação. Para fins didáticos e de treinamento, costumamos categorizar os problemas em grandes classes ou domínios. Abaixo, apresentamos as principais classes que serão abordadas ao longo disciplina e que são frequentes em competições como a Maratona SBC e o ICPC.

1. Ad-Hoc

Problemas classificados como “Ad-Hoc” são aqueles que não requerem o conhecimento prévio de um algoritmo clássico específico (como Dijkstra ou MergeSort). Eles exigem principalmente lógica, criatividade e capacidade de simulação.

  • Na Disciplina: Base para todas as Unidades, especialmente Unidade 1 (Fundamentos).
  • Características: Enunciados muitas vezes longos ou com regras de negócio específicas (como jogos de cartas, simulação de processos físicos simplificados).
  • Desafio: Entender todas as regras e implementá-las sem bugs.

2. Strings

Envolvem o processamento e manipulação de textos. Vai muito além de apenas concatenar ou cortar strings.

  • Na Disciplina: Tópico Extra / Transversal.
  • Tópicos:
    • Busca de padrões (KMP, Rabin-Karp).
    • Estruturas avançadas (Trie, Suffix Array/Tree).
    • Algoritmos de compressão (Huffman).
    • Processamento de palíndromos.

3. Estruturas de Dados e Bibliotecas

O foco aqui é o uso eficiente da memória e do tempo para armazenar e consultar dados. Muitas vezes, o segredo para resolver um problema é escolher a estrutura certa.

  • Na Disciplina: Unidade 6 (Árvores Segmentadas) e uso transversal em todas as unidades.
  • Básicas: Pilhas, Filas, Filas de Prioridade (Heaps), Mapas e Conjuntos (Hash Tables e Árvores Rubro-Negras).
  • Avançadas: Segment Trees, Fenwick Trees (BIT), Union-Find (Disjoint Set Union).
  • Bibliotecas: Domínio da STL (C++) ou Collections (Java/Python).

4. Matemática

Não espere calcular integrais complexas, mas sim usar conceitos de matemática discreta e teoria dos números.

  • Na Disciplina: Unidade 5: Matemática Computacional.
  • Tópicos:
    • Teoria dos Números (Primalidade, MDC/MMC, Aritmética Modular).
    • Combinatória (Arranjos, Combinações, Princípio da Inclusão-Exclusão).
    • Probabilidade Básica.
    • Álgebra (Matrizes, Exponenciação Rápida).

5. Grafos

Uma das áreas mais vastas e importantes. Modela relacionamentos entre objetos.

  • Na Disciplina: Unidade 6: Algoritmos em Grafos.
  • Travessias: BFS (Busca em Largura) e DFS (Busca em Profundidade).
  • Caminhos Mínimos: Dijkstra, Bellman-Ford, Floyd-Warshall.
  • Árvores: Árvores Geradoras Mínimas (Kruskal/Prim), LCA (Lowest Common Ancestor).
  • Fluxo em Redes: Algoritmos de Fluxo Máximo e Corte Mínimo.

6. Paradigmas de Resolução de Problemas

São “meta-técnicas” ou estratégias gerais de design de algoritmos que podem ser aplicadas a diversos tipos de problemas.

  • Na Disciplina: Unidades 2, 3 e 4.
  • Força Bruta (Brute Force): Tentar todas as possibilidades (Backtracking - Unidades 2 e 4).
  • Divisão e Conquista: Quebrar o problema em pedaços menores (ex: MergeSort) (Unidade 2).
  • Algoritmos Gulosos (Greedy): Fazer a escolha ótima localmente na esperança de encontrar o ótimo global (Unidade 4).
  • Programação Dinâmica (DP): Resolver subproblemas e armazenar seus resultados para evitar reprocessamento (Unidade 3).

7. Geometria Computacional

Lidar com formas geométricas, pontos, retas e polígonos no plano cartesiano ou no espaço 3D.

  • Na Disciplina: Unidade 7: Geometria Computacional.
  • Tópicos:
    • Interseção de retas e segmentos.
    • Área de polígonos (Shoelace formula).
    • Envoltória Convexa (Convex Hull).
    • Detectar ponto dentro de polígono.
    • Cuidado redobrado com precisão de ponto flutuante!
Back to top