Modalidade Iniciação

As provas da Modalidade Iniciação não exigem nenhum conhecimento especial. As tarefas abordam problemas de lógica e são feitas com lápis e papel. Apesar de não necessitarem de conhecimento anterior, a prática com tarefas de anos anteriores ajuda a obter melhores resultados. Uma fonte de estudo e treinamento é o livro Jogos de Lógica, escrito pelo prof. Wellington Santos Martins, do Instituto de Informática da Universidade Federal de Goiás. O prof. Wellington gentilmente disponibiliza seu livro gratuitamente para participantes da OBI.

Modalidade Programação

A Ementa da Modalidade Programação indica o conhecimento esperado dos competidores em cada Nível da Modalidade Programação.

As provas serão feitas de forma que com os conteúdos especificados para um determinado nível seja possível resolver todas as tarefas daquele nível de forma completa.

Os tópicos possuem links de referência para que o aluno possa iniciar ou aperfeiçoar seus estudos. O conteúdo das referências não limita o escopo das provas, ou seja, as provas podem requerer conhecimentos que não estão presentes em nenhuma das referências. Além disso, algumas referências sugeridas para os tópicos têm uma abordagem muito mais profunda que o necessário, dependendo do nível para o qual está treinando. Além disso, algumas referências são em inglês, para competidores em níveis mais avançados.

A ementa foi compilada por Arthur Pratti Dadalto com base no Syllabus da IOI, que também pode ser usado como referência. Para comentários, críticas ou sugestões entre em contato com a Coordenação da OBI (olimpinf@ic.unicamp.br ou corretor.obi@gmail.com).

A seguinte convenção é utilizada para definir os tópicos que podem ser cobrados na OBI em cada um de seus níveis:

[J] Tópico que pode ser cobrado a partir do Nível Júnior.
[N1] Tópico que pode ser cobrado a partir do Nível 1.
[N2] Tópico que pode ser cobrado a partir do Nível 2 (no Nível Sênior podem estar presentes os mesmos tópicos do Nível 2).
[S] Tópico que pode ser cobrado na Seletiva para a IOI.
  1. Conceitos básicos de Aritmética e Geometria
    1. [J] Inteiros, operações e comparações.
    2. [J] Propriedades básicas dos inteiros (sinal, paridade, divisibilidade, etc).
    3. [J] Frações.
    4. [J] Linha, segmento de linha, ângulo, triângulo, retângulo, quadrado, circunferência.
    5. [J] Distância Euclidiana. [5]
    6. [J] Teorema de Pitágoras.
    7. [J] Números primos.
    8. [N1] Ponto, vetor, coordenadas no plano.
    9. [N2] Aritmética modular básica: adição, subtração e multiplicação. [21] [30]
    10. [N2] Polígono (vértice, aresta, convexo, área).
    11. [N2] Operações com matrizes (adição, multiplicação e exponenciação).
  2. Conceitos básicos de Matemática Discreta
    1. [J] Conceitos de grafos e árvores
    2. [J] Árvores e suas propriedades básicas, árvores enraizadas. [22] [23][38]
    3. [J] Grafos direcionados e não direcionados. [22] [23] [38]
    4. [J] Grau, caminho, ciclo, conectividade. [22] [23]
    5. [N1] Grafos com pesos, cores ou classificações nas arestas ou vértices. [22] [35]
    6. [N2] Operações simples em inteiros de tamanho arbitrário. [41]
    7. [N2] Algoritmos de força bruta e programação dinâmica com auxílio de máscaras de bits. [51] [52] [53]
    8. [N2] Exponenciação de matrizes para resolver problemas de programação dinâmica. [54]
    9. [S] Quickselect para achar o k-ésimo menor elemento. [55]
  3. Algoritmos em grafos
    1. [J] Percorrer grafos com busca em largura e busca em profundidade. [38] [37]
    2. [N1] Algoritmos de caminho mínimo (Dijkstra, Bellman-Ford, Floyd-Warshall). [46] [47]
    3. [N1] Encontrar componentes conexas.
    4. [N1] Ordenação topológica. [42] [43]
    5. [N1] Árvores geradoras mínimas. [48] [49]
    6. [N2] Encontrar um caminho/ciclo de Euler. [50]
    7. [S] Conjunto de arestas independentes em grafo bipartido (bipartite matching) em O(VE). [56]
  4. Estruturas de dados
    1. [J] Não é necessário, mas é muito útil conhecer a STL usando C++. [59]
    2. [J] Pilhas e filas. [60]
    3. [J] Listas ligadas. [61]
    4. [J] Representação de grafos.
    5. [J] Árvore de busca binária estática. [62]
    6. [N1] Heap binário. [63]
    7. [N1] Conjuntos disjuntos: Union-find. [64]
    8. [N1] Árvore de Fenwick (binary indexed tree) 1D. [65]
    9. [N1] Menor ancestral comum: algoritmo para responder perguntas em O(logN). [66]
    10. [N2] Árvore de Fenwick (binary indexed tree) 2D. [65]
    11. [N2] Árvore de segmentos (Segment tree). [67] [68] [69]
    12. [S] Estruturas de dados persistentes.
    13. [S] Divisão em buckets de tamanho N (square root decomposition). [1]
    14. [S] Árvores de busca binária balanceadas (Treaps, splay trees, etc). [70]
    15. [S] Árvore de segmentos 2D. [69]
    16. [S] Tries. [71]
  5. Geometria computacional
    1. [N1] Pontos, vetores, linhas e segmentos de linhas. [72]
    2. [N1] Pontos colineares, vetores paralelos e ortogonais. [72]
    3. [N1] Interseção de duas linhas. [72]
    4. [N2] Compressão de coordenadas. [73]
    5. [N2] Envoltória convexa (convex hull) em O(NlogN). [72]
    6. [N2] Line sweep. [4]
    7. [S] Calcular área de um polígono. [2] [72]
    8. [S] Checar se um polígono contém um ponto. [3] [72]
  6. Referências

    [1] http://www.infoarena.ro/blog/square-root-trick

    [2] https://en.wikipedia.org/wiki/Shoelace_formula

    [3] https://en.wikipedia.org/wiki/Point_in_polygon

    [4]https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/

    [5] https://pt.wikipedia.org/wiki/Distância_euclidiana

    [6] http://www.obmep.org.br/docs/apostila4.pdf

    [7] http://www.ime.usp.br/~pf/algoritmos/aulas/string.html

    [8] https://pt.wikipedia.org/wiki/Fun%C3%A7%C3%A3o_(matemática)

    [9] https://pt.wikipedia.org/wiki/Conjunto

    [10] https://pt.wikipedia.org/wiki/Defini%C3%A7%C3%A3o_recursiva

    [11] http://clubes.obmep.org.br/blog/texto_002-principio-das-casas-dos-pombos/

    [12]http://clubes.obmep.org.br/blog/texto_006-principio-fundamental-de-contagem/principio-fundamental-de-contagem-generalizacao/

    [13]http://vestibular.uol.com.br/ultnot/resumos/progressao-aritmetica-geometrica.jhtm

    [14] http://www.mat.uc.pt/~mat1131/Fibonacci.html

    [15] https://pt.wikipedia.org/wiki/Permuta%C3%A7%C3%A3o

    [16] https://pt.wikipedia.org/wiki/Combina%C3%A7%C3%A3o_(matemática)

    [17] http://www.infoescola.com/matematica/fatorial/

    [18] http://www.cin.ufpe.br/~gdcc/matdis/aulas/contagem.pdf

    [19]https://www.artofproblemsolving.com/wiki/index.php?title=Principle_of_Inclusion-Exclusion

    [20] http://www.cin.ufpe.br/~gdcc/matdis/aulas/binomial

    [21]https://pt.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation

    [22] https://pt.wikipedia.org/wiki/Teoria_dos_grafos

    [23] http://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf

    [24] http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/guloso.html

    [25]http://www.decom.ufop.br/toffolo/site_media/uploads/2011-1/bcc402/slides/08._divisao_e_conquista.pdf

    [26] https://en.wikibooks.org/wiki/Algorithms/Backtracking

    [27]https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/

    [28] https://www.codechef.com/wiki/tutorial-dynamic-programming

    [29]https://www.quora.com/I-want-to-learn-memoization-What-are-some-links-with-problems-from-SPOJ-Topcoder-Codeforces

    [30]https://docs.google.com/presentation/d/1ABSFgyRu1I-yKyOxA6RyUqUxqmvxF7XaHySaGmUgSvc/edit?usp=sharing

    [31] https://pt.wikipedia.org/wiki/Algoritmo_de_Euclides

    [32] http://codeforces.com/blog/entry/15729

    [34] http://www.tutorialspoint.com/data_structures_algorithms/sorting_algorithms.htm

    [35] https://pt.wikipedia.org/wiki/Merge_sort

    [36] http://www.ime.usp.br/~pf/algoritmos/aulas/bubi.html

    [37]https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-graphs-and-their-data-structures-section-2/

    [38]https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-graphs-and-their-data-structures-section-1/

    [39] https://pt.wikipedia.org/wiki/Crivo_de_Erat%C3%B3stenes

    [40]https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/

    [41] https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

    [42] https://pt.wikipedia.org/wiki/Ordena%C3%A7%C3%A3o_topol%C3%B3gica

    [43] http://www.geeksforgeeks.org/topological-sorting/

    [44] https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

    [45] http://codeforces.com/blog/entry/16205

    [46]https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-graphs-and-their-data-structures-section-3/

    [47] https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

    [48] http://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm

    [49] http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/kruskal.html

    [50] https://en.wikipedia.org/wiki/Eulerian_path

    [51]https://www.topcoder.com/community/data-science/data-science-tutorials/a-bit-of-fun-fun-with-bits/

    [52] http://codeforces.com/blog/entry/18169

    [53] http://codeforces.com/blog/entry/337

    [54] http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

    [55] http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

    [56]https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-section-2/

    [57] http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

    [58] http://www.geeksforgeeks.org/bridge-in-a-graph/

    [59] https://community.topcoder.com/tc?module=Static&d1=features&d2=082803

    [60] http://www.facom.ufu.br/~madriana/EBD/Pilha.pdf

    [61] https://pt.wikipedia.org/wiki/Lista_ligada

    [62] http://www2.ic.uff.br/~boeres/slides_ed/ed8.pdf

    [63] https://en.wikipedia.org/wiki/Binary_heap

    [64]https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/

    [65]https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

    [66]https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

    [67] http://codeforces.com/blog/entry/15729

    [68] http://codeforces.com/blog/entry/15890

    [69] http://e-maxx.ru/algo/segment_tree

    [70] https://en.wikipedia.org/wiki/Treap

    [71]https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/

    [72]https://www.topcoder.com/community/data-science/data-science-tutorials/geometry-concepts-basic-concepts/

    [73] https://www.quora.com/What-is-coordinate-compression

Volta ao início