E. Experiment - Bad Genius
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Credits to Saji Tan

For their English class, Alice, Bob, and Cindy must recreate a scene from one of their favorite movies—and if possible (if they have the audacity to), they must attempt to improve upon it in some way. Our friends decided to re-enact the climax of one of their favorite movies of all time, Bad Genius.

Bad Genius is a Thai heist-thriller film... where the "heists" being pulled off are elaborate cheating methods on academic exams! The movie features striking social commentary about the pressure put on students by the school system, but that aside, the "heist scenes" themselves are well-crafted in both idea and execution. We highly recommend it.

For their project, Alice and Bob and Cindy are going to "improve" the climax of the film by fleshing out the details of the plan, providing rigorous justification that shows that the final heist is actually mathematically possible! This is a hypothetical scenario only, and NOI.PH does not endorse actual cheating in any shape or form.

Alice will fly to Sydney to take the Big-Ahh Internal Test (BAIT) early relative to her home country (due to how timezones work). The test consists of $$$100$$$ True or False questions. Alice is a (bad) genius, and she knows the answers to all $$$100$$$ questions the moment she sees them.

Back in their home country, Bob and Cindy are selling custom-made pencils that will help their customers cheat. Each pencil will contain a $$$16$$$-digit code (this code is always in decimal, so its characters are among the digits 0123456789—it may contain leading zeros). Unbeknownst to the test proctors, this $$$16$$$-digit code actually contains the answers (or some of the answers) to the BAIT—or at least, it does if you know how to decipher it.

After taking the exam, Alice—knowing all the answers—phones her friends and tells them what digits should be printed on each pencil. The cheaters do not know the actual $$$16$$$-digit code in advance, until they receive their pencils on the day of the exam—however, there was ample time beforehand for them to have been briefed on the proper decoding scheme for how to extract the answers from it.

These customers will pay more if you can guarantee them a higher score. Configure your scheme to try and guarantee as high a score as possible, across $$$10000$$$ possible answer keys.

Implementation Details

This is an IOI-style problem which may only be solved in Python or C++.

If coding in C++, please implement the following three functions: 


void init();

string encode(string answer_key);

string decode(string code);

If coding in Python, please implement the following three functions: 


def init():
    ...

def encode(answer_key: str) -> str:
    ...

def decode(code: str) -> str:
    ...

You may use the code templates linked here. These functions should have the following behavior:

  • encode accepts an answer key, which is a string of length $$$100$$$, where each of its characters is T (for True) or F (for False). It should then return a string containing exactly $$$16$$$ digits—these are what should be printed on the pencils, if this is the answer key. The digits are among 0123456789 and the code may have leading zeros.
  • decode accepts a code, which is a string of exactly $$$16$$$ digits. It should then return an answer sheet, which is a string of length $$$100$$$, where each of its characters is T or F—this is how a cheating student should answer the BAIT if they see this code on their pencil.
  • Your goal is to create encode and decode functions such that decode(encode(answer_key)) matches answer_key in as many places as possible.
The function init() will be called exactly once when your program starts, so you can put any "set-up" (of global state) here.

There will be $$$10000$$$ different answer keys—some were randomly generated, while others were specifically handcrafted. The grade of your program on some test case is equal to the number of items it got correct. Formally, let answer_sheet := decode(encode(answer_key)); then, your grade is equal to the number of indices $$$i$$$ such that answer_key[i] == answer_sheet[i]. Your overall grade is equal to the minimum grade across all test cases.

If your program crashes, or if the return value of encode or decode is invalid, then you get a grade of $$$0$$$.

Some technical details: Your program will be run two separate times. In the first execution, init() is called, and then encode(answer_key) will be called on all $$$10000$$$ answer keys. In the second execution, init() is called, and then decode(code) will be called on all codes produced by the first run, in a randomized order.

Because these are totally separate executions, no information can be sent from encode to decode, other than the parameter code passed into it as argument.

Scoring

Let $$$g$$$ be your overall grade. If $$$g=0$$$, you will get $$$0$$$ points. Otherwise, the number of points you get is $$$$$$3 + e^{g/19}$$$$$$ capped at a maximum of $$$100$$$ points.