Saiba o que é e como se preparar para a Maratona de Programação

Programação Competitiva

Olá galera,

Quem já teve interesse em participar de competições de programação mas não sabe por onde começar?

A principal razão de termos criado o CodCad em 2015 (que se tornou o Neps Academy), foi criar uma plataforma onde todo mundo pudesse encontrar material de qualidade e se preparar para as mais importantes competições de programação do país.

Mas o Neps não é a única fonte que existe. Diversos grupos tem se esforçado para manter a cultura de competições de programação dentro das universidades. Hoje nós gostariamos de compartilhar com vocês o material criado pelo pessoal do GEMA (Grupo Estudos para a Maratona de Programação) da Universidade de São Paulo.

A seguir você pode conferir a aula de Introdução a Programação Competitiva e se você estiver interessado em saber mais sobre o trabalho do GEMA, basta seguir o link.


Introdução à Programação Competitiva

"Dado um problema de programação já conhecido, resolva ele no menor tempo possível."

O estudo em programação competitiva se baseia em várias técnicas e algoritmos. Além de conhecê-los, também é importante uma constante prática, para que o tempo que se gasta em cada problema seja menor.

Essências de um problema

Certo, você irá resolver um problema. Para se familiarizar melhor com eles, aqui vai um resumo de como eles costumam aparecer. Normalmente, os enunciados de problemas apresentam a seguinte forma:

  1. Título do Problema: Na maioria dos casos, é realmente só um título, não influenciando em nada o problema. Porém, às vezes ele nos dá uma dica de como o resolver (apresenta alguma tag, etc.)
  2. História do Problema: Mesma coisa que em vestibular. Uma historinha que o cara criou só para o problema ter sentido - e que, assim como em matemática, o que realmente importa está dentro dela. Portanto, é sempre bom ler o enunciado para saber o que fazer.
  3. Constraints (restrições): Embora agora isso não faça muito sentido, mais pra frente vocês verão que isso importa muito. As constraints de determinado problema representam o intervalo que os valores de entrada podem apresentar. Isso irá restringir a complexidade do algoritmo que você desenvolver, ou o tipo de variável que você deve utilizar.
  4. Casos de Teste de Exemplo: Digamos que você leu o enunciado e tem uma noção do que fazer. Então, você vê os casos de teste de exemplo. Eles terão um exemplo de entrada de valores, e logo depois a saída que o problema espera.
  5. Explicação dos Casos de Teste: Em alguns problemas, também é possível que os casos de teste sejam explicados, para facilitar a compreensão do problema.
Exemplo básico

Aqui vai um exemplo básico de problema:

Cremosas em Ferpa (Tempo limite: 1s)

Jaojão é um garoto sagaz. Sempre que possível, ele vai à Ferpa em busca de cremosas aos finais de semana. Agora ele quer dizer a seus amigos a quantiadade kk de cremosas que ele avistou em sua grande terra natal em um final de semana. Seja nn (0<n<1000 < n < 100) o número de cremosas que Jaojão viu no sábado e mm (0<m<1000 < m < 100) o número de cremosas que ele viu no domingo, responda a quantidade kk de cremosas avistadas.

Entrada

A primeira linha contém dois inteiros nn e mm (a quantidade de cremosas avistadas).

Saída

Seu programa deverá apresentar um único inteiro kk, o total de cremosas.

Exemplo

Entrada:
3 4

Saída:
7

Bom, você deve ter percebido que a solução deste problema é apenas somar os dois valores de entrada. Nele, podemos perceber as situações que destaquei acima: o título do problema (que realmente não tem nada a ajudar na solução em si); a história (que tem muita coisa inútil, porém é nela que está descrito o problema). Nesse caso, as constraints são dadas também no enunciado (tanto nn quanto mm são valores inteiros entre 1 e 99, inclusive), isso nos ajuda a escollher os tipos de variáveis que vamos utilizar; e a restrição de tempo do problema é 1 segundo - isto é, a execução do seu problema não pode ultrapassar 1 segundo - vamos ver mais para frente como saber se seu programa será executado dentro do tempo limite.

Introdução à Programação em C++

Se você já estiver familiarizado com alguma linguagem de programação (c, python, pascal), não será tão difícil aprender os conceitos básicos de C++. Em C++, você pode usar tudo que se usa em C (posso, por exemplo, pegar um programa em C e compilá-lo em C++ sem problemas).

Formato do Código em C++
#include <iostream> //incluindo biblioteca que possui alguma função que eu quero

int main() { //funcao principal, a primeira a ser executada em seu codigo
    return 0; //retorno da funcao (opcional)
}

// OBS: '//' (barra barra) representa um comentario de uma linha do codigo
// e sera ignorado na execucao do programa
Introdução à Complexidade

Normalmente, os computadores convencionais conseguem computar cerca de 41084*10^8 comandos por segundo. E é aí que as constraints do problema são úteis. No caso do exemplo anterior, por exemplo, o nn ia até no máximo 100. Ou seja, nós poderiamos fazer um for indo de 0 até nn sem problemas, pois seriam executados apenas cerca de 100 comandos. Porém, se o nn pudesse valer 10910^9, isso não seria possível, pois estouraria o limite de tempo.

Mais para a frente iremos estudar métodos para analisar a complexidade de cada código. Porém, por enquanto, é bom ter algumas noções:

  • Se seu programa depende de nn para o número de execuções, dizemos que ele é de ordem de alguma f(n)f(n) (ele é O(f(n)O(f(n))
  • Se seu programa executa as instruções independentemente de nn (por exemplo, no exemplo acima, era necessário apenas somar dois números), dizemos que ele é constante (O(1)O(1))
  • Um for de 0 a nn apresenta complexidade O(n)O(n)
  • Dois for aninhados de 0 a nn apresenta complexidade O(n2)O(n^2)

Essa parte de complexidade não é tão imposta no início, e será revista mais tarde, então se você não entendeu isso agora, não se preocupe: o seu "eu" do futuro se preocupará com isso.

Respostas dos Judges

Após submeter seu código, você pode receber alguma resposta do site em que mandou:

  1. Accepted (AC): sua solução estava certa e foi aceita.
  2. Wrong Answer (WA): sua solução apresentou alguma saída diferente da esperada.
  3. Time Limit Exceed (TLE): seu programa demorou mais do que o limite para executar.
  4. Memory Limit Exceed (MLE): seu programa está usando mais memória do que deveria.
  5. Runtime Error (RTE): seu programa bugou no meio da execução e travou alguma coisa (fez um acesso indevido, por exemplo).
  6. Presentation Error: Alguns judges apresentam esse erro, que ocorre quando a saída do problema está em um formato diferente do esperado (por exemplo, você colocou espaços ou quebras de linha a mais do que deveria).

Referências

Sites para aprender

É sempre bom ler sobre algoritmos em diferentes sites, para ter diferentes perspectivas sobre um tópico. Entre estes sites, recomendamos:

Em português
Em inglês
Sites para competir

Após ter certa noção de programação competitiva, você já pode começar a treinar e competir. Para isso, existem vários sites que te dão problemas para resolver, e alguns promovem campeonatos (contests) periodicamente, e dão um certo rating de acordo com os problemas resolvidos. Entre os melhores (em minha opinião) estão:

Livro de programação competitiva

O livro mais utilizado por aqueles que estão aprendendo algoritmos e técnicas para maratonas de programação é o Competitive Programming 3, de Steven e Felix Halim. O livro conta com ótimas explicações e código em C++, além de recomendar diversos problemas para cada assunto estudado.

Os problemas recomendados estão todos no UVA, um dos sites citados acima, e seu progresso na resolução de cada tópico do livro pode ser acompanhado em uHunt.

Uma ótima forma de utilizar esse livro é combinando-o a alguns outros recursos citados aqui. Como já foi dito anteriormente, é importante tentar ter diferentes perspectivas sobre um mesmo tópico.

A biblioteca do ICMC conta com apenas uma cópia, mas o livro também pode ser encontrado na internet.

Acompanhando seu progresso

Depois de ter resolvido problemas em alguns dos online judges (sites para competir citados acima), talvez você queira ter uma visão geral do que já fez. Para isso, existem alguns sites que reúnem diversas informações, exibem gráficos, mostram números e listam seus problemas resolvidos. Eles são:

StopStalk: Esse site reúne dados dos online judges mais famosos, mostra um heatmap de atividade, conta e lista todos os seus problemas resolvidos e ainda permite que você acompanhe seus amigos.

Codeforces Visualizer: Esse site faz o mesmo que o de cima, mas focando apenas no Codeforces.

Os dois sites podem servir como grande fonte de motivação, então vale a pena dar uma olhada.


Ficou interessado em Competições de Programação, junte-se a centenas de alunos também interessado sobre o tema no nosso servidor no Discord e troque experiências.

Bons estudos à todos!

Comentários