Lista de referências para a prova da maratona 2020

Olá, Pedro e Handel

Vou organizar aqui todas as referências que conheço e podem ser úteis para a prova do dia 14, quanto mais pra cima na lista, mais importante ela é.

Bibliotecas

Lib da PUC

Aqui é a referência mais atualizada da biblioteca da PUC-Rio de ~20 páginas. (https://github.com/FranciscoThiesen/lib-puc-icpc/tree/tmp)

Detalhes sobre ela:

1. Geometria dela é sensacional. Até hoje usada por vários times
2. Tem bastante coisa de grafo
   1. Fluxo máximo
   2. Pontes / Pontos de Articulação
   3. Componentes fortemente conexos
   4. Matching em grafos bipartidos
3. Tem Heavy-Light decomposition, Segment Trees, BIT, Range minimum quero e outras estruturas super úteis.
4. Tem uma parte de strings boa, com suffix array, Rabin-karp (string hashing) e outras coisas bem úteis.

KACTL

Biblioteca super completa e famosa no mundo de programação competitiva. Códigos sempre em c++ e com mais de 14 autores diferentes. (https://github.com/kth-competitive-programming/kactl/tree/master/content)

Aqui você vai achar até coisas mais básicas (tipo fatoração de primos e tal), até coisas bem mais complexas.

spaghetti-source

Outra lib boa com bastante diversidade de código. (https://github.com/spaghetti-source/algorithm)

Tem alguns algoritmos de programação dinâmica clássicos já pronto, o que pode ser útil na prova

Daqui pra baixo, é meio que tudo a mesma coisa.. (bom pra kct, mas não tão famoso/impactante)

Biblioteca do TFG

https://github.com/tfg50/Competitive-Programming/tree/master/Biblioteca

Ele é o participante do codeforces brasileiro com rating mais alto. Os códigos dele são lindos e tem várias implementações lindas e tal.

Biblioteca (do time bem forte da UFMG)

https://github.com/brunomaletta/Biblioteca

Eles vão participar esse ano e já se classificaram pra final mundial 1x. Referência boa de usar tbm

Biblioteca do Tourist

https://github.com/the-tourist/algo Referência de algoritmos usados em competições pelo próprio tourist. Bem completa

Detalhes sobre:

1. Usei algumas vezes o FFT dessa biblioteca, é bem eficiente e bom de usar.
2. Uso Sparse Table dele.
3. Biblioteca de grafos dele é bem completa. Tem até dijkstra e coisas mais simples.

Sites úteis

https://cp-algorithms.com/ -> Muitas implementações + explicações (altas chances de ser útil em algum momento)

Bônus

Algumas implementações pessoais minhas (https://github.com/FranciscoThiesen/algorithms-collection)