Introduction

Run-twice problems (also called multipass or communication problems) are problems in which your program is executed twice. Here are some examples:

• 2054A - TON Block Compression from the TON marathon.
• Problems D, G and K from Universal Cup Season 2 Stage 5.
• All problems from Universal Cup Season 2 Stage 16.
• Flash from BOI 2019 (this one is actually more complicated, but the premise is the same — there are multiple instances of your program which cannot share data except through the interactor.

As you can see, there are many ways this format can be used, but the common themes are encoding/decoding, compression/decompression, constructing a bijection and similar ideas. The general principle is that you have to implement two functions and the second function has to somehow use the value returned by the first function. Run-twice is useful if the problem would be ruined if the second function had access to the input data of the first function.

It is possible to prepare run-twice problems on Polygon and to host them on Codeforces. I think there is a lot of unexplored design space for problems here. This is why I am showing how to prepare them here — to encourage problemsetters to set more run-twice problems. $$$~$$$

This tutorial is completely unofficial: everything I've written here is either figured out by experimentation or gathered from little bits I've found in blogs here. Also, I think it's fair to assume that unless Mike or someone else from Codeforces says so, all APIs mentioned here are "unstable" — they may be changed at any time and future versions may not be backwards compatible.

Even and Odd Combinations

Let's start by preparing problem B from Universal Cup Season 2 Stage 16, one of the easier problems from the set. I've slightly simplified the problem here (by removing multi-test) for ease of explanation.

Problem. Let $$$A_n$$$ be the set of even-length subsequences of the array $$$[1, 2, \ldots, n]$$$ and let $$$B_n$$$ be the set of odd-length subsequences of the same array. Construct a bijection between these two sets. To prove that you have constructed a bijection, your program will be run twice.

• First run. The first line of the input consists of two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 50$$$, $$$0 \le k \le n$$$). The second line of the input consists of $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ in ascending order. Print two lines of output; the first line must consist of two integers $$$n$$$ and $$$\ell$$$ ($$$0 \le \ell \le n$$$); the second line must consist of $$$\ell$$$ integers $$$b_1, b_2, \ldots, b_\ell$$$ in ascending order. $$$\ell$$$ must have different parity from $$$k$$$.
• Second run. The input consists of the output from the first run. The output must match the input the first run.

#include <iostream>
#include <vector>

using namespace std;

int main () {
  int n, k;
  cin >> n >> k;

  vector<int> arr (k);
  for (int i = 0; i < k; i++)
    cin >> arr[i];

  if (!arr.empty() && arr.back() == n)
    arr.pop_back();
  else
    arr.push_back(n);

  cout << n << " " << arr.size() << '\n';
  for (int i = 0; i < (int) arr.size(); i++)
    cout << arr[i] << " ";
  cout << '\n';
}

Hopefully it's clear why run-twice is necessary here. If the problem simply asked to implement two functions, the participant could cheat by simply storing the input.

To start preparing a run-twice problem on Polygon, go to General Info -> Advanced and select "Run solutions twice". Now the workflow for running on a test case looks like this:

Blue arrows denote data controlled by you, the problemsetter — test inputs and data printed by your programs. Orange arrows denote data controlled by the participant. You cannot assume anything about them as the participant may choose to output anything they wish.

This setup is inadequate. The output of the first run is forwarded straight to the input of the second run. While this is what we eventually want, it does not work properly right now: we have no way of checking that $$$k$$$ has a different parity from $$$\ell$$$, or even that the output from the first run is in the required format.

The solution is to make the problem interactive. This is now the workflow:

• The input is available to the interactor via inf.
• The interactor can write data to the first run via cout, the submission can read this data from standard input.
• The interactor can read data that the first run writes to standard input from the stream ouf.
• If the interactor quits with a verdict other than _ok, this will be the final verdict of the solution.
• Otherwise, data that the interactor writes to tout will be the input to the second run.
• The checker can read the output of the second run from ouf, the original input from inf, and the output of the second run of the model solution from ans.

Making the problem interactive sounds a bit odd considering that the problem is not interactive from the participant's point of view at all. This is actually pretty common if you go in the unusual problem territory (though part of this is due to the limitations of Polygon's model). In fact, virtually every run-twice problem needs to be interactive (edit: if it is to be hosted on Codeforces). I challenge anyone to come up with a counterexample.

In our case, the interactor will be fairly simple. The interactor reads the input from inf, writes that to cout (where the submission can read it), then reads the first run's output from ouf. If this output is invalid in some way, the interactor quits with _wa, _pe or another failing verdict. Otherwise, it writes that output to tout; that will become the input for the second run.

#include "testlib.h"

#include <vector>

int main (int argc, char **argv) {
  registerInteraction(argc, argv);

  // read the input data
  // this is available as `inf`
  int n = inf.readInt();
  int k = inf.readInt();

  std::vector<int> A (k);
  for (int i = 0; i < k; i++)
    A[i] = inf.readInt();
    
  // forward this data to the first run
  // the standard input of the first run is wired to the standard output
  // of the interactor
  std::cout << n << " " << k << '\n';
  for (int i = 0; i < k; i++) {
    std::cout << A[i];

    // since this is sent to the participant, it should be "well-formed"
    // therefore, we should not send trailing spaces
    if (i != k - 1)
      std::cout << " ";
  }

  // flush the output!
  std::cout << std::endl;

  // read the output from the first run; that is available as `ouf`
  // if any of these reads fail, testlib.h will quit with a _pe verdict
  // and no second run will occur
  int pn = ouf.readInt();
  if (pn != n)
    quitf(_wa, "n=%d in the output of the first run doesn't match original n=%d", pn, n);

  int l = ouf.readInt(0, n);
  if (l % 2 == k % 2)
    quitf(_wa, "l=%d has the same parity as k=%d", l, k);

  std::vector<int> B (l);
  for (int i = 0; i < l; i++)
    B[i] = ouf.readInt(1, n);

  for (int i = 0; i < l - 1; i++)
    if (B[i] >= B[i + 1])
      quitf(_wa, "output of the first run is not ascending");

  // check that the output doesn't contain extra tokens
  // polygon would do this automatically if this was a checker
  // however, there is no such automatic checker for interactors, so
  // this needs to be done manually
  if (!ouf.seekEof())
    quitf(_pe, "extra tokens in the output");

  // now that the input data from the first run is validated,
  // write it to `tout`
  // exercise to the reader: get rid of code duplication 
  tout << n << " " << l << '\n';
  for (int i = 0; i < l; i++) {
    tout << B[i];

    // once again, this is sent to the participant and should be
    // well-formed
    if (i != l - 1)
      tout << " ";
  }
  
  tout << std::endl;

  quitf(_ok, "first run ok");
}

Finally, we need a checker to check that the output of the second run matches the original input. Since this is true for the model solution, we can use ncmp.cpp. However, if you don't trust the model solution, you can also write a simple checker that compares ouf (which is just the output of the second run) to inf.

Swap and Guess

Let's prepare another one. Classical problems about prisoners who cannot communicate but can agree on a strategy beforehand are also a great fit for run-twice problems. For example, let's prepare Anton's problem from this old post.

Problem. There are $$$2n$$$ cards on a table; each contains an unique integer from $$$1$$$ to $$$2n$$$. Your program will be run twice on each test case.

• First run. The cards are face-up. You can pick a pair of cards and swap them.
• Second run. The cards are face-down. You are given a number $$$x$$$ ($$$1 \le x \le 2n$$$) and must find the card with that number. To do so, you are allowed to turn at most $$$n$$$ cards over.

Unlike the last problem, the solution needs to know whether it is in the first or the second run. The easiest way is to have the first token in the input be first or second respectively.

In this problem, the second phase is actually interactive. In the previous problem, the interactor was only invoked for the first run. To enable the interactor for the second run, go to General Info -> Advanced and enable "Interactive second invocation". Now the workflow looks like this:

Now we need to figure out exactly what the interactor should do and what the input files should contain. Of course, the input files should contain the permutation $$$p$$$ and the target card $$$x$$$ (although we will later discuss choosing $$$x$$$ adaptively). But keep in mind that there is no way for the interactor to tell whether it is in the first run or the second run, so we need to pass that information along somehow as well.

We'll say that the input files have the following format:

0 n x
p_1 p_2 ... p_2n

In the first run, the interactor will read that data from inf and pass the word first, $$$n$$$, and the permutation to the submission. The interactor will read the positions of the cards to swap from the submission. Then, it will write to tout data to be consumed by the second run of the interactor. It will be in this format:

1 n x
q_1 q_2 ... q_2n

Here, $$$q_1, q_2, \ldots, q_{2n}$$$ is the permutation after performing the swap. Importantly, we need to pass along $$$x$$$ from the first run of the interactor because the second run has no way of reading the original input file.

Some examples:

#include "testlib.h"

#include <iostream>
#include <vector>

int main (int argc, char **argv) {
  registerInteraction(argc, argv);

  int run = inf.readInt();
  int n = inf.readInt();
  int x = inf.readInt();

  std::vector<int> p (2 * n);
  for (int i = 0; i < 2 * n; i++) {
    p[i] = inf.readInt();
  }

  if (run == 0) { // first run
    std::cout << "first " << n << '\n';
    for (int i = 0; i < 2 * n; i++) {
      std::cout << p[i];
      if (i != 2 * n - 1)
        std::cout << " ";
    }
    std::cout << std::endl; // flush the output!

    // now, read the positions to swap from the participant
    // the participant could print anything, so we need to check that
    // the printed positions fall in the correct range

    // readInt(l, r) will exit with "presentation error" or "wrong answer"
    // if the printed values fall outside the correct range; this will 
    // short-circuit the whole workflow and return a verdict immediately;
    // there will be no second invocation.
    int swi = ouf.readInt(1, 2 * n) - 1;
    int swj = ouf.readInt(1, 2 * n) - 1;

    std::swap(p[swi], p[swj]);

    // finally, pass everything to the second run using the `tout` stream
    tout << 1 << " " << n << " " << x << '\n';
    for (int i = 0; i < 2 * n; i++)
      tout << p[i] << " ";
    tout << '\n';
  } else {
    // second run, TODO
  }
}

In the second run, the interactor reads the input (which is not the original input, but the contents of tout from the last interaction) and passes the word first, $$$n$$$ and $$$x$$$ to the submission. Then, it must read at most $$$n$$$ guesses from the submission and reply to them. If one of the guesses turns out to be correct, the interactor exits successfully (which means the checker will now run), otherwise it exits with a "wrong answer" verdict (and no checker is run).

Codeforces requires that all problems, including interactive ones, have a checker. In this case, there is really nothing to check (the checker will not be run if the submission made too many incorrect guesses), so the checker will be almost a do-nothing program. What you can do, however, is pass some structured data via tout, which the checker can incorporate into the checker message. For example, let's add the number of guesses and the correct $$$x$$$ to the checker message.

#include "testlib.h"

#include <iostream>
#include <vector>

int main (int argc, char **argv) {
  registerInteraction(argc, argv);

  int run = inf.readInt();
  int n = inf.readInt();
  int x = inf.readInt();

  std::vector<int> p (2 * n);
  for (int i = 0; i < 2 * n; i++) {
    p[i] = inf.readInt();
  }

  if (run == 0) { // first run
    // see above
  } else { // second run
    std::cout << "second " << n << " " << x << std::endl;

    // reply to guesses
    int guess_count = 0;
    while (true) {
      // once again, this comes from the participant, so we need to verify that it actually lies in the correct range
      int gi = ouf.readInt(1, 2 * n) - 1; 
      guess_count++;

      if (guess_count > n) {
        std::cout << -1 << std::endl;
        quitf(_wa, "query limit exceeded");
      }

      std::cout << p[gi] << std::endl;
      if (p[gi] == x) {
        // pass x and the number of guesses to the checker
        tout << x << " " << guess_count << '\n';
        quitf(_ok, "ok"); // not the checker message - that will come from the checker
      }
    }
  }
}

#include "testlib.h"

int main (int argc, char **argv) {
  registerTestlibCmd(argc, argv);
  
  // this comes from the interactor's output
  // x could of course also be extracted from the original input data, which is accessible as `inf`
  int x = ouf.readInt();
  int guess_count = ouf.readInt();
  quitf(_ok, "correctly guessed %d in %d guesses", x, guess_count);
}

Adaptively choosing $$$x$$$

In some problems, it may be necessary to make the interactor adaptive. In this case, the permutation is obviously determined ahead of time, but we may want to choose $$$x$$$ based on how the solution chose to swap cards. For example, if the submission failed to make all cycles at most $$$n$$$ elements long, it makes sense to choose an $$$x$$$ on the longest cycle of the permutation.

Let's prepare an adaptive interactor that uses the following two strategies:

• $$$x$$$ is picked uniformly at random from all possible values.
• $$$x$$$ is picked uniformly at random from the longest cycle.

The input data will now obviously need to contain a parameter that indicates which strategy the interactor should use. But it also needs to contain a random seed. If you attempt to use rnd.next(int) in an interactor, it will always return the same values because registerInteraction does not set a seed value (and even if it did, it would always be the same one). Thus, this random seed should also be in the input data and passed along in tout to the second run of the interactor.

The input files will thus have the following format:

0 n strat seed
p_1 p_2 ... p_2n

and in the first run, the interactor will write to tout the input for the second run, with the following format:

1 n strat seed
q_1 q_2 ... q_2n

Here is the new interactor:

#include "testlib.h"

#include <iostream>
#include <vector>

int main (int argc, char **argv) {
  registerInteraction(argc, argv);

  int run = inf.readInt();
  int n = inf.readInt();
  int strat = inf.readInt();
  long long seed = inf.readLong();

  std::vector<int> p (2 * n);
  for (int i = 0; i < 2 * n; i++) {
    p[i] = inf.readInt();
  }

  if (run == 0) { // first run
    std::cout << "first " << n << '\n';
    for (int i = 0; i < 2 * n; i++) {
      std::cout << p[i];
      if (i != 2 * n - 1)
        std::cout << " ";
    }
    std::cout << std::endl; // flush the output!

    // now, read the positions to swap from the participant
    // the participant could print anything, so we need to check that
    // the printed positions fall in the correct range

    // readInt(l, r) will exit with "presentation error" or "wrong answer"
    // if the printed values fall outside the correct range; this will 
    // short-circuit the whole workflow and return a verdict immediately;
    // there will be no second invocation.
    int swi = ouf.readInt(1, 2 * n) - 1;
    int swj = ouf.readInt(1, 2 * n) - 1;

    std::swap(p[swi], p[swj]);

    // finally, pass everything to the second run using the `tout` stream
    tout << 1 << " " << n << " " << strat << " " << seed << '\n';
    for (int i = 0; i < 2 * n; i++)
      tout << p[i] << " ";
    tout << '\n';
  } else { // second run
    rnd.setSeed(seed);

    int x;
    // choose x according to the strategy given in the input file
    if (strat == 0) {
      x = rnd.next(1, 2 * n);
    } else {
      // TODO: identify the longest cycle and choose a random index from it
      // i'll let you figure it out
    }

    std::cout << "second " << n << " " << x << std::endl;

    // reply to guesses
    int guess_count = 0;
    while (true) {
      // once again, this comes from the participant, so we need to verify that it actually lies in the correct range
      int gi = ouf.readInt(1, 2 * n) - 1; 
      guess_count++;

      if (guess_count > n) {
        std::cout << -1 << std::endl;
        quitf(_wa, "query limit exceeded");
      }

      std::cout << p[gi] << std::endl;
      if (p[gi] == x) {
        // pass x and the number of guesses to the checker
        tout << x << " " << guess_count << '\n';
        quitf(_ok, "ok"); // not the checker message - that will come from the checker
      }
    }
  }
}