Informações aos Calouros

Para informações gerais, olhe a página de boas vindas: Bem-vindo!

Editores de texto:

Para a maratona, os favoritos são

Vim e gEdit estão instalados no fedora da puc.
Mas você pode usar o editor de sua preferência.

Comandos básicos de terminal:

  • mkdir dir: cria o diretório dir
  • ls: mostra os arquivos e diretórios na pasta corrente
  • cd odir: muda o diretório corrente para odir (odir deve ser um subdiretório do diretório corrente)
  • diff a1 a2: retorna as diferenças entre os arquivos a1 e a2
  • cat a1: mostra o conteúdo do arquivo a1
  • clear: limpa a tela
  • rm a1: remove a1
  • Ctrl+C mata o processo
  • Ctrl+D simula End-of-File
  • Ctrl+L limpa a tela (clear)

Compilação:

Se você estiver usando C++, a compilação é feita com g++ nomeDoArquivo.cpp, mas compilando assim ele não exibe nenhum warning a mais e cria um executável de nome a.out. Para mudar isso, existem as seguintes opções de compilação:

As opções podem ter qualqer ordem, ou seja, g++ nome.cpp -g -Wall -Wshadow -o out e g++ -o out -Wshadow -g -Wall nome.cpp funcionam ambos

Se você estiver usando C, as regras se aplicam usando o compilador gcc.
Se quiser forçar o padrão ANSI, use a flag -ansi.

Rodando o programa com uma entrada

Você PODE (e deve) gerar um output por caso de teste, não precisa imprimir tudo só no final. Geralmente é útil fazer redirecionamento de entrada (e algumas vezes, de saída):

  • ./out < entrada (onde "entrada" é um arquivo com a entrada do seu programa): roda o programa usando "entrada" como stdin
  • ./out > saida: cria um arquivo com a saída do seu programa

Esses dois comandos podem ser combinados at will, por exemplo:

./out < entrada > saida

roda out usando "entrada" como stdin e redireciona a saída para "saida"

Esquema da competição (ACM-ICPC, somente – outras competições tem outros esquemas)

A prova é feita em trio, com apenas uma máquina para cada time, e tem duração de 300 minutos (pode parecer muito, mas na hora, fica pouco, acreditem). Cada time recebe três cópias da prova, que varia de 7 a 12 problemas, e deve escrever um código para resolver cada problema, submetendo o código para a máquina do juiz. A submissão é então julgada numa bateria grande de testes e pode ter as seguintes respostas:

  • AC (Sim, aceito ou accepted): seu programa passou em todos os testes! Ae! Nesse caso, você vai ter um balão afixado na sua máquina da cor do problema resolvido.
  • WA (Resposta errada ou wrong answer): seu programa falhou em algum dos testes (sim, basta um, mas pode ter falhado em mais). Você não ganha nada aqui, então faça mais casos, leia de novo o código até você conseguir fazê-lo passar. Nota importante: você não recebe qual caso seu programa falhou!
  • TLE (tempo limite excedido ou Time limit (exceeded)): seu programa esgotou o tempo que ele tinha para rodar – lembre-se que isso não garante que, dado que você otimize, ele vai estar certo; a execução é interrompida antes do judge comparar as respostas. Nesse caso, a primeira providência é olhar limites de loops (seu programa pode ter caído num loop infinito). Se estiver tudo aparentemente certo, é provável que seu código precise de otimizações ou até uma reconstrução completa do algoritmo (porque a complexidade é muito maior do que deveria)
  • RE (runtime (error)): no meio dos testes, seu programa deu erro, muito provavelmente acesso de memória inválida, mas pode ser qualquer tipo de erro – cheque limites e tamanhos de arrays; verifique casos base de recursão (lembre-se que estouro de pilha existe!)
  • CE (compile/compilation error): é, seu programa nem compilou – você mandou o código certo? Se você usa Mac, como eu, cheque os includes padrão de C(++). Muitas vezes as coisas compilam no Mac MESMO que você não tenha incluído a biblioteca certa; Linux é mais rigoroso com isso.
  • PE (presentation error): sua resposta está certa a menos de espaços em branco; verifique se os finais de linha estão com esses espaços. Muitas vezes não é aplicável.
  • Filename mismatch (mais para Java): você não nomeou seu arquivo de acordo com a especificação – lembre-se que, em Java, ele chama o nome da classe onde fica a main (me corrijam se eu estiver errado); algumas vezes eles estendem a restrição para todas as outras linguagens.
  • MLE (memory limit exceeded): você usou mais memória na alocação estática que deveria (lembre-se que, para memória de pilha, o erro vai ser RE).

Com todos esses erros possíveis, é necessário checar se todos se aplicam. Para isso, existe uma fase da competição antes da prova oficial chamada "Warm-up", que tipicamente tem 60 minutos e o scoreboard não importa. Usem essa fase para verificar o layout de teclado da preferência de vocês, para ver qual o limite de memória, verificar a existência de PE e filename mismatch. Tudo isso pode ser crítico na hora da prova, já que uma submissão errada (não-AC) custa igual para todos os erros possíveis.

Sobre o placar:
Como todos somos programadores (se não, não faço ideia porque vocês estão lendo isso…), posso fazer um código de como é ordenado o placar, então vamos introduzir um struct time:

struct time {
   int nProbAC;
   int penalidade;

   time() : nProbAC(0), penalidade(0) {}
};

Não sei quanto vocês estão familiarizados com C++, mas a linha time() … significa que toda vez que um objeto time é criado, nProbAC e penalidade são inicializados com 0 – para mais info nessa parte de OO, olhem constructors e initialization lists; pra galera C que está estranhando a falta de typedef e a existência de um constructor, saibam que, no C++, struct funciona igual a uma classe, só que os membros são public por default, onde na classe, eles são privados

Quando o time A acerta um problema - ou seja, recebe AC na tentativa n, no minuto de prova m:

A.nProbAC++;
A.penalidade+=m+(n-1)*penDefault;

Onde penDefault é tipicamente 20, mas achei melhor colocar em variáveis se a regra mudar por algum motivo. Notem que a penalidade NÃO aumenta se você errar uma questão um milhão de vezes e não conseguir o AC. De qualquer forma, conforme vocês verão abaixo, sempre é bom tentar passar um problema, afinal o critério-mor de comparação é o numero de problemas, conforme mostra a função de comparação usada na ordenação do scoreboard:

bool cmp(time A, time B) {
   if (A.nProbAC!=B.nProbAC)
      return A.nProbAC>B.nProbAC;

   return A.penalidade<B.penalidade;
}

Então sempre vale a pena passar um problema – claro que esse critério também incentiva que vocês façam isso de forma mais precisa o possível, já que a penalidade É um critério para a ordenação dos times; então, passar problemas em poucas tentativas e rápido (com pouco tempo de prova) é uma coisa que melhora a penalidade, e logo, a colocação de vocês, durante a prova.

A partir daí, acho que é sensato fazer uma observação: se vocês tomarem 10 minutos antes de submeter o código para verificá-lo por alto e criar um ou dois casos de teste novos, isso é uma coisa muitas vezes positiva. Por mais que, se o código não estiver errado, vocês tenham tomado 10 minutos, se ele estiver, vocês vão perder 20 de penalidade de cara e ainda vão gastar mais tempo pra debugar; como o critério de AC é muito rigoroso, todo cuidado é pouco nesse sentido.

Fases da prova:

  • De "faltam 300" até "faltam 61": o placar é atualizado continuamente e os times ganham balão por cada problema submetido corretamente.
  • De "faltam 60" até "faltam 16" (conhecido como Frozen): o placar geral é congelado, ou seja, ele fica exatamente igual pelo resto da prova, mesmo que os times tenham acertado novos problemas. O único indicativo de que outros times acertaram são os balões que continuam vindo. Para o próprio time, o sistema também dá a resposta das suas submissões.
  • De "faltam 15" até o final da prova (conhecido como Blind): o placar continua congelado, mas agora os balões param de vir e você para de saber os resultados das suas próprias submissões – continuem tentando as questões, pessoal, muitas vezes falta um detalhezinho que você esqueceu; mude tudo que você acha que possa estar errado. Lembre-se que passar uma questão no blind pode mudar tudo (como bem sabe o time Challenge Accepted, da UFPE, que foi campeão brasileiro por ter passado uma questão no Blind após 15 tentativas; e menos maneiro, mas maneiro, o meu time na regional de 2012, que foi campeão de sede por uma questão também passada no Blind). Além disso, passar uma questão no blind tem seu gosto especial (como sabe o time The Garbage Collectors, da PUC-Rio, que ficou em 5º na regional do ano passado)

Dicas de prova
Toda questão tem um enunciado, que é uma historinha especificando o problema; um seção de 'Input', que detalha todas as restrições do input; uma seção de output, que faz o mesmo para o output e um sample, que são alguns casos de teste que, na grande maioria das vezes não cobrem todos os casos.
DICA 1: se algo não está especificado, muitas vezes NÃO é verdade – se não está escrito "inteiro", e sim, "número", é provável que tenha um caso de teste com doubles (a não ser que algo na definição da questão te dê certeza que não, como por exemplo, esse número ser primo). Se está escrito que você recebe um grafo e nada mais além disso, ele NÃO necessariamente vai ser conexo, direcionado ou até mesmo simples (grafo simples == grafo que tem, no máximo, uma aresta entre quaisquer vértices u,v)! Então leia o enunciado com calma e atenção, aí leia de novo; tenha certeza que você pegou todas as restrições de lá e não apenas deduziu. Uma coisa que pode ajudar nessas horas é pedir pro seu colega ler a questão sem falar nada pra ele; se a interpretação de ambos bater, existe uma probabilidade maior que ela esteja certa.

DICA 2: muitas vezes o sample é SUPER vagabundo, só cobre casos bases, por exemplo. Nesse caso, faça alguns testes na mão! Sério, testes curtos ou que possam ser automaticamente gerados. Testes super comuns das pessoas errarem: teste mínimo – muitas vezes você sabe que n>0, mas o seu código acessa v[i] e v[i-1] - ops, você esta assumindo que n>1, isso não é verdade – testar sempre o caso mínimo é a boa.
Teste o caso máximo – se você ganha um vetor de presente que tem até n posições que podem ter números <= m, use o copy/paste do seu editor (acho emacs e vim mais convenientes pra isso, já que eles têm um 'cole 20.000.000 de vezes', mas talvez isso seja minha ignorância com outros editores) para gerar o giga vetor {m, m, m, …, m} – esse teste vai te ajudar a ver problemas de overflow (como ajudou a minha equipe em 2012) e tamanho de array, então é super importante.

DICA 3: tempo de máquina na prova é valioso, então use as funções de impressão do sistema de contest para fazer debugs menos profundos e tentar achar casos de teste onde o código não funciona

DICA 4: tempo de máquina na prova é valioso (2), então se você já tem uma ideia para a solução, acostume-se a fechar todos os detalhes de implementação na folha de papel. Muitas vezes competidores não o fazem, o que acaba atrasando uma outra solução, ou um debug importante (porque você tem que dar aquela parada pra pensar). Geralmente detesto esse 'o que cara fodão X faz pra ser fodão', mas acho que o processo do Tomek é bem válido, então leiam o artigo: http://community.topcoder.com/tc?module=Static&d1=features&d2=091405
Outro resource mais focado, mas bacana, é ler a parte de estratégia da lib do LinkEdiSamba.

DICA 5: Se vocês tiverem que digitar os inputs, PEÇAM PRO COLEGA CONFERIR – to falando sério, conheço times que perderam milênios de bobeira porque o time errou o input na hora de digitar e, quando voce está debugando, a última coisa que ocorre é que a entrada está errada. Aliás, essa dica pode ser generalizada para: TESTEM AS COISAS RÁPIDAS E IDIOTAS ANTES (sério, vocês vão me agradecer depois).

Onde treinar (Online Judges e competições)

Abaixo estão online judges mais focados para competições periódicas ou que têm um esquema todo especial:

Abaixo estão competições que só acontecem uma ou duas vezes ao ano:

Outras ferramentas

  • http://cerberus.delos.com:790/usacogate (USACO Training Gateway – um pseudo curso de programação, com teoria, exemplos e problemas; muito, muito legal, começa do começo)
  • http://ahmed-aly.com (VOC - aqui você pode usar problemas de MUITOS OJs para criar suas próprias competições, seguindo as mesmas regras do ICPC; além disso, foram introduzidas ferramentas no mesmo estilo do checklist do Pedro Gold – RIP –, onde o que importa é se você resolveu aquele problema alguma hora da sua vida ou não)
  • http://uhunt.felix-halim.net (uHunt – ferramenta que mostra suas estatísticas no UVa, quais problemas são estatísticamente mais fáceis de se resolver, além de ter uma integração com o excelente livro dos irmãos Halim, o Increasing the Lower Bounds, onde os problemas são divididos em tópicos e explicados de um ponto de vista prático, mais focado na maratona mesmo)

Bibliografia sugerida

Livros majoritariamente teóricos sobre algoritmos:

Livros voltados para a Maratona:

Livros sobre engenharia de software:

Livros sobre linguagens:

Website sobre C++:

Wesites de referência de bibliotecas:

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License