kactl

KACTL

Ce référentiel héberge KACTL, le document de référence de l'équipe ICPC de KTH. Il se compose de 25 pages de code C++ copier-coller, à utiliser dans les concours de programmation de style ICPC.

Voir kactl.pdf pour la version finale consultable et content/ pour le code source brut.

Aspirations

Les algorithmes KACTL doivent être : utiles, courts, suffisamment rapides, bien testés et, si pertinent, lisibles et faciles à modifier. Ils ne doivent pas être trop génériques, car le code est saisi manuellement, ce qui ne fait qu'ajouter une surcharge. En raison de problèmes d'espace, nous excluons également les algorithmes très courants/simples (par exemple, Dijkstra) ou très rares (correspondance pondérée générale).

Si vous pensez que quelque chose manque, pourrait être nettoyé ou si vous remarquez un bug, veuillez signaler un problème ou envoyer une pull request !

Personnalisation de KACTL

Bien que KACTL soit utilisable tel quel, il est également facile à modifier si vous souhaitez créer une copie personnalisée. En particulier, vous souhaiterez peut-être modifier la page de garde ou faire votre propre choix d'algorithmes à inclure. En raison de problèmes d'espace, tous les algorithmes du dépôt ne sont pas inclus dans le pdf. Vous souhaiterez peut-être également activer la coloration syntaxique colorée.

content/kactl.tex est le fichier principal de KACTL et peut être modifié pour changer le nom de l'équipe, le logo, la coloration syntaxique, etc. Il importe les fichiers chapter.tex de chacun des sous-répertoires content/ , qui définissent le contenu de chaque chapitre. Ceux-ci incluent le code source, le texte et les mathématiques sous forme de LaTeX. Pour ajouter/supprimer du code d'un chapitre, ajoutez/supprimez une ligne kactlimport correspondante du fichier chapter.tex . Pour un meilleur alignement, vous souhaiterez peut-être insérer des commandes hardcolumnbreak , columnbreak ou newpage , bien que cela ne soit généralement fait qu'avant les concours importants, et non sur la branche principale. Les algorithmes qui ne sont pas inclus dans le pdf sont commentés dans chapter.tex .

Pour construire KACTL, tapez make kactl (ou make fast ) sur une machine *nix -- cela mettra à jour kactl.pdf . (Windows peut également fonctionner, mais n'a pas été testé.) doc/README contient quelques notes supplémentaires à ce sujet.

Conseils:

1. Découvrez ce qui est exclu par défaut en exécutant make showexcluded . La configuration par défaut est choisie pour constituer un équilibre raisonnable pour les équipes débutants et avancées.
2. Profitez du hachage lors de la saisie de ces algorithmes. Chaque algorithme possède un hachage MD5 de 6 caractères en haut à droite. Ce hachage peut être généré à l'aide de hash.sh ou de la commande :Hash du .vimrc . Le hachage ignore les espaces et les commentaires.

Style de codage

KACTL utilise un style de codage relativement concis, avec une poignée de macros/typedefs définis dans le modèle qui permettent de raccourcir le code. La largeur de ligne est de 63 caractères, avec des tabulations pour l'indentation (tabulation = 2 espaces dans le pdf).

Chaque algorithme contient un en-tête avec l'auteur du code, la date à laquelle il a été ajouté, une description de l'algorithme, son statut de test, et de préférence également la source, la licence et la complexité temporelle.

kactl.pdf doit être limité à 25 pages + page de couverture. Parfois, le kactl.pdf généré est validé dans le dépôt pour plus de commodité, mais pas trop souvent car cela ralentit les opérations git.

Essai

KACTL vise un niveau élevé de confiance dans l’exactitude des algorithmes. Les tests sont effectués à la fois sur des juges en ligne et (pour les algorithmes plus récents) avec des tests de résistance qui comparent les résultats à un algorithme plus naïf pour un grand nombre de cas générés aléatoirement. Ces tests se trouvent dans le répertoire stress-tests et sont exécutés avec CI à chaque validation. Le CI vérifie également que tous les en-têtes sont compilés (à l'exception d'une liste d'exclusion dans docs/scripts/skip_headers ) et que le latex est compilé.

old-unit-tests contient quelques tests unitaires défectueux, touchés pour la dernière fois il y a environ dix ans.

Licence

Comme d'habitude pour les programmes compétitifs, la situation des licences est un peu floue. De nombreux fichiers sources sont marqués d'une licence (nous essayons d'utiliser CC0), mais beaucoup ne le sont pas non plus. Il faut cependant supposer que la bonne volonté des autres auteurs est bonne et, dans de nombreux cas, une autorisation ne devrait pas être nécessaire puisque le code n'est pas distribué. Pour aider à retracer les choses, les sources et les auteurs sont notés dans les fichiers sources.

Tout dans stress-tests est implicitement CC0, à l'exception des implémentations de référence prises sur Internet.