> For the complete documentation index, see [llms.txt](https://bulgarian-olympic-system-bos.gitbook.io/bos-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://bulgarian-olympic-system-bos.gitbook.io/bos-docs/fundamentals/tasks/task-types.md).

# Task types

The BOS system supports a variety of types. Tasks are usually distinguished by the content of the archives; adding the required files is enough in most cases. One of the things that is always present in tasks are input files for the tests and solutions get a *score* for each test that show the correctness - a decimal number between 0 and 1. Normally, solutions produce output for every input file, which is stored in a files - the contestant's output file. That output is checked against the author's output file with this command:

* `diff -Z -B -q <contestant's output files> <author's output file>` - it reports whether the files differ or are the same ignoring trailing spaces at the end of the lines and blank lines.

Keep in mind that the input and output files are sanitized by the system - `\r` and `\r\n` are replaced with `\n`.

Normally, the possible *scores* for the tests are only 0 and 1. In many cases, the check is more complicated than that or there are partial results (the default behaviour is to have only *scores* of 0 or 1 for each test). So, there is an option to use a program (the so-called *checker* program) by having a `checker` folder:

<details>

<summary><code>checker</code></summary>

checker.cpp

some other files needed for the compilation of the *checker*

</details>

The files in that folder are compiled together to create a binary file for the *checker*. It is important that in this case these, these files can indeed be compiled (don't forget to remove binary files, .o files, and such). If you have an already compiled *checker*, the content of the folder has to be only a binary file `checker`, a shell script `checker.sh`, a python script `checker.py` or `checker.jar`.  The *checker* program is expected to produce output that is only one decimal number between 0 and 1 - the solution's score for the test. All text in the standard error is considered a message for the test and is displayed to the contestants. If the *scores* can be partial, it is important to indicate this in the system by adding the `precision` property to the `grade.properties` file (see subsection 3 from [other properties](/bos-docs/fundamentals/tasks/task-properties.md#other-properties)).

We divide the tasks into three categories. The simplest, most standard and popular tasks are in the first category - **batch** tasks. Tasks that are non-standard and require the contestant to give an output file to a problem or many output files to the tests are in the second category - **output-only** tasks. The last category (**interactive** tasks) is the newest and requires the author to make additional programs for managing the execution process and/or for compiling the contestant's program.

## Batch

These are the classic tasks. The contestant's solution is a program that is compiled by itself to produce a binary file. Then the binary file is tested with the inputs that are stored in the input files and the corresponding outputs are compared to the author's outputs for the tests. No additional setting up is needed.

## Output-only

This type of tasks don't require the contestant to submit a classic program. Instead the contestant submits the outputs for the tests. There is no real compilation and usually there's a *checker* to validate the outputs and output the *scores* and messages for the tests. If there will be decimal results, than it is possible that the results are rounded and the `precision` property should be added to the `grade.properties` file (see subsection 3 from [other properties](/bos-docs/fundamentals/tasks/task-properties.md#other-properties)).&#x20;

### One file

In some cases, one file is submitted with instructions or a program in an esoteric programming language (usually a simple made-up language). That file has to be a .txt file, which has to be configured by adding `extensions=txt` to `grade.properties`. Here, a *checker* is needed to simulate the program on the tests. Another scenario is for a task where an approximate solution has to be found. Again, the contestant has to submit a .txt file to be evaluated by a *checker*. For everything to work fine, an input file still has to be added (it can be just empty file).

### Multiple files

This is similar to the last scenario, except that there are multiple tests. This can be achieved by adding `extensions=zip` to `grade.properties`, which enables submissions to be ZIP archives. The inputs of the tests can be written in the statement or added to the `contestant` folder (see [Tasks](/bos-docs/fundamentals/tasks.md)). It's important that the inputs' names have extension .in.  Each submission is a ZIP archive that should contain at least one output file. The names of the output files should be the same as the names of the input files, only differing in the extension - .out instead of .in.

## Interactive

This is the newest category of tasks and the most diverse. Usually, contestants must not read the whole input - they have to find it with some interaction, perform some action on it, or simulate multi-step interaction with hidden information between some steps. For this reason, contestants often have to only implement some functions and not the `main` function. The `main` function is written in a jury's program - the so-called *grader* program. That program is included by adding a `system` folder containing it:

<details>

<summary><code>system</code></summary>

`grader.cpp`

`<task>.h` - needed for compilation if there is only real interaction (the contestant's program calls functions from the jury's program)

some other files needed for the compilation

</details>

The important thing is that there is only one `grader.cpp` file in the task archive (the name of the folder is not important). Local graders for the contestants and other needed files can be included in the `contestant` folder (see [Tasks](/bos-docs/fundamentals/tasks.md)).

### Pseudo interactive

Header file is not needed if the task is *pseudo interactive*. This is used to restrict the solutions to be online. In addition, input and output are done by the jury's program which removes the contestant's ability to optimize that speed. Another case where the problem needs to be *pseudo interactive* is when the time for the input and output has to be removed from the total execution time to make differentiating solutions easier. Sometimes even tests can be generated during the execution of the *grader* and this time can also be removed.

This can be set up by measuring the time for removal in the *grader* (using C `clock` or C++ `chrono`) and writing this information in a special file. The information should be lines in the following format:

* `io-time: <time>`, where `<time>` is a decimal number that specifies the removed time in seconds

There could be several such lines (for example, after the input is read and after the output is written). The system only considers the last one, so you have to always output the total time for removal. Furthermore, it's important to output that information after every *grader* step that is measured to have actual information even if the program ends abruptly.

The measured *io-time* is subtracted from the total execution time and that time is displayed in the system as execution time. The time limit for the task is set according to the subtracted time, so there is another time limit property just for the subtracted time - `io_time` (see subsection 2 from [time limits](/bos-docs/fundamentals/tasks/task-properties.md#time-limits)). The real time limit that is passed to the sandbox for execution is the sum of the times in the properties `time` and `io_time`. Moreover, when `io_time` is set up, the `main` function of the *grader* program has a first argument which is the name of the file where the measured *io-time* has to be written (that is the special file mentioned earlier).

### Manager

The described format is not very secure because the *grader* program is compiled together with the code of the contestant, so the two programs share memory space. There is an option to add another program that manages the whole process and is compiled independently - a *manager* program. The contestant's program is compiled either by itself or together with the files in the `system` folder (if `grader.cpp` is present there). If there are no further properties, the *manager* program and the contestant's program are connected with 2 pipes for communication, which is apparent only in the *manager* program (for the contestant's program, the ends of the pipes are just standard input and standard output). The input of the *manager* program is from the input files of the tests, and the output is considered the contestant's output.

Although this method for interactive tasks is secure, the downside is the time spent for piping the information between the *manager* and the contestant's program. This is slower than the usual reading and writing. If that communication is done just a small number of times, then the overhead is insignificant, but it becomes very significant when it is done many times. For this communication, it is better to have a *grader* that communicates with the *manager*. That *grader* becomes more of a *stub* program - only providing better communication between the contestant's program and the *manager* program.

The *manager* program is added in the familiar way:

<details>

<summary><code>manager</code></summary>

`manager.cpp`

some other files needed for the compilation

</details>

Again, the important thing is the presence of `manager.cpp` file. There has to be only one such file in the task archive.

We have still not described how the *manager* program uses the pipes. Full specification of this is in the next section.

### Multiple-run

Sometimes, tasks require the contestant's program to be run several times or the contestant's program must have several independent functions (run in separate executions). This is achieved by having a *manager* program and adding the property `processes` with the appropriate value (see subsection 7 from [other properties](/bos-docs/fundamentals/tasks/task-properties.md#other-properties)). Now we can describe the full list of arguments that is passed to the `main` function of the *manager* program, if `processes=n`:

```
in_1 out_1 in_2 out_2 ... in_n out_n pid_1 pid_2 ... pid_n
```

The *manager* program is connected with *n* pairs of pipes to *n* instances of the contestant's program (which is the binary file created from the compilation of either the *grader* and contestant's solution, or the contestant's solution alone). The first 2*n* arguments are the file descriptors for the ends of those pipes and the last *n* arguments are the PIDs (process IDs) of the *n* instances. Those PIDs give the *manager* the ability to better 'control' the processes, for example, it can kill some of them.&#x20;

In more detail, `in_1` can be used to read data from the first instance of the contestant's program (which is the standard output for that program) and `out_1` can be used to write data to it. Let the `main` function in the *manager* be: `int main(int argc, char* argv[])`. You can use the following syntax to work with the file descriptors:

* C way - open the files through the descriptors

  ```cpp
  FILE *in1 = fdopen(atoi(argv[1]),"r"), *out1 = fdopen(atoi(argv[2]),"w");
  ```

  `argv[1]` is the corresponding argument for `in_1` and `argv[2]` is for `out_1`. The function `fdopen` is from `#include<fcntl.h>` and `atoi` is used to convert the string value to an integer value.
* C++ way - make streams through the descriptors (this does not impact the speed of the reading and writing through the pipes)

  ```cpp
  __gnu_cxx::stdio_filebuf buffer(atoi(argv[1]), std::ios::in);
  istream in1(&buffer);
  ```

  The class `__gnu_cxx::stdio_filebuf` is from the non-standard library `#include<ext/stdio_filebuf.h>`!

Now we can describe the whole picture. Everything is in one sandbox which first runs a 'parent' C++ built-in program `piper.cpp`. That program forks *n* instances of the contestant's program and for each makes 2 POSIX unnamed pipes for two-way communication that become standard input and output for the contestant's program.

In addition, for each of the instances, the following signal handler is used: `signal(SIGPIPE,SIG_IGN)`. It ensures that those instances won't die if some of the pipes are closed. For this reason, it's also good to add this in the beginning of the `main` function of the *manager*. This is from `#include <signal.h>` and won't compile in Windows!

Lastly, the *piper* program forks one instance of the *manager* program, passes the described arguments to it and then listens to register errors from the forked child processes.

Keep in mind, that the `piper.cpp` in some moment has all of the pipes ends and that are additional 4*n* opened file descriptors. The default limit is 64 and you can set a higher limit by the `open_files` property (see subsection 8 from [other properties](/bos-docs/fundamentals/tasks/task-properties.md#other-properties)).

### Limiting global memory

This is another reason for a task to be interactive. Here, we are talking about limiting the memory to very small amounts that are not possible with the memory limit. One good way to achieve this is to run the contestant's program several times on different tests and check that the program makes the same steps for the same test. The downsides of this approach are that it requires the program to be deterministic and the overhead to achieve this is significant. If there is communication through the pipes many times, it can become very slow. So it can be a challenge to make the whole process efficient enough.

Another way to achieve this is using C++ syntax means - *constant expressions*. The contestant is required to write `constexpr` functions which are **intended** to be evaluated at compile time. This can be done if the arguments passed to those functions can be evaluated at compile time and also if all statements and expressions within those functions are can be evaluated at compile-time. So if the functions are truly `constexpr`, then they cannot use non-*constant expressions* from the global memory, i.e. they cannot save useful information in global memory between different calls.

The problem is that these functions are not required to be evaluated at compile time. The best practice is to make a small test during compile time to check that the result of the function is a *constant expression*. Unfortunately, it is still possible that everything compiles fine and the function uses global non-*constant expressions* because the test cannot traverse all branches when there are conditional statements.

One requirement for the `constexpr` functions is that the compiler has to know their definitions during the early compilation - before the linking stage. This means that the contestant's program has to be included in the jury's program - the *grader*. Technically, here only the *grader* program is compiled and it must include `solution.h` - the contestants submit header files instead of C++ programs. This has to be configured only by adding `extensions=h` to `grade.properties`. When this is configured, only the *grader* program is compiled, and the contestant's source is in that folder with the name `solution.h`. The only difference from the normal compilation is the additional flag to the compilation command: `-fconstexpr-depth=2048`, which makes the maximum limit of the depth for evaluating `constexpr` functions more generous.