Shisuko's blog

[Help] On making "magician & assistant" problems---How to stop functions from sharing info?
By Shisuko, history, 5 days 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
  • +15
  • Vote: I do not like it

»
5 days ago, # |
← Rev. 2   Vote: I like it +35 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
  • »
    »
    5 days 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
  • »
    »
    17 hours 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
    • »
      »
      »
      10 hours 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