This document describes the different parts needed to create a problem.
We differentiate between three kinds of solutions: correct ones, wrong ones and too slow ones. We usually refer to them by their judge verdicts: AC, WA and TLE.
Solutions are written as C++ or Python files in the executables directory of a problem.
Their filename should always start with solution.
To mark WA and TLE solutions, use an additional suffix .wa or .tle before the file extension (for example: solution-slow.tle.cpp)
Any solution without one of these suffixes is considered an AC solution.
A problem must always include a primary solution named solution.{cpp|py}.
This solution is used to generate the expected solutions for testcases.
In general, you should write solutions of all three types to best test your problem. All solutions are also included in the package uploaded to the judge, and their expected verdict is verified.
Every problem includes a generator in the executables named generator.{cpp|py}.
When run, a generator should generate the testcases as .in files in the current directory.
Every testcase should be accompanied by an according .desc file, containing a short, one-line description of the testcase to be shown in the judge interface.
The testcases are always generated in the build/testcases directory, should you wish to inspect them.
For reproducability, make sure that your generator always produces the same result when run multiple times. To this end, the included templates already set up the random number generators with fixed seeds.
When using C++, you should use the random genrator from testlib.h instead of the one in the standard library for ease of use.
Search through the testlib.h header symlinked in the executables directory to find all the available methods.
Note that next(a) generates an integer in the range [0,a) (right-exclusive), but next(a, b) in the range [a, b] (right-inclusive).
You might also want to check out testlibs utility functions such as println to make your life easier.
The problem statement is created from the problem.tex LaTeX file in the problem directory.
It is generated from a template specific to the course the problem was generated for.
You can build this file as-is, however some features won't work correctly, such as the inclusion of samples as well as the problem name and timelimit.
When generating the pdf with make pdf or another make command, it gets build in the build/problem directory.
This should usually not change anything for you, however, if you include files such as images, your relative paths won't work as expected.
To fix this, always use the \problemDir latex command to refer to the problem directory when including files.
Use an answer generator if the .ans files should not correspond to the output of the solution.
This is usually the case when using in interactor, where the interactor writes the output file instead of the solution, or a validator, where the .ans file can be anything that helps the validator assess the solutions output.
Answer generators reside in the executables directory and are named answer-generator.{cpp|py}.
They work just like solutions in that they should read the .in file through stdin and write to stdout.
Use a validator if you want to accept more than a single, unique solution. The default validator already ignores extraneous whitespace and even supports matching floats with a given accuracy, so it should be sufficient for most cases.
Validators can currently only be written in C++, and are placed as validator.cpp in the executables directory.
As with generators, we use testlib.h for many convenience features.
In a validator, you can read the input file (from inf), the answer file generated by the primary solution (from ans) and the submission output (from ouf).
You can then assign a verdict using the family of quit* functions.
It is important to always finish the program using one of these, as returning from main normally would be registered as a validator crash!
While testlib.h supports many verdicts, we use only four of those:
_okaccepts the submission output_wamarks it as a wrong answers_peindicates a malformed submission output. You should rarely have to use this manually, since the read methods ofoufalready quit with this verdict if they cannot parse the output._failindicates an error in the validators logic. Use this as a defensive measure in seemingly impossible cases, such as when a valid solution has a better result than the expected one. When a validator quits with this verdict or otherwise crashes, the problem gets disabled giving you a chance to investigate what happened.
To keep your code concise, remember that you can use quitf(verdict, format_string, ...) and quitif(condition, verdict, format_string, ...) with printf-style formatting instead of the plain quit.
Use an interactor in an interactive problem, i.e. one where the solution can send queries that are then answered by the interactor.
The implementation of interactors is complex enough to warrant its own document: interactors.md.
This contains metadata for the problem that will be shown in the problem list.
You generally don't need to care about the format of this file since setup-problem.py prompts you for everything needed, but it is documented here for completeness.
The overall format is:
{
"difficulty": 3,
"tags": [...],
"based_on": {
"type": "...",
"data": [...]
}
}Difficulty can be a value between 1 and 5, standing for trivial, easy, medium, hard, and very hard.
Tags is a list of tag strings.
The available tags are based on the ones used by codeforces (setup-problem.py contains a complete list).
The based_on key is optional, but if it is present, its type subkey must be one of three values: "codeforces", "old-problem", or "other".
If it is "codeforces", data must contain two strings: the id of the codeforces contest and problem, for example ["1234", "B1"].
If it is "old-problem", data must contain a triple of the old problems course, contest, and problem name, in that order.
Lastly, if it is "other", data contains a single string message.