title | sort |
---|---|
Main page |
1 |
This site contains the specification for the (Kattis) Problem Package Format. It is available in two places:
- The latest version: https://www.kattis.com/problem-package-format.
- The version used in the current ICPC World Finals cycle: https://icpc.io/problem-package-format.
Development happens in the GitHub repository: https://github.com/Kattis/problem-package-format.
The ICPC uses a strict subset of the larger Kattis version of the spec.
Click ICPC
or Kattis
in the sidebar on the problem package format page to select the version.
TODO: Should we create a separate `overview` page instead? Or maybe just link to one of the examples?
The main page doesn't have the TOC in the sidebar, so I think it's best to keep this page concise.
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
To start with, it probably helps to see some examples. Here's a set of problems that are written in the format: https://nordic.icpc.io/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
TODO: We could create a separate page with a quick tooling overview for this.
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 verifyproblem
, problem2pdf
, and problem2html
.
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
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).
The problem format is a directory with a top-level file problem.yaml
and a number of subdirectories (and sub-subdirectories). Here are some
of the common things that are expected:
data/sample/{a.in, a.ans}
-- required; sample input file, corresponding answer file -- these are automatically placed into the problem statement
data/secret/{a.in, a.ans}
-- 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)
input_format_validators/
-- required; contain program(s) which must accept each input file NB: the definition of an input validator accepting is exiting with exit code 42
output_validators/
-- 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/problem.tex
-- required; the LaTeX file describing the problem
submissions/accepted/
-- required; contain program(s) which give correct outputsubmissions/time_limit_exceeded/
-- contain program(s) which are intended to take too longsubmissions/wrong_answer/
-- contain program(s) which are intended to finish in time but give incorrect outputsubmissions/run_time_error/
-- contain program(s) which are intended to result in a run-time error during execution (e.g. crash)
problem.yaml
-- required; metadata about the problem, such as authorship, license, judging flags, etc.
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.
Run this website locally using bundle exec jekyll serve
from the repository root.
bundle
is a Ruby package manager and can be installed with the ruby-bundler
package.
Run bundle install
from the repository root to install the gems needed to build the website.