Shisuko's blog

[Help] On making "magician & assistant" problems---How to stop functions from sharing info?
By Shisuko, history, 2 months ago, In English

So, I learned that it is possible to implement IOI-style tasks on Codeforces by implementing a grader program.

The gist of the problem I want to set is: Given x, implement two functions encode(x) and decode(code) such that decode(encode(x)) == x. This is a pretty standard class of puzzles.

Unfortunately, if the setter only makes one grader file, and the participant submits one file with the implemented functions, then it is possible for them to maintain a global map that just contains the actual exact answers for each x, and then cheese the problem this way.

I believe the way to get around this is to run all the encode steps in one run, and then run all the decode steps on a second run. My guess is that I can do this by ticking the following "Advanced Settings" box on Polygon:

Is this correct? If so, could someone be kind enough to please share me an example of a Polygon problem that does this, so I can see what I need to implement?

  • Vote: I like it
  • +49
  • Vote: I do not like it

»
2 months ago, # |
← Rev. 2   Vote: I like it +53 Vote: I do not like it

Theoretically it is like this.

Remind yourself that when you tick "Is problem interactive", the pipeline becomes:

  • (Input) => inf in Interactor, inf in Checker;
  • Interactor (ouf and cout) <==> Submission (STDOUT and STDIN);
  • Interactor Output (tout) => ouf in Checker;
  • Verdict = Interactor Verdict && Checker Verdict.

When you tick "Run solutions twice" (alongside interactive), the pipeline changes slightly. It becomes:

  • (Input) => inf in Interactor (First Run), inf in Checker;
  • Interactor (First Run, ouf and cout) <==> Submission (First Run) (STDOUT and STDIN);
  • Interactor (First Run) Output (tout) => Submission (Second Run) Input (STDIN);
  • Submission (Second Run) Output => ouf in Checker;
  • Verdict = Interactor First Run Verdict && Interactor Second Run Verdict && Checker Verdict.

When you also tick "Interactive second invocation", the pipeline again changes to:

  • (Input) => inf in Interactor (First Run), inf in Checker;
  • Interactor (First Run, ouf and cout) <==> Submission (First Run) (STDOUT and STDIN);
  • Interactor (First Run) Output (tout) => inf in Interactor (Second Run)
  • Interactor (Second Run, ouf and cout) <==> Submission (Second Run) (STDOUT and STDIN);
  • Interactor (Second Run) Output (tout) => ouf in Checker;
  • Verdict = Interactor First Run Verdict && Interactor Second Run Verdict && Checker Verdict.

In any case the validator only checks the input given initially, not between the pipelines. The Interactor on both runs are the same Interactor, similar to how the submissions are the same as well.

So, what you want to do is:

  • Tick both "Run solutions twice" and "Interactive second invocation". (I am assuming you already use an interactor)
  • To the Interactor, feed the initial input with information denoting which run it is now (AFAIK, I and many people prefer prepending first to initial input to do this)
  • The Interactor judges the first run, and generates the information to send to the second run, with information denoting which run it is again (you can prepend second to the input to do this)
  • The Interactor, given the necessary information from the first run, judges the second run and sends final information to the checker.
  • Between the first and second run, information is only sent from Interactor (First Run) to Interactor (Second Run), and not between the submissions. This should be what you are looking for.

I hope this helps you well in your preparation (This is not very well documented sadly, all this info is found from trial and error)

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Thank you SO MUCH!! This information is invaluable, I was so close to tearing my hair out---I couldn't find it anywhere else

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I seem to be getting something like: FAIL Call register-function in the first line of the main (registerTestlibCmd or other similar) as a Runtime Error in my prep so far.

    My interactor begins with registerInteraction(argc, argv); Do I need to make it begin with registerTestlibCmd(argc, argv) as well? I (blindly) tried doing that, and it caused the output sent to the grader program it was interacting with to become weird

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      This happens when you used a testlib function but didn't call register* in a source; it might be your interactor, validator, checker, or generator. I am guessing probably checker or generator.

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Hmm. The checker, generator, and validator do not seem to be the issue, I think. I have just been playing around with Polygon all afternoon, tweaking things and checking the cerr in Invocation.

        Here is the gist of the current state of my interactor. My grader just invokes the encode and decode functions implemented by the contestant, and sends the desired return value back to the interactor.

        I have some debugging logic in here.

        #include <bits/stdc++.h>
#include "testlib.h"
using namespace std;

int main(int argc, char **argv)
{
    registerInteraction(argc, argv);
    ...
    string mode = inf.readToken();
    if (mode == "first") {
        tout << "second" << endl;
        int n = inf.readInt(1, 2024);
        ...
        for (int i = 0; i < n; i++) {
            // read from test data, then ask the interactor to evaluate it
            string arguments = inf.readToken();
            cout << "ENCODE" << endl;
            cout << [...arguments...] << endl;

            // 
            string response = ouf.readToken();
            tout << [...arguments...] << endl;
            tout << [...response...] << endl;
        }

    } else if (mode == "second") {
        assert(false);
        ...
        
    } else {
        throw runtime_error(mode);
    }
}

        Note the assert(false); for the second run, which isn't triggering at all for me haha.

        Based on cerr, it seems to me that the first run executes properly and successfully. The Output reported the thing I do want sent to the second run (It starts with "second"...). The interactor also seems to reach the end of its main function successfully, but then the stderr ends with

        FAIL Call register-function in the first line of the main (registerTestlibCmd or other similar)

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Oh! The interactor does need to terminate with quit/quitf as well (same types of verdict as with the checker). In interactive the Interactor and Checker must both return a verdict.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Hmm I added quitf(_ok, "good"); to the end of my interactor and it still doesn't seem to have solved it.

            I still get FAIL Call register-function in the first line of the main (registerTestlibCmd or other similar) after one successful run of the interactor.

            I disabled the validator and replaced the generator with a hard-coded small test case (for debugging purposes). I also double-checked and did in fact make sure that "Is problem interactive", "Run solutions twice", and "Interactive second invocation:" were all are correctly checked and enabled.

            My grader isn't supposed to registerTestlibCmd is it? Could you think of anything else that could cause that error I was getting above.

            I'm sorry to keep bugging you about this, I truly am at my wit's end T_T

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
              ← Rev. 2   Vote: I like it +8 Vote: I do not like it

              :((( I am still unsure where you missed it out. but it has to be either registerTestlibCmd, registerInteraction, registerValidation, or registerGen in the first line of a main function that needs to use testlib.

              In testlib's source code it is like this:

                  ~TestlibFinalizeGuard() {
        bool _alive = alive;
        alive = false;

        if (_alive) {
            if (testlibMode == _checker && quitCount == 0)
                __testlib_fail("Checker must end with quit or quitf call.");

            if (testlibMode == _validator && readEofCount == 0 && quitCount == 0)
                __testlib_fail("Validator must end with readEof call.");

            /* opts */
            autoEnsureNoUnusedOpts();

            if (!registered)
                __testlib_fail("Call register-function in the first line of the main (registerTestlibCmd or other similar)");
        }

        if (__testlib_exitCode == 0) {
            validator.writeTestOverviewLog();
            validator.writeTestMarkup();
            validator.writeTestCase();
        }
    }

              and the functions that change registered are only the four functions said above. So clearly something has to be missing. I hope you find it well...

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it +6 Vote: I do not like it

                THE PROBLEM FINALLY WORKS! It turns out I'm just a dumbass HAHAHAHA

                For future reference of everyone reading: The issue was that I had accidentally copy-pasted include "testlib.h" in the header of the grader.cpp. That's not supposed to be there. So it was the grader.cpp causing that error to occur.

                Anyway, the problem works wonderfully now and I could not have gotten it to work without your detailed advice above. Thank you so much again!

                → Reply