CIC0169 - Programação Competitiva

Códigos-fontes produzidos na disciplina CIC0169 - Programação Competitiva, nos cursos de Bacharelado em Ciência da Computação e Bacharelado em Engenharia de Computação da Universidade de Brasília.

Esta disciplina cobre conteúdos importantes para trabalhar a capacidade de resolução de problemas dos competidores iniciantes e intermediários. Para estudar os tópicos específicos de programação competitiva como grafos, strings, teoria dos números, geometria computacional, programação dinâmica etc, consulte o repositório CIC0258 - Tópicos Especiais em Programação Competitiva.

Atenção: o Material Didático (Slides, Exercícios Resolvidos) na íntegra é possível obter no Aprender3/Moodle da disciplina, ou nos repositórios elaborados no decorrer dos últimos anos em:

• GitHub UnBalloon

• GitHub do Projeto de Extensão Maratona de Programação

Cronograma de Aulas

Clique aqui. Última atualização: 10 de novembro de 2024.

Autores

Prof. Dr. Vinícius R. P. Borges

Sumário

Módulo I: Fundamentos de Programação Competitiva

1. Fundamentos de Linguagem C/C++

     1.1. Template C++ (aula 05/04/2023), [String: Classe STL], [String Nativas C], [Vector], [Vetor Nativo C], [Pair], [Tuple]

     1.2. Ordenação e Busca Binária: [sort] [Lower Bound e Upper Bound]

     1.3. Upsolving 1: Codeforces 992A - Nastya and an Array [Solução]

     1.4. Upsolving 2: Codeforces 706B - Interesting drink [Solução]

     1.5. Upsolving 3: Codeforces 25A - IQ Test [Solução]

     1.6. Upsolving 4: Codeforces 50A - Domino Pilling [Solução]

2. Ponteiros e Alocação Dinâmica de Memória

     2.1. Ponteiros e Iterators

     2.2. Alocação Dinâmica de Memória (malloc)

Módulo II: Estruturas de Dados

3. Estruturas de Dados Lineares

     3.1. Fila

     3.2. Pilha [Extra: Pilha de Máximos]

     3.3. Fila de Prioridade Mínima

     3.4. Fila de Prioridade Máxima

     3.5. Fila de Prioridade por Pair - Custom Comparator

     3.6. Upsolving: Codeforces 343B - Alternating Current [Solução]

     3.7. Upsolving: Codeforces 920B - Tea Queue [Solução]

     3.8. Upsolving: Codeforces 1153A - Serval and Bus [Solução]

     3.9. Upsolving: Beecrowd 1523 - Estacionamento Linear [Solução]

     3.10. Upsolving: Beecrowd 2065 - Supermarket Line [Solução]

     3.11. Upsolving Codeforces 982B - Bus of Characters [Solução]

4. Estruturas de Dados Não-Lineares

     4.1. Sets

     4.2. Map

     4.3. Upsolving: Codeforces Good Bye 2020 - Bovine Dilemma [Solução]

     4.4. Upsolving: Codeforces 1703D - Double Strings [Solução]

     4.5. Upsolving: Codeforces 1234D - Distinct Characters Queries [Solução]

5. Soma de Prefixos e Codificação Delta

     5.1. Soma de Prefixos (Prefix sum): Exemplo básico

     5.2. Codificação Delta (Delta encoding, Difference arrays): Exemplo básico

     5.4. Upsolving 1: CSES1646 - Static Range Sum Queries [Solução]

     5.4. Upsolving 2: Codeforces 816B - Karen and Coffee [Solução]

     5.5. Upsolving 3: Codeforces 295A - Greg and Array [Solução]

6. Operadores Bitwise e Bitmasks

     6.1. Operadores Bitwise

     6.2. Bitmasks

     6.3. Upsolving: Codeforces 1421A - XORwice [Solução]

     6.4. Upsolving: Codeforces 1698A - XOR Mixup [Solução]

     6.5. Upsolving: Codeforces 1567B - MEXor Mixup [Solução]

     6.6. Upsolving: CodeTON Round 6B - Friendly Arrays [Solução]

     6.7. Upsolving: Codeforces 579A - Raising Bacteria [Solução]

     6.8. Upsolving: Codeforces 1949A - ABC String [Solução]

Módulo III: Paradigmas de Resolução de Problemas

7. Busca Completa

     7.1. Busca em Profundidade e Backtracking

          7.1.1. Gerando subsets e permutações

          7.1.2. Upsolving 4: Beecrowd 1556 - Removing Letters [Solução]

          7.1.3. Upsolving 5: Codeforces 510B - Fox and Two Dots [Solução]

          7.1.4. Upsolving 6: Codeforces 339C - Xenia and Weights [Solução]

          7.1.5. Upsolving 7: Codeforces 550B - Preparing Olympiad [Solução]

     7.1. Busca em Largura

          7.1.1. Upsolving 1: Beecrowd 1910 - Ajude Clotilde [Solução]

          7.1.2. Upsolving 2: Codeforces 520B - Two Buttons [Solução]

          7.1.3. Upsolving 3: Beecrowd 1907 - Colouring Game Scenarios [Solução]

8. Divisão-e-Conquista

     8.1. Busca Binária

          8.1.1. Implementação Tradicional

          8.1.2. Lower and Upper Bounds

          8.1.3. Busca Binária na Resposta

          8.1.4. Upsolving 1: Codeforces 812C - Sagheer and Nubian Market [Solução]

          8.1.5. Upsolving 2: Codeforces 760B - Frodo and Pillows [Solução]

          8.1.5. Upsolving 3: Codeforces 1538C - Pair of Numbers [Solução]

          8.1.6. Upsolving 4: Beecrowd 1472 - Triângulos [Solução]

          8.1.7. Upsolving 3: Codeforces 1676E - Eating Queries [Solução]

9. Análise amortizada: Two Pointers

     9.1. Problema 2SUM

     9.2. Problema 3SUM

     9.3. Problema Max Len Substring

     9.4. Upsolving 1: Codeforces 1133C - Balanced Teams [Solução]

     9.5. Upsolving 2: Codeforces 1343C - Alternating Subsequence [Solução]