| | You are receiving a special message from command. Unfortunately, the terminal used by command
to enter and send the messages is known to have issues. Most of the time, each letter is sent correctly,
but occasionally, a character may be sent incorrectly, or omitted altogether. Fortunately, you have
the ability to request them to resend any part of the message. Unfortunately, the re-sent portion
of the message may also have errors, in similar manner to the original. However, you can also request
a checksum value for any segment of the message, which is guaranteed to be accurate. Of course, as
time is of the essence, you want to do as few additional message requests as possible, while still
properly receiving the original message.
Checksum values are calculated by assigning each letter 'A..'Z' a value 0..25. Those values are
added together, and the result MOD 26 is the checksum.
The message to be received is a String of 'A'-'Z' characters. The terminal that sends
messages will have a fixed error rate for each test case. Characters sent correctly are naturally
sent correctly. Errors will result in either the sending of a random character or omission of the
character from the message, chosen at random, non-uniformly, but with a distribution that is fixed
for each test case.
Method Description
Your code should implement a method as described here:
String receiveMessage(int length, String received)
Where the parameters are as follows:
- length: The actual length of the correct message.
- received: The message (inclusive of any errors) as you initially receive it.
- Return value: Your best estimate of the actual original message.
Additionally, you can call two library methods to request additional information about the message:
- int Sender.getChecksum(int start, int length):
Returns a (correct) checksum for the requested substring of the message. Each call to this method
has a fixed cost of 5.
- String Sender.getMessage(int start, int length):
Resends (with possible errors) the requested substring of the message. Each call to this method
has a cost equal to the length.
Scoring
Your score will be based upon two factors: correctness of the return value, and the total cost
of messages requested. Correctness here is defined as the edit distance between the actual
message, and your return value. Cost is defined as the total cost of each of the library method
calls that were made. Your score for each test case is then calculated as:
(CORRECTNESS + 1) * (COST + 100)
If your code throws an error, times out, or makes any calls with invalid parameters, that test
case will receive a score of 0.
Your overall score is calculated as the sum of BEST / YOUR (for all cases where you scored greater
than 0), divided by the number of test cases,
and multiplied by 1,000,000. BEST and YOUR refer to the best (lowest) score anyone achieved on that
test case, and YOUR refers to YOUR score on that test case.
Test Case Generation
- The length of the message is chosen between 100 and 10000, and each character of the message is chosen uniformly at random.
- The error rate is chosen between 0.01 and 0.50, uniformly at random.
- A distribution for errant characters is chosen:
- The 26 valid characters, and an empty string (e.g. "character send omission") are placed in an array and permuted at random.
- Any time an errant character is chosen, it is selected by choosing the SQRT(RAND(0..728)) element from that array.
- Note: this means that errant characters are sent in a way which does not depend upon the correct character,
and such that characters closer to the end of the shuffled array appear more often than those at the front.
Notes
- Time limit per test case is 10s, and memory limit is 1GB.
- There are 10 example test cases, 50 provisional tests, and 1000 system tests.
- There is no explicit code size limit. The implicit source code size limit is around 1 MB (it
is not advisable to submit codes of size close to that or larger). Once your code is compiled, the
binary size should not exceed 1 MB.
- The compilation time limit is 30 seconds. You can find information about compilers that we
use and compilation options here.
- This contest is rated.
- An offline tester is available.
|