Abóbora Contest

Data: 30/11/2019

09:00hrs - 10:00hrs

         Recepção

10:00hrs - 11:00hrs

         Treinamento / Teste dos Equipamentos

11:00hrs - 12:45hrs

         Almoço (livre, por conta do participante)

13:00hrs

         Prova

17:00hrs

         Lanche

         Encerramento

• O Contest realizado pela instituição IF Goiano Campus Rio Verde com o intuito de promover a aprendizagem na área de programação aos participantes.


• Os times serão formados por três alunos, podendo estes participantes serem da mesma instituição ou não. a não presença de um dos integrantes na realização da prova levará  a desclassificação da equipe.


• Para realizar substituições na equipe entrar em contato até o dia 29/11/2019


• É de suma importância o time participar de todos os eventos que irá ocorrer, principalmente a recepção e o treinamento, pois caso ocorra algum problema técnico, o mesmo possa ser relatado para ser resolvido antes que esse problema ocorra em um momento crucial durante a Prova.


• A competição irá abordar diferentes áreas no âmbito da programação, sendo elas desde a parte mais básica como estrutura um código quanto temas mais difíceis como programação dinâmica e implementação de grafos.


• O competidor irá receber uma prova com o enunciado e terá como intuito resolvê-lo, tendo na prova alguns dos casos que irá ser testados e resultados esperados, mas na prova não irá conter todos os casos de testes que será testado pelo sistema.


• A correção dos exercícios é realizada de forma centralizada, sempre que o time realizar uma submissão do exercício errada ele será penalizado no julgamento dos pontos.


• Estes estudantes têm à sua disposição apenas um computador e material impresso (livros, listagens, manuais) para vencer a batalha contra o relógio e os problemas propostos

Premiação da Prova

1. Conceitos básicos de Aritmética e Geometria
   • Inteiros, operações e comparações.
   • Propriedades básicas dos inteiros (sinal, paridade, divisibilidade, etc).
   • Frações.
   • Linha, segmento de linha, ângulo, triângulo, retângulo, quadrado, circunferência.
   • Distância Euclidiana.
   • Teorema de Pitágoras.
   • Números primos.
   • Ponto, vetor, coordenadas no plano.
   • Aritmética modular básica: adição, subtração e multiplicação.
   • Polígono (vértice, aresta, convexo, área).
   • Operações com matrizes (adição, multiplicação e exponenciação).
   
   
2. Conceitos básicos de Matemática Discreta
   • Conceitos de grafos e árvores
   • Arvores e suas propriedades básicas, árvore enraizadas.
   • Grafos direcionados e não direcionados.
   • Grau, caminho, ciclo, conectividade.
   • Grafos com pesos, cores ou classificações nas arestas ou vértices.
   • Operações simples em inteiros de tamanho arbitrário.
   • Algoritmos de força bruta e programão dinâmica com auxílio de máscaras de bits.
   • Exponenciação de matrizes para resolver problemas de programação dinâmica.
   • Quickselect para achar o k-ésimo menor elemento.
   
   
3. Algoritmos em grafos
   • Percorrer grafos com busca em largura e busca em profundidade.
   • Algoritmos de caminho mínimo (Dijkstra, Bellman-Ford, Floyd-Warshall).
   • Encontrar componentes conexas.
   • Ordenação topológica.
   • Árvores geradoras mínimas.
   • Encontrar um caminho/ciclo de Euler.
   • Conjunto de arestas independentes em grafo bipartido (bipartite matching) em O(VE).
   
   
4. Estruturas de dados
   • Não é necessário, mas é muito útil conhecer a STL usando C++.
   • Pilhas e filas.
   • Listas ligadas.
   • Representação de grafos.
   • Árvore de busca binária estática.
   • Heap binário.
   • Conjuntos disjuntos: Union-find.
   • Árvore de Fenwick (binary indexed tree) 1D.
   • Menor ancestral comum: algoritmo para responder perguntas em O(logN).
   • Árvore de Fenwick (binary indexed tree) 2D.
   • Árvore de segmentos (Segment tree).
   • Estruturas de dados persistentes.
   • Divisão em buckets de tamanho vN (square root decomposition).
   • Árvores de busca binária balanceadas (Treaps, splay trees, etc).
   • Árvore de segmentos 2D.
   • Tries.
   
   
5. Geometria computacional
   • Pontos, vetores, linhas e segmentos de linhas.
   • Pontos colineares, vetores paralelos e ortogonais.
   • Interseção de duas linhas.
   • Compressão de coordenadas.
   • Envoltória convexa (convex hull) em O(NlogN).
   • Line sweep.
   • Calcular área de um polígono.
   • Checar se um polígono contém um ponto.

Referências em inglês.

• cp-algorithms.com
• hackerearth.com

Referências em português.

• neps.academy
• UnBalloon (Github)