Multipass problem Support

[mzuenni]

Description of the enhancement request

In multipass problems the submission gets started multiple times and is fed with the output of the output valdiator from the previous run (but besides that the new run has no knowledge of any prior run). This allows some new types of problems about information theory and some other fields.

Expected behaviour

• The submission is run on the test input (like for normal problems)
• The output Validator is run on the submission output (like for normal problems)
• The output Validator either accepts, rejects or indicates that the submission should be run again with a new input that it provides

Any other information that you want to share?

Multipass seems to also get added to the kattis problem package format: https://www.kattis.com/problem-package-format/spec/2023-07-draft.html#multi-pass-validation
Maybe it would also be nice to run the output validator with an argument which indicates which iteration this is or provide a way for the output validator to keep information between invocations.

[vmcj]

Could you provide a minimal problem we can test this with?

[vmcj]

@mzuenni as discussed in person, I'll close this issue as this requires the problemspec to first have a definition for this. Please re-open when that is in a reasonable state so we can start implementing this.

[mzuenni]

Just a small update:

A multi-pass validator can be used for problems that should run the submission multiple times sequentially, using a new input generated by output validator during the previous invocation of the submission.

To signal that the submission should be run again, the output validator must exit with code 42 and output the new input in the file nextpass.in in the feedback directory. Judging stops if no nextpass.in was created, or the output validator exited with any other code.

It is a judge error to create the nextpass.in file and exit with any other code than 42.

• multipass can be combined with validation set to custom or custom interactive.
• Regarding the timelimit, it should be checked per invocation of the submission.
• The judgemessage.txt and judgeerror.txt should not be removed between invocations of the output validator i.e. the validator is responsible for appending/overwriting to the files in there
• The feedbackdir should persist between invocations

Comments:

• If the validator uses stdout and stderr you likely want to display that per invocation

Are there more things that need to be properly defined?

[mzuenni]

Maybe these are helpful for testing:
https://github.com/RagnarGrootKoerkamp/BAPCtools/tree/master/test/problems/multipass
https://github.com/RagnarGrootKoerkamp/BAPCtools/tree/master/test/problems/interactivemultipass

[meisterT]

Example interactive problem on Kattis: https://open.kattis.com/problems/guessinggame2

[meisterT]

To summarize my understanding of the spec:

• the submission is first called with the given input
• the validator can decide whether another pass is needed
• if so, it needs to exit with 42, and put the new input in feedback/nextpass.in
• if no new input is created, then the typical 23/42 exit codes indicate WA/AC

IMHO, the spec should be extended to include a required upper bound of passes.
@mzuenni was this considered?

The following changes are likely required in DOMjudge:

• in the judging backend, we probably could get away with some modifications to https://github.com/DOMjudge/domjudge/blob/main/judge/testcase_run.sh
• in the database/schema, we have to think about how to represent the multiple answers, probably having a list of https://github.com/DOMjudge/domjudge/blob/main/webapp/src/Entity/JudgingRun.php per judging
• in the UI, we have to see, how to represent things in the UI
• no actual scoring changes

All in all doable, but still touches more than just the backend.

[mzuenni]

I think an upper bound was not considered (it is intended that the number of passes is variable so the validator is responsible for deciding the number of passes)... still an upper bound might be a good safeguard against bugs in the validator that result in an infinite loop... but not sure if that should be part of the spec or just a domjudge thing (is the maximum runtime of the output validator specified for normal problem?). maybe a new entry in limits should be added

[eldering]

A limit of validation passes was added in Kattis/problem-package-format#231, defaulting to 2 if nothing is specified.

[meisterT]

We discussed this in person a little bit more.

For a complete implementation we want to do/consider the following:

• In the backend, make multipass problems the default, where non-multipass problems are just a multipass problem with one pass.
• That implies that we do the same isolation between passes that we do between test case runs in terms of chroot and cgroups that we do today.
• From an entity / data storage perspective, we likely want to have the same data about each pass, that we currently have in a JudgingRun. The easiest might just be to say that a judging run is the run on a single pass vs a single test case.
• We have to design how to display multipass output nicely in the UI. We have to consider that the output could be in binary format, so we should be able to handle this as well.
• For the API, the most likely thing is to add a pass type, which probably will look very very similar to https://ccs-specs.icpc.io/draft/contest_api#runs and is a child of it.
• This would also allow downstream clients to continue to work transparently as we don't modify existing structures and it is a backwards-compatible change (with additional info) on top.
• We probably should use this opportunity to better document the flow in the judging backend.

Implementation wise we probably can do baby steps and learn as we go and don't need to do any UI/API/storage changes in the first step as we can just display the info from the last pass.