O que é programação competitiva?

Programação competitiva é um esporte mental, assim como o xadrez, onde o principal objetivo é resolver problemas utilizando programação.

Se você faz ou já fez algum curso de programação ou pesquisou sobre como são as entrevistas de emprego de Big Techs, provavelmente já teve contato com esses tipos de problemas. Em geral eles avaliam seu Problem Solving, ou seja, sua capacidade de modelar uma solução para um determinado problema com limites de tempo e de memória.

Quais os benefícios?

Já deixando claro desde o início que você vai aprender técnicas, algoritmos e estruturas que, sinceramente, provavelmente nunca vai utilizar em outros locais, e, caso utilize, sempre vai ser melhor pegar de uma biblioteca que já foi testada.

Então por que você deveria praticar com programação competitiva? Para aprimorar o bendito do Problem Solving (vou dar ênfase nessa expressão). Programadores resolvem problemas. Você vai resolver problemas mais rápido, mais complexos e utilizando menos recursos do computador.

Muitos não gostam de fazer as coisas sob pressão, seja competindo ou tendo que realizá-las num curto período de tempo, e mesmo assim eu penso que deveriam praticar com os problemas de programação competitiva, porém sem a parte competitiva. Existem vários locais onde você pode testar e praticar seus conhecimentos, vou listar alguns mais à frente.

Principais competições

Essas são as principais competições que existem no Brasil e no mundo. Por mais que você não seja elegível para algumas, você pode recomendar para aquele seu primo do ensino médio que "gosta de mexer no computador". Todas são realizadas anualmente.

OBI: A Olimpíada Brasileira de Informática é a principal competição para alunos do ensino fundamental, médio e até o primeiro ano de um curso de graduação. Existem duas modalidades: iniciação (sem código) e programação, é dividida em vários níveis e é realizada individualmente.

Maratona SBC: Realizada pela Sociedade Brasileira de Computação, ela é voltada para alunos que estão na graduação. É a principal competição da América Latina, tendo em vista que a maior parte dos competidores ativos estão em universidades. É realizada em time de 3 integrantes, tem duas fases, além de ser o filtro para a maratona internacional de programação (ICPC).

ICPC: O International Collegiate Programming Contest é a competição mais importante do mundo nesse ramo. Também é voltada para estudantes universitários, e é realizada em times de 3 integrantes, representando diversos países do mundo.

CodeJam: Realizada pelo Google, a CodeJam é uma competição individual onde qualquer pessoa pode participar. Os melhores colocados ganham um prêmio em dinheiro (até $15,000 USD), além da viagem e estadia no local da prova, caso avancem para a fase final.

Também existem os contests, que são pequenas competições realizadas semanalmente em sites como Codeforces e AtCoder, organizados pela própria comunidade. Quando são patrocinados, os melhores colocados ganham prêmios, como dinheiro ou camisetas e outros brindes. Mas normalmente elas valem somente seu rating, que é como seu score na plataforma. De acordo com seu score você alcança cores, que são semelhantes as ligas presente nos jogos.

Um problema "simples"

Nesse problema você recebe uma lista de n-1 números distintos de 1 até n e deve informar qual o número que está faltando.

Pense por no máximo 10 minutos e então prossiga.

E aí, qual foi sua ideia?

A primeira solução (naive)

A primeira ideia que vem a cabeça é: faz um laço percorrendo de 1 até n e então faz outro laço aninhado para descobrir se o número existe na lista da entrada.

for i in range 1..n:
	existe = False
	
	for j in range 1..n-1:
		if lista[j] == i:
			existe = True
	
	if not existe:
		print(f'O número que está faltando é {i}')

Isso de fato resolve o problema, porém a complexidade de tempo é quadrática no pior caso, pois ele iria percorrer o primeiro laço n vezes e o segundo n-1 vezes.

Segunda solução (otimizada)

Bom, como nosso gargalo é o laço que verifica se o número que estou testando existe ou não, podemos substituí-lo por um dicionário, marcando se o número existe ou não na lista da entrada.

for i in range 1..n-1:
	existe[lista[i]] = True

for i in range 1..n:
	if not existe:
		print(f'O número que está faltando é {i}')

Veja que essa solução só percorre a lista da entrada uma vez, então a complexidade de tempo é linear (assumindo que o acesso ao dicionário é em tempo constante).

Terceira solução (ainda mais otimizada)

Você pode ver os elementos de 1 até n como uma progressão aritmética (P.A.) de razão 1. Conseguimos calcular a soma de uma P.A. com uma fórmula em tempo constante, então se subtrairmos a soma de 1 até n da soma da lista da entrada (que pode ser calculada enquanto é lida), vamos obter o número que está faltando para obter a soma de 1 até n, ou seja, o número que está faltando na sequência.

soma_1_n = (n*(n+1))/2

print(f'O número que está faltando é {soma_1_n - soma_entrada}')

Isso resolve o problema com complexidade de tempo constante.

Link para o problema original no CSES

Existem várias formas de abordar um problema, e várias formas de solucioná-lo, algumas utilizando mais memória ou levando mais tempo que outras. Nosso objetivo é que execute dentro dos limites estipulados pelo problema, que nesse caso são: 1 segundo de Time Limit e 512 MB de Memory Limit. As duas últimas soluções resolvem o problema no CSES, já a primeira dá Time Limit Exceed.

Por onde começar?

Fico feliz se esse conteúdo fez você ter interesse ou curiosidade pela área. Pretendo escrever algo parecido com um roadmap de programação competitiva, com algumas dicas que aprendi ao longo dessa jornada.

Até lá, minhas recomendações são (todas gratuitas):

CSES Handbook: Livro que explica algumas técnicas e algoritmos frequentes em programação competitiva. Vai do iniciante até tópicos bem avançados. Também conta com um problemset com diversos problemas clássicos separados por categorias, onde alguns são explicados no próprio livro.

USACO Guide: É um guia separado por níveis com tópicos que aparecem frequentemente em programação competitiva. Também apresenta questões recomendadas sobre cada tópico. USACO é a competição dos EUA voltada para ensino fundamental e médio.

Você pode praticar com problemas presentes no Codeforces, AtCoder, beecrowd, LeetCode e no TopCoder.

Atualmente curso graduação na Universidade de Brasília e, sempre que posso, incentivo os outros alunos do curso a participarem desse esporte delicinha.