Que tipos de problemas podem aparecer nos concursos?
Os tipos mais comuns de problemas são:
- Problemas de ordenação;
- Problemas com grafos: pesquisa, ciclos, caminhos,…
- Problemas geométricos: intersecção de linhas ou polígnos,…
- Problemas combinatórios: permutações, combinações,…
- Problemas com strings: dicionários, funções de hash, comparações,…
- Problemas matemáticos: mdc, primos, factorização, congruências, triangulo de Pascal, números arbitrariamente grandes,…
- Problemas de simulação;
- Problemas “ad-hoc” (não encaixam em nenhum padrão)
Que tipos de algoritmos/estratégias de resolução devo conhecer para resolver os problemas?
Alguns dos algoritmos mais conhecidos são:
- Greedy (gulosa)
- Backtracking
- Divide-and-conquer
- Programação dinâmica
- Recursividade
- Força bruta (atenção ao tempo limite
)
O livro Programming Challenges: The Programming Contest Training Manual explica estes e outros algoritmos assim como quais as estratégias ganhadoras em concursos de programação
Quais as linguagens de programação permitidas e quais as opções de compilação normalmente usadas para cada uma delas?
- Linguagem C : gcc -Wall -lm
- Linguagem C++: g++ -Wall
- Linguagem Java: javac
Os sistemas de avaliação usados nos concursos correm tipicamente em Linux mas a versão dos compiladores pode variar de prova para prova.
Situações a ter atenção durante os concursos:
- O input é sempre o stdin e o output é sempre o stdout.
- Normalmente, nas primeiras linhas dos dados de entrada surgem alguns números inteiros que anunciam o tamanho das diversas partes do texto que se segue. Isso evita a necessidade de testar a condição de “fim-de-ficheiro”, durante a leitura dos dados.
Note que as linhas com números inteiros que ocorrem no início dos dados de entrada devem ser consumidas bem até ao fim para evitar desalinhamentos na leitura dos dados subsequentes.
Em http://ctp.di.fct.unl.pt/~amd/cpn/2007tiup/etapa5/praticos.html é explicado como isso se faz nas várias linguagens.
- Os dados de saída sempre são escritos na saída padrão (stdout). É necessário respeitar rigorosamente o formato exigido no problema. Qualquer desacerto, mesmo ligeiro, é suficiente para que um programa seja classificado como “Presentation error”. Note que não é possível detectar visualmente certas anomalias nos dados de saída. Por exemplo: um espaço em branco no final duma linha, uma linha em branco no final dos dados, a omissão da mudança de linha na última linha dos dados. Todas estas situações provocam normalmente um “Presentation error”.
- Ler com cuidado a especificação do input e output (e segui-la rigorosamente).
- Ver os casos limite do problema (máximo e mínimo tamanho do input, etc).
- Criar conjuntos de dados diferentes do exemplo e testá-los.
- Flags de compilação (usar sempre o mesmo comando do sistema de avaliação) (ver help do Mooshak).
- Função main() deve terminar com exit(0) (cuidado ao exit(1)).
- Não comparar exactamente doubles ou floats (ex: #define EQUAL(x,y) ((x)-(y) < 0.000001)).
- Usar sempre as estruturas de dados o mais simples possível (ex: se arrays e listas servirem, usar arrays).
Que livros posso/devo levar para os concursos?
Para os concursos pode-se levar todo o tipo de material impresso (nada de ficheiros, calculadoras, palms, etc…) embora com um número limitado de páginas, que variam entre concursos.
Aconselham-se um bom livro de algoritmos, livro(s) de consulta sobre a(s) linguagem(ns) utilizada(s) e um livro de matemática discreta.
Os problemas são em inglês, quem não estiver tão à vontade pode levar um dicionário.
Por último, impressões de problemas resolvidos.
Qual a melhor forma de gerir o tempo vs. utilização do pc num concurso?
Depende das pessoas que compõem as equipas.
Uma boa abordagem costuma ser o “divide and conquer”, ou seja, os três elementos irem resolvendo problemas separadamente do mais fácil para o mais díficil, rodando no computador.
Há alguma disciplina onde seja focada a algoritmia avançada?
Ao longo do curso, muitos dos conhecimentos necessários vão sendo adquiridos, mas se quiseres saber ainda mais inscreve-te em Design e Análise de Algoritmos (DAA)
Onde posso praticar para os concursos?
Existem várias hipóteses, entre as quais resolver problemas de concursos anteriores e praticar online.
Os problemas de algumas MIUP’s anteriores estão na secção de problemas.
O site mais utilizado pela comunidade dos concursos de programação é o repositório de Valladolid.