programação competitiva - Competitive programming

Petr Mitrichev (esquerda) e Gennady Korotkevich (direita), dois programadores competitivos proeminentes durante um concurso.

A programação competitiva é um esporte mental geralmente realizado pela Internet ou rede local , envolvendo participantes tentando programar de acordo com as especificações fornecidas. Os competidores são chamados de programadores esportivos . A programação competitiva é reconhecida e apoiada por várias empresas multinacionais de software e Internet, como Google e Facebook .

Uma competição de programação geralmente envolve o apresentador apresentando um conjunto de problemas lógicos ou matemáticos , também conhecidos como quebra- cabeças , aos competidores (que podem variar em número de dezenas a vários milhares), e os competidores são obrigados a escrever programas de computador capazes de resolver cada problema. . O julgamento é baseado principalmente no número de problemas resolvidos e no tempo gasto para escrever soluções bem-sucedidas, mas também pode incluir outros fatores (qualidade da saída produzida, tempo de execução, tamanho do programa, etc.)

História

Um dos concursos mais antigos conhecidos é o ICPC , que se originou na década de 1970 e cresceu para incluir 88 países em sua edição de 2011.

De 1990 a 1994, Owen Astrachan , Vivek Khera e David Kotz realizaram um dos primeiros concursos de programação distribuídos baseados na Internet inspirados no ICPC.

O interesse pela programação competitiva cresceu muito desde 2000 e está fortemente ligado ao crescimento da Internet, que facilita a realização de concursos internacionais online, eliminando problemas geográficos.

Visão geral

O objetivo da programação competitiva é escrever código-fonte de programas de computador que sejam capazes de resolver determinados problemas. A grande maioria dos problemas que aparecem em concursos de programação são de natureza matemática ou lógica. Essas tarefas típicas pertencem a uma das seguintes categorias: combinatória , teoria dos números , teoria dos grafos , teoria algorítmica dos jogos , geometria computacional , análise de cordas e estruturas de dados . Problemas relacionados à programação de restrições e inteligência artificial também são populares em certas competições.

Independentemente da categoria do problema, o processo de resolução de um problema pode ser dividido em duas grandes etapas: construir um algoritmo eficiente e implementar o algoritmo em uma linguagem de programação adequada (o conjunto de linguagens de programação permitido varia de competição para competição). Essas são as duas habilidades mais testadas em competições de programação.

Na maioria dos concursos, o julgamento é feito automaticamente por máquinas host, comumente conhecidas como juízes. Cada solução apresentada por um concorrente é executada no juiz contra um conjunto de casos de teste (geralmente secretos). Normalmente, os problemas de competição têm um sistema de pontuação tudo ou nada, o que significa que uma solução é "Aceitada" somente se produzir resultados satisfatórios em todos os casos de teste executados pelo juiz e rejeitada caso contrário. No entanto, alguns problemas do concurso podem permitir pontuação parcial, dependendo do número de casos de teste aprovados, da qualidade dos resultados ou de alguns outros critérios especificados. Alguns outros concursos exigem apenas que o competidor envie a saída correspondente aos dados de entrada fornecidos, caso em que o juiz só precisa analisar os dados de saída enviados.

Juízes online são ambientes online nos quais os testes acontecem. Juízes online têm listas de classificação mostrando os usuários com o maior número de soluções aceitas e/ou menor tempo de execução para um problema específico.

Competições notáveis

Existem dois tipos de formatos de competição: curto prazo e longo prazo. Cada rodada de competição de curta duração dura de 1 a 5 horas. Competições de longo prazo podem durar de alguns dias a alguns meses.

Curto prazo

• Concurso Internacional de Programação Colegiada (ICPC) – uma das competições mais antigas, para estudantes de universidades em grupos de 3 pessoas cada
• Olimpíada Internacional de Informática (IOI) – uma das competições mais antigas, para alunos do ensino médio
• American Computer Science League (ACSL) - competição de ciência da computação com porções escritas e de programação, para alunos do ensino fundamental e médio
• CodeChef – concurso realizado a partir de 2009, são três concursos realizados todos os meses e um concurso anual chamado CodeChef SnackDown
• Codeforces Round – normalmente duas horas de competição, realizada toda semana
• Facebook Hacker Cup – competição realizada a partir de 2011, fornecida e patrocinada pelo Facebook
• HackerRank – várias competições
• Gridwars – quatro competições realizadas entre 2003 e 2004.
• Google Code Jam – concurso realizado a partir de 2003, fornecido e patrocinado pelo Google
• IEEEXtreme Programming Competition – competição anual para IEEE Student Members realizada desde 2006 pelo IEEE .
• Topcoder Open (TCO) – Competição de algoritmos realizada desde 2001 pela Topcoder

Na maioria das competições acima, como o número de competidores é bastante grande, as competições geralmente são organizadas em várias rodadas. Eles geralmente exigem participação online em todas as rodadas, exceto na última, que exige participação no local. Uma exceção especial a isso é o IEEEXtreme, que é uma competição anual de programação virtual de 24 horas. Os melhores desempenhos no IOI e ICPC recebem medalhas de ouro, prata e bronze, enquanto nos outros concursos, prêmios em dinheiro são concedidos aos primeiros colocados. Alcançar também os primeiros lugares nas tabelas de pontuação dessas competições pode atrair o interesse de recrutadores de empresas de software e Internet.

Longo prazo

• Semana de Código HackerRank
• ICFP Programming Contest - competição anual de 3 dias realizada desde 1998 pela Conferência Internacional de Programação Funcional
• Partidas da Maratona de Topcoder
• Codechef Long Challenges - realizados todos os meses - com duração de até 10 dias

Inteligência artificial e aprendizado de máquina

• Kaggle – competições de aprendizado de máquina.
• CodeCup – competição de IA de jogos de tabuleiro realizada anualmente desde 2003. As regras do jogo são publicadas em setembro e o torneio final é realizado em janeiro.
• Google AI Challenge – competições semestrais para estudantes que aconteceram de 2009 a 2011
• Halite – Um desafio de programação de IA patrocinado pela Two Sigma, Cornell Tech e Google
• Copa de IA da Rússia abre concurso de programação de inteligência artificial

Concursos com foco em tecnologias de código aberto

• A lista pode estar incompleta

Concurso online e recursos de treinamento

A comunidade de programação em todo o mundo criou e manteve vários recursos da Internet dedicados à programação competitiva. Eles oferecem concursos autônomos com ou sem prêmios menores. Além disso, os arquivos anteriores de problemas são um recurso popular para treinamento em programação competitiva. Existem várias organizações que organizam competições de programação regularmente. Esses incluem:

Participantes notáveis

A lista a seguir é composta por competidores que alcançaram resultados significativos em concursos de programação e, em certa medida, em suas respectivas carreiras. Observe que esta lista exclui pessoas (por exemplo , Mark Zuckerberg ) que podem ter sucesso em sua carreira, mas não tiveram resultados significativos em programação competitiva:

• Gennady Korotkevich (turista)
• Petr Mitrichev (Petr)
• Makoto Soejima (rng_58), um dos ex-administrador e escritor de problemas da Topcoder e membro fundador da Atcoder.
• Tiancheng Lou (ACRush), 2 vezes vencedor do Google Code Jam (2008 e 2009), cofundador da Pony.ai
• Adam D'Angelo , CTO do Facebook e fundador do Quora .
• Scott Wu (scott_wu), CTO do Lunchclub .
• Matei Zaharia (Matei), professor assistente da Universidade de Stanford e fundador da Databricks .

Benefícios e críticas

A participação em concursos de programação pode aumentar o entusiasmo dos alunos pelos estudos de ciência da computação . As habilidades adquiridas em concursos de programação do tipo ICPC também melhoram as perspectivas de carreira, pois ajudam a passar nas "entrevistas técnicas", que muitas vezes exigem que os candidatos resolvam problemas complexos de programação e algorítmicos no local.

Também houve críticas à programação competitiva, principalmente de desenvolvedores de software profissionais. Um ponto crítico é que muitos concursos de programação em ritmo acelerado ensinam aos concorrentes maus hábitos de programação e estilo de código (como uso desnecessário de macros , falta de abstração e comentários OOP, uso de nomes curtos de variáveis, etc.). Além disso, ao oferecer apenas pequenos quebra-cabeças algorítmicos com soluções relativamente curtas, concursos de programação como ICPC e IOI não necessariamente ensinam boas habilidades e práticas de engenharia de software, pois projetos de software reais normalmente têm muitos milhares de linhas de código e são desenvolvidos por grandes equipes ao longo de longos períodos de tempo. Peter Norvig afirmou que, com base nos dados disponíveis, ser um vencedor de concursos de programação correlacionava-se negativamente com o desempenho de um programador em seu trabalho no Google (mesmo que os vencedores do concurso tivessem maiores chances de serem contratados). Norvig afirmou mais tarde que essa correlação foi observada em um pequeno conjunto de dados, mas que não pôde ser confirmada após examinar um conjunto de dados maior

Ainda outro sentimento é que, em vez de "desperdiçar" seu tempo com competição excessiva, resolvendo problemas com soluções conhecidas, os programadores de alto nível devem investir seu tempo na solução de problemas do mundo real.

Literatura

• Halim, S., Halim, F. (2013). Programação Competitiva 3: O Novo Limite Inferior dos Concursos de Programação . Lula.
• Laaksonen, A. (2017). Guia de Programação Competitiva (Tópicos de Graduação em Ciência da Computação). Cham: Springer International Publishing.

Veja também

• Categoria:Competições de ciência da computação
• Código de golfe
• Hackathon

Referências

links externos

Projeto de código aberto para a realização de concursos

• Contest Management System Ferramenta de código aberto em Python para executar e gerenciar um concurso de programação em um servidor IOI 2012 e IOI 2013 .