Regras da Seleção 2019

As regras para a seleção das ONI são as seguintes:

1. A seleção das ONI será baseada no estágio e em duas provas: a prova final (que decorreu em Abril) e a prova de seleção. A prova de seleção será uma prova presencial que se realizará em data ainda não definida.
2. Para se ser selecionado para a equipa portuguesa que irá à IOI no Azerbaijão é necessário estar numa das quatro primeiras posições da classificação global. A classificação global é determinada pela pontuação global (definida no ponto 3).
3. A pontuação global é definida pela seguinte fórmula: Total = (Pontos Final/300 + PontosSelecao/400 + PontosEstagio/100) * 100). Em caso de empate, é usada a pontuação obtida na prova de seleção como desempate. Se o empate persistir, a ordem será determinada pelo juri das ONI, tendo por base a performance no estágio de seleção (em termos de mais problemas resolvidos).
4. A pontuação do estágio é entre 0 a 100 de acordo com o cumprimento das regras do estágio que são detalhadas em baixo. O funcionamento desta pontuação está detalhado em baixo.
5. Os quatro concorrentes que passarem na seleção para a IOI serão expostos a um estágio de preparação para a IOI muito semelhante ao estágio de seleção (mas com temas de treino diferentes). Os restantes concorrentes são convidados a assistir e a participar informalmente se quiserem.

Regras do estágio de seleção 2019

As regras para o estágio de seleção das ONI são as seguintes:

1. O estágio está dividido em 7 semanas: 15 a 21 de Abril, 22 a 28 de Abril, 29 de Abril a 5 de Maio, 6 a 12 de Maio, 13 a 19 de Maio, 27 de Maio a 3 de Junho. Cada semana terá um tópico a estudar e terá 3 componentes obrigatórias: leituras recomendadas, resolução de dois a três problemas e uma aula por vídeo.
2. As leituras obrigatórias consistem num conjunto de artigos/capítulos de livros que desenvolvem o tema da semana. Além disso irão incluir pequenas perguntas de consolidação do género "Como usar X para Y?" que devem ser fáceis de responder depois de saber o conteúdo. Nota que não é necessário efetuar estas leituras, apenas saber o seu conteúdo, por isso se já conhecerem o que tratam podem passá-las à frente.
3. Os dois a três problemas dados devem ser resolvidos sem consulta de soluções. Serão sempre problemas do CodeForces, por isso devem criar conta se ainda não tiverem. O prazo limite de resolução é de duas semanas após a data da semana em que forem propostos.
4. Todas as semanas realizar-se-á uma aula online com a duração de uma hora que terá como objetivo permitir aos concorrentes colocar dúvidas e discutirem temas relativos à seleção. As aulas não são de presença obrigatória, mas o seu objetivo é discutir problemas, dúvidas ou quaisquer questões que tenham sobre a seleção, as ONI, a IOI ou outro tema. As aulas serão aos Domingos às 20:30.
5. Cada semana vale 15 pontos do estágio que serão atribuídos caso todos problemas obrigatórios sejam resolvidos. De notar que exceções serão abertas para casos particulares que devem avisar com antecedência, o objetivo destas regras não é "queimar" ninguém, é obrigar a trabalhar. A pontuação final é a soma da pontuação de cada semana até um máximo de 100 pontos.
6. Duas das semanas serão semanas de prova, onde em vez das leituras e problemas obrigatórios, terão uma prova de 2 horas que devem fazer virtualmente. Isto significa que terão uma semana para começar a prova, assim que começarem têm 2 horas para a terminar. Cada prova terá uma pontuação mínima obrigatória que é muito fácil de obter e que será divulgada antes da prova.
7. Além do conteúdo obrigatório, haverá algum conteúdo extra assim como problemas extra em cada semana que lidam com temas mais avançados e problemas mais complicados.
8. Os temas abordados no estágio não serão necessariamente incluídos na prova de seleção, mas é muito provável que um ou mais problemas sejam facilitados depois da exposição a alguns dos temas abordados no estágio.

Sumário do estágio de seleção 2019

A página principal do treino do estágio encontra-se aqui. Segue-se um sumário de tudo o que se vai passar:

15/04 a 21/04, Programação dinâmica
- Básicos de Programação dinâmica (TPC);
- Programação dinâmica em DAG (TPC);
- Programação dinâmica em dígitos (TPC);
- Programação dinâmica em árvores (aula);
- Programação dinâmica com intervalos (aula);
- 3 problemas de TPC;
- Programação dinâmica bitmask (extra);
- Programação dinâmica e combinatória (extra);
- 6 problemas extra;
22/04 a 28/04, Estruturas de dados
- Árvores binárias de pesquisa (TPC);
- Implementações da STL: priority_queue, set, map, queue/stack, deque (TPC);
- Segment trees (TPC);
- Consolidar segtrees: generalizar funções e queries (aula);
- Aplicações em diferentes problemas fundamentais (aula);
- 2 problemas de TPC;
- Outras versões de Segment trees: lazy, 2d (extra);
- Fenwick trees/BIT (extra);
- Disjoint Set Union (extra);
- 4 problemas extra;
29/04 a 05/05, Prova de Treino I
- 5 problemas 2 horas (CodeForces);
06/05 a 12/05, Grafos
- Pesquisas DFS e BFS (TPC);
- Algoritmo de Bellman-Ford (TPC);
- Algoritmo de Dijkstra (TPC);
- Grafos direcionados e TopoSort (aula);
- Componentes fortemente conexos e Pontes (aula);
- 3 problemas de TPC;
- Minimum spanning trees (extra);
- Árvore de caminhos mais curtos (extra);
- Ciclos de Euler (extra);
- Árvore de pontes (extra);
- 3 problemas extra;
13/05 a 19/05, Problemas dinâmicos
- Delta encoding (TPC);
- Decomposição SQRT (TPC);
- Buckets (TPC);
- Segment trees dinâmicas (TPC);
- Truque de reconstrução de estruturas de dados em O(sqrt(q)) (aula);
- Exemplos de problemas dinâmicos (aula);
- 2 problemas de TPC;
- Truque para Segtrees em árvores (extra);
- Sparse tables e árvores/Lowest common ancestor (extra);
- Algoritmo de Mo (extra);
- 5 problemas extra;
20/05 a 26/05, Prova de Treino II
- 5 problemas 2 horas (CodeForces);
27/05 a 03/06, Output-only (otimização)
- Introdução a problemas de otimização (TPC);
- Algoritmos greedy (TPC);
- Hill climbing (TPC);
- Estudo de caso (aula);
- 1 problema de TPC;
- Otimização convexa (extra);
- Pesquisa local (extra);
- 2 problemas extra;