kactl
1.0.0
Este repositorio aloja KACTL, el documento de referencia del equipo ICPC de KTH. Consta de 25 páginas de código C++ que se puede copiar y pegar, para usar en competencias de programación estilo ICPC.
Consulte kactl.pdf para ver la versión final navegable y content/ para ver el código fuente sin formato.
Los algoritmos KACTL deben ser: útiles, breves, lo suficientemente rápidos, bien probados y, si son relevantes, legibles y fáciles de modificar. No deberían ser demasiado genéricos, ya que el código se escribe manualmente y eso sólo añade gastos generales. Debido a problemas de espacio, también excluimos algoritmos que son muy comunes/simples (p. ej., Dijkstra) o muy poco comunes (coincidencia ponderada general).
Si cree que falta algo, que se puede limpiar o nota un error, presente un problema o envíe una solicitud de extracción.
Si bien KACTL se puede utilizar tal cual, también es fácil de modificar si desea crear una copia personalizada. En particular, es posible que desee cambiar la portada o elegir los algoritmos que desea incluir; debido a cuestiones de espacio, no todos los algoritmos del repositorio están incluidos en el pdf. Es posible que también desee habilitar el resaltado de sintaxis en color.
content/kactl.tex es el archivo principal de KACTL y se puede editar para cambiar el nombre del equipo, el logotipo, el resaltado de sintaxis, etc. Importa archivos chapter.tex de cada uno de los subdirectorios content/ , que definen el contenido de cada capítulo. Estos incluyen código fuente, texto y matemáticas en forma de LaTeX. Para agregar o eliminar código de un capítulo, agregue o elimine la línea kactlimport correspondiente del archivo chapter.tex . Para una mejor alineación es posible que desees insertar comandos hardcolumnbreak , columnbreak o newpage , aunque esto normalmente sólo se hace antes de concursos importantes y no en la rama principal. Los algoritmos que no están incluidos en el pdf se dejan comentados en chapter.tex .
Para compilar KACTL, escriba make kactl (o make fast ) en una máquina *nix; esto actualizará kactl.pdf . (Windows podría funcionar también, pero no está probado). doc/README tiene algunas notas más sobre esto.
Consejos:
make showexcluded . La configuración predeterminada se elige para que sea un equilibrio razonable para equipos principiantes y avanzados.hash.sh o el comando :Hash del .vimrc . El hash ignora los espacios en blanco y los comentarios. KACTL utiliza un estilo de codificación relativamente conciso, con un puñado de macros/typedefs definidos en la plantilla que ayudan a acortar el código. El ancho de línea es de 63 caracteres, con pestañas para sangría (tabulación = 2 espacios en el pdf).
Cada algoritmo contiene un encabezado con el autor del código, la fecha en que se agregó, una descripción del algoritmo, su estado de prueba y, preferiblemente, también la fuente, la licencia y la complejidad temporal.
kactl.pdf debe mantenerse en 25 páginas + portada. Ocasionalmente, el kactl.pdf generado se envía al repositorio por conveniencia, pero no con demasiada frecuencia porque hace que las operaciones de git sean más lentas.
KACTL apunta a un alto nivel de confianza en la corrección del algoritmo. Las pruebas se realizan tanto con jueces en línea como (para algoritmos más nuevos) con pruebas de estrés que comparan el resultado con un algoritmo más ingenuo para una gran cantidad de casos generados aleatoriamente. Estas pruebas se encuentran en el directorio stress-tests y se ejecutan con CI en cada confirmación. El CI también verifica que todos los encabezados se compilan (excepto una lista de exclusión en docs/scripts/skip_headers ) y que el látex se compila.
old-unit-tests contiene un par de pruebas unitarias rotas, que se tocaron por última vez hace unos diez años.
Como es habitual en la programación competitiva, la situación de las licencias es un poco confusa. Muchos archivos fuente están marcados con licencia (intentamos utilizar CC0), pero muchos tampoco. Sin embargo, es de suponer que se debe asumir la buena voluntad de otros autores y, en muchos casos, no debería ser necesario el permiso ya que el código no se distribuye. Para ayudar a rastrear los datos, las fuentes y los autores se anotan en los archivos fuente.
Todo en stress-tests es implícitamente CC0, excepto las implementaciones de referencia tomadas de Internet.
