Problem Package Format Specification

This site contains the specification for the (Kattis) Problem Package Format. It is available in two places:

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.

Overview

Note

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

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

Note

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

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 problem.yaml and a number of subdirectories (and sub-subdirectories). Here are some of the common things that are expected:

Test Data

  • 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)

Validators

  • 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_statement/problem.tex – required; the LaTeX file describing the problem

Submissions (Correct **and** Incorrect)

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

problem.yaml

  • problem.yaml – 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.

Development notes

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.