Introduction_to_the_Kattis_Problem_Format.mw

= Quick Introduction to the Kattis Problem Format =

This document is a quick introduction to writing problems for the Kattis
Problem Format and using Kattis Problem Tools.  For more thorough documentation
about the Kattis Problem Format, please refer to [Problem_Format]. For more
information about the Kattis Problem Tools, please refer to
https://github.com/Kattis/problemtools

== Example Problems ==

To start with, it probably helps to see some examples. Here's a set of problems
that are written in the format:
http://ncpc.idi.ntnu.no/ncpc2015/ncpc2015all.tar.bz2 (Warning: 22+ MB download.)
These were the ones used for NCPC 2015. You can see how they appear on Kattis in
HTML here: https://ncpc15.kattis.com/problems

== Kattis Problem Tools ==

Here is the source to the Kattis problemtools:
https://github.com/Kattis/problemtools You can install these on Ubuntu (see the
README on that page). The three key programs you need from this are
<tt>verifyproblem</tt>, <tt>problem2pdf</tt>, and <tt>problem2html</tt>. 

=== verifyproblem ===

Verifyproblem will do something like the following:

* check that the problem statement can be compiled (from LaTeX)
* check that there's at least one input format validator and one accepted submission
* run input format validators on all inputs
* run all submissions (accepted and otherwise) on the inputs and check that the results match the expectation
* run any output validators if they exist on output produced by the submissions
* compute time limits based on a time multiplier times the slowest accepted submission

== Kattis Problem Format ==

Here's extensive documentation on the problem format: [Problem_Format] Note that
some sections are deprecated and some are not yet implemented (but are marked as
such).

=== Typical Problem Format Layout ===

The problem format is a directory with a top-level file <tt>problem.yaml</tt> and a
number of subdirectories (and sub-subdirectories). Here are some of the common
things that are expected:

==== Test Data ====

* <tt>data/sample/{a.in, a.ans}</tt> -- required; sample input file, corresponding answer file -- these are automatically placed into the problem statement

* <tt>data/secret/{a.in, a.ans}</tt> -- required; secret corresponding input / answer files 
  
NB: Kattis runs all sample AND secret test cases with each submission, so no need to include an extra copy of the samples in the secret directory

NB: the order of tests is the file sort order of the file names (all samples before all secrets)

==== Validators ====

* <tt>input_format_validators/</tt> -- required; contain program(s) which must accept each input file NB: the definition of an input validator accepting is exiting with exit code 42

* <tt>output_validators/</tt> -- typically not used; here you can put program(s) which evaluate the correctness of a program's output (if the default behavior of comparing with a static file is not sufficient)

==== Problem Statement ====

* <tt>problem_statement/problem.tex</tt> -- required; the LaTeX file describing the problem

==== Submissions (Correct **and** Incorrect) ====

* <tt>submissions/accepted/</tt> -- required; contain program(s) which give correct output
* <tt>submissions/time_limit_exceeded/</tt> -- contain program(s) which are intended to take too long
* <tt>submissions/wrong_answer/</tt> -- contain program(s) which are intended to finish in time but give incorrect output
* <tt>submissions/run_time_error/</tt> -- contain program(s) which are intended to result in a run-time error during execution (e.g. crash)

==== <tt>problem.yaml</tt> ====

* <tt>problem.yaml</tt> -- required; metadata about the problem, such as authorship, license, judging flags, etc.

== Using the Problem Format on Kattis Judge ==

When judging on Kattis, Kattis's default output validator is lenient on
whitespace changing differences, but this can be made strict. Also,
floating-point outputs can be judged to be correct within some specified
tolerance (relative or absolute), which is really nice.