Difference between revisions of "Problem Format (ITC 2015 Working Draft)"

Latest revision as of 17:58, 15 February 2016

This is a working draft.

Overview

This document describes the format of a Kattis problem package, used for distributing and sharing problems for algorithmic programming contests as well as educational use.

General Requirements

The package consists of a single directory containing files as described below, or alternatively, a ZIP compressed archive of the same files using the file extension .kpp . The name of the directory or the base name of the archive must consisting solely of lower case letters a-z and digits 0-9.

All file names for files included in the package must match the following regexp

[a-zA-Z0-9][a-zA-Z0-9_.-]*[a-zA-Z0-9]

I.e., it must be of length at least 2, consist solely of lower or upper case letters a-z, A-Z, digits 0-9, period, dash or underscore, but must not begin or end with period, dash or underscore.

All text files for a problem must be UTF-8 encoded and not have a byte order mark.

All floating point numbers must be given as the external character sequences defined by IEEE 754-2008 and may use up to double precision.

Programs

There are a number of different kinds of programs that maybe provided in the problem package; submissions, input validators, output validators, graders and generators. All programs are always represented by a single file or directory. In other words, if a program consists of several files, these must be provided in a single directory. The name of the program, for the purpose of referring to it within the package is the base name of the file or the name of the directory. There can't be two programs of the same kind with the same name.

Validators and graders, but not submissions, in the form of a directory may include two POSIX-compliant scripts "build" and "run". Either both or none of these scripts must be included. If the scripts are present, then:

• the program will be compiled by executing the build script.
• the program will be run by executing the run script.

Programs without build and run scripts are built and run according to what language is used. Language is determined by looking at the file endings. If a single language from the table below can't be determined, building fails. In the case of Python 2 and 3 which share the same file ending, language will be determined by looking at the shebang line which must match the regular expressions in the table below.

For languages where there could be several entry points, the default entry point in the table below will be used.

Problem types

There are two types of problems: pass-fail problems and scoring problems. In pass-fail problems, submissions are basically judged as either accepted or rejected (though the "rejected" judgement is more fine-grained and divided into results such as "Wrong Answer", "Time Limit Exceeded", etc). In scoring problems, a submission that is accepted is additionally given a score, which is a numeric value (and the goal is to either maximize or minimize this value).

Problem Metadata

Metadata about the problem (e.g., source, license, limits) are provided in a UTF-8 encoded YAML file named problem.yaml placed in the root directory of the package.

The keys are defined as below. Keys are optional unless explicitly stated. Any unknown keys should be treated as an error.

license

Allowed values for license.

Values other than unknown or public domain requires rights_owner to have a value.

limits

A map with the following keys:

For most keys the system default will be used if nothing is specified. This can vary, but you SHOULD assume that it's reasonable. Only specify limits when the problem needs a specific limit, but do specify limits even if the "typical system default" is what is needed.

scoring

A map with the following keys:

libraries

A set from elements below. A library will be available for the languages listed.

Problem Statements

The problem statement of the problem is provided in the directory problem_statement/.

This directory must contain one file per language, for at least one language, named problem.<language>.<filetype>, that contains the problem text itself, including input and output specifications, but not sample input and output. Language must be given as the shortest ISO 639 code. If needed a hyphen and a ISO 3166-1 alpha-2 code may be appended to ISO 639 code. Optionally, the language code can be left out, the default is then English (en). Filetype can be either tex for LaTeX files, md for Markdown, or pdf for PDF.

Please note that many kinds of transformations on the problem statements, such as conversion to HTML or styling to fit in a single document containing many problems will not be possible for PDF problem statements, so using this format should be avoided if at all possible.

Auxiliary files needed by the problem statement files must all be in <short_name>/problem_statement/ , problem.<language>.<filetype> should reference auxiliary files as if the working directory is <short_name>/problem_statement/. Image file formats supported are .png, .jpg, .jpeg, and .pdf.

A LaTeX file may include the Problem name using the LaTeX command \problemname in case LaTeX formatting of the title is wanted. If it's not included the problem name specified in problem.yaml will be used.

The problem statements must only contain the actual problem statement, no sample data.

Attachments

Public, i.e. non-secret, files to be made available in addition to the problem statement and sample test data are provided in the directory attachments/.

Test data

If input generators are used the files described here might not be available in this directory. This section describes what must be the case after running the generators.

The test data are provided in subdirectories of data/. The sample data in data/sample/ and the secret data in data/secret/.

All input and answer files have the filename extension .in and .ans respectively.

Annotations

Optionally a hint, a description and an illustration file may be provided.

The hint file is a text file with filename extension.hint giving a hint for solving an input file. The hint file is meant to be given as feedback, i.e. to somebody that fails to solve the problem.

The description file is a text file with filename extension .desc describing the purpose of an input file. The description file is meant to be privileged information that explains the purpose of the related test file, e.g. what cases it's supposed to test.

The Illustration is an image file with filename extension .png, .jpg, .jpeg, or .svg. The illustration is meant to be privileged information illustrating the related test file.

Input, answer, description, hint and image files are matched by the base name.

Test Data Groups

The test data for the problem can be organized into a tree-like structure. Each node of this tree is represented by a directory and referred to as a test data group. Each test data group may consist of zero or more test cases (i.e., input-answer files) and zero or more subgroups of test data (i.e., subdirectories).

At the top level, the test data is divided into exactly two groups: sample and secret, but these two groups may be further split into subgroups as desired.

The result of a test data group is computed by applying a grader to all of the sub-results (test cases and subgroups) in the group. See Graders for more details.

Test files and groups will be used in lexicographical order on file base name. If a specific order is desired a numbered prefix such as 00, 01, 02, 03, and so on, can be used.

In each test data group, a file testdata.yaml may be placed to specify how the result of the test data group should be computed. If such a file is not provided for a test data group then the settings for the parent group will be used. The format of testdata.yaml is as follows:

Included Code

Code that should be included with all submissions are provided in one directory per supported language, called include/<language>/.

The files should be copied from a language directory based on the language of the submission, to the submission files before compiling, overwriting files from the submission in the case of name collision. Language must be given as one of the language codes in the language table in the overview section. If any of the included files are supposed to be the main file (i.e. a driver), that file must have the language dependent name as given in the table referred above.

Example Submissions

Correct and incorrect solutions to the problem are provided in subdirectories of submissions/. The possible subdirectories are:

For submissions in the accepted subdirectory the expected score may be specified in a UTF-8 encoded YAML file named score.yaml. This is only relevant for scoring problems. The file must contain a map where the keys are the name of a submission and the value is the expected score for that submission. Not all submissions must be mentioned in the file, if a submission is not mentioned any score is accepted (but the submission may not be rejected).

For submissions in the rejected subdirectory the expected reason for rejection may be specified in a UTF-8 encoded YAML file named judgement.yaml. The file must contain a map where the keys are the name of a submission and the value is the reason for rejection for that submission. The reason for rejection must be one of WA or RTE. Not all submissions must be mentioned in the file, if a submission is not mentioned any rejection is accepted.

Every file or directory in these directories represents a separate solution. Same requirements as for submissions with regards to filenames. It is mandatory to provide at least one accepted solution.

Submissions must read input data from standard input, and write output to standard output.

Input Validators

Input Validators, for verifying the correctness of the input files, are provided in input_validators/. Input validators can be specified as VIVA-files (with file ending .viva), Checktestdata-file (with file ending .ctd), or as a program.

All input validators provided will be run on every input file. Validation fails if any validator fails.

Invocation

An input validator program must be an application (executable or interpreted) capable of being invoked with a command line call.

All input validators provided will be run on every test data file using the arguments specified for the test data group they are part of. Validation fails if any validator fails.

When invoked the input validator will get the input file on stdin.

The validator should be possible to use as follows on the command line: Needs to be clarified to fit Java and Python and similar

 ./validator [arguments] < inputfile

Output

The input validator may output debug information on stdout and stderr. This information may be displayed to the user upon invocation of the validator.

Exit codes

The input validator must exit with code 42 on successful validation. Any other exit code means that the input file could not be confirmed as valid.

Dependencies

The validator MUST NOT read any files outside those defined in the Invocation section. Its result MUST depend only on these files and the arguments.

Output Validators

Output Validators are used if the problem requires more complicated output validation than what is provided by the default diff variant described below. They are provided in output_validators/, and must adhere to the Output validator specification.

All output validators provided will be run on the output for every test data file using the arguments specified for the test data group they are part of. Validation fails if any validator fails.

Default Output Validator Specification

The default output validator is essentially a beefed-up diff. In its default mode, it tokenizes the files to compare and compares them token by token. It supports the following command-line arguments to control how tokens are compared.

When supplying both a relative and an absolute tolerance, the semantics are that a token is accepted if it is within either of the two tolerances. When a floating-point tolerance has been set, any valid formatting of floating point numbers is accepted for floating point tokens. So for instance if a token in the answer file says 0.0314, a token of 3.14000000e-2 in the output file would be accepted. If no floating point tolerance has been set, floating point tokens are treated just like any other token and has to match exactly.

Graders

Graders are programs that are given the sub-results of a test data group and aggregate a result for the group. They are provided in graders/ .

For pass-fail problems, this grader will typically just set the verdict to accepted if all sub-results in the group were accepted and otherwise select the "worst" error in the group (see below for definition of "worst"), though it is possible to write a custom grader which e.g. accepts if at least half the sub-results are accepted. For scoring problems, one common grader behaviour would be to always set the verdict to Accepted, with the score being the sum of scores of the items in the test group.

Invocation

A grader program must be an application (executable or interpreted) capable of being invoked with a command line call.

When invoked the grader will get the judgement for test files or groups on stdin and is expected to produce an aggregate result on stdout.

The grader should be possible to use as follows on the command line:

./grader [arguments] < judgeresults

Input

A grader simply takes a list of results on standard input, and produces a single result on standard output. The input file will have the one line per test file containing the result of judging the testfile, using the code from the table below, followed by whitespace, followed by the score. Format to be extended.

The score is taken from the score.txt files produced by the ouput validator. If no score.txt exists the score will be as defined by the grading accept_score and reject_score setting from problem.yaml.

Output

The grader must output the aggregate result on stdout in the same format as its input. Any other output, including no output, will result in a Judging Error.

For pass-fail problems, or for non-Accepted results on scoring problems, the score provided by the grader will always be ignored.

The grader may output debug information on stderr. This information may be displayed to the user upon invocation of the grader.

Default Grader Specification

The default grader has two different modes for aggregating the verdict -- no_errors and always_accept -- and four different modes for aggregating the score -- sum, avg, min, max. These modes can be set by providing their names as command line arguments (through the "grader_flags" option in testdata.yaml). If multiple conflicting modes are given, the last one is used. Their meaning are as follows.

Generators

Input generators are programs that generates input. They are provided in generators/.

Invocation

A generator program must be an application (executable or interpreted) capable of being invoked with a command line call.

The generators will be run with the test data directory (data/) as the working directory. The generator may read any existing files in that directory and should create any kind of test data file as defined in the test data section. The generator may not read or write anything outside the test data directory. The generators will be run in lexicographical order on name. If a specific order is desired a numbered prefix such as 00, 01, 02, 03, and so on, can be used.

The generators must be deterministic, i.e. always produce the same input file when give the same arguments.

The generators must be idempotent, i.e. running them multiple times should result in the same contents of the test data directory as running them once.

See also

• Output validator
• Problem format directory structure
• Problem Format Verification