kactl
1.0.0
Este repositório hospeda KACTL, documento de referência da equipe ICPC do KTH. Consiste em 25 páginas de código C++ que pode ser copiado e colado, para uso em competições de programação no estilo ICPC.
Consulte kactl.pdf para a versão final navegável e content/ para o código-fonte bruto.
Os algoritmos KACTL devem ser: úteis, curtos, rápidos o suficiente, bem testados e, se relevantes, legíveis e fáceis de modificar. Eles não devem ser excessivamente genéricos, pois o código é digitado manualmente e isso apenas adiciona sobrecarga. Devido a questões de espaço, também excluímos algoritmos que são muito comuns/simples (por exemplo, Dijkstra) ou muito incomuns (correspondência ponderada geral).
Se você sentir que algo está faltando, pode ser limpo ou notar um bug, registre um problema ou envie uma solicitação pull!
Embora o KACTL possa ser usado como está, também é fácil de modificar se você quiser criar uma cópia personalizada. Em particular, você pode querer alterar a página de rosto ou fazer sua própria escolha de algoritmos a serem incluídos - devido a questões de espaço, nem todos os algoritmos do repositório estão incluídos no pdf. Você também pode ativar o realce de sintaxe colorido.
content/kactl.tex é o arquivo principal do KACTL e pode ser editado para alterar o nome da equipe, logotipo, destaque de sintaxe, etc. Ele importa arquivos chapter.tex de cada um dos subdiretórios content/ , que definem o conteúdo de cada capítulo. Isso inclui código-fonte, texto e matemática na forma de LaTeX. Para adicionar/remover código de um capítulo, adicione/remova uma linha kactlimport correspondente do arquivo chapter.tex . Para um alinhamento melhor, você pode querer inserir os comandos hardcolumnbreak , columnbreak ou newpage , embora isso geralmente seja feito apenas antes de concursos importantes, e não no branch principal. Os algoritmos que não estão incluídos no pdf são deixados comentados em chapter.tex .
Para construir o KACTL, digite make kactl (ou make fast ) em uma máquina *nix - isso atualizará kactl.pdf . (O Windows também pode funcionar, mas não foi testado.) doc/README tem mais algumas notas sobre isso.
Pontas:
make showexcluded . A configuração padrão é escolhida para ser um equilíbrio razoável para equipes iniciantes e avançadas.hash.sh ou o comando :Hash do .vimrc . O hash ignora espaços em branco e comentários. KACTL usa um estilo de codificação relativamente conciso, com um punhado de macros/typedefs definidos no modelo que ajudam a encurtar o código. A largura da linha é de 63 caracteres, com tabulações para recuo (tabulação = 2 espaços no pdf).
Cada algoritmo contém um cabeçalho com o autor do código, a data em que foi adicionado, uma descrição do algoritmo, seu status de teste e, preferencialmente, também fonte, licença e complexidade de tempo.
kactl.pdf deve ter 25 páginas + página de rosto. Ocasionalmente, o kactl.pdf gerado é enviado ao repositório por conveniência, mas não com muita frequência porque torna as operações do git mais lentas.
KACTL visa um alto nível de confiança na correção do algoritmo. O teste é feito tanto em juízes on-line quanto (para algoritmos mais recentes) com testes de estresse que comparam a saída a um algoritmo mais ingênuo para uma grande quantidade de casos gerados aleatoriamente. Esses testes ficam no diretório stress-tests e são executados com CI em cada commit. O CI também verifica se todos os cabeçalhos são compilados (exceto uma lista de exclusões em docs/scripts/skip_headers ) e se o látex é compilado.
old-unit-tests contém alguns testes de unidade quebrados, tocados pela última vez há cerca de dez anos.
Como é habitual na programação competitiva, a situação do licenciamento não é clara. Muitos arquivos de origem estão marcados com licença (tentamos usar CC0), mas muitos também não estão. Presumivelmente, a boa vontade deve ser assumida por outros autores e, em muitos casos, a permissão não deve ser necessária, uma vez que o código não é distribuído. Para ajudar a rastrear as coisas, as fontes e os autores são anotados nos arquivos de origem.
Tudo nos stress-tests é implicitamente CC0, exceto implementações de referência retiradas da Internet.
