JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 105
Problem: MessageChecksum

Problem Statement

    

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.
 

Definition

    
Class:MessageChecksum
Method:receiveMessage
Parameters:int, String
Returns:String
Method signature:String receiveMessage(int length, String s)
(be sure your method is public)
 

Available Libraries

    
Class:Sender
Method:getChecksum
Parameters:int, int
Returns:int
Sample Call:val = Sender.getChecksum(start, length);
Method:getMessage
Parameters:int, int
Returns:String
Sample Call:val = Sender.getMessage(start, length);
    
 

Examples

0)
    
Message Length = 20
Error Rate = 0.1
Actual message = FKVQJUQUVQVRUDLPQEZZ
Initial received = FKVQUQUHQVRUDLPCEZZ
1)
    
Message Length = 40
Error Rate = 0.12
Actual message = OBZYDMUGUTNSHWWQYFRCRLPRMAURWIEEUSHKQKLG
Initial received = ABZYDMUGUTZSHWWNYFRCRLPRMARWREEUSHKQKPG
2)
    
Message Length = 80
Error Rate = 0.15
Actual message = GIWIKMZBNECGICBUHYQFQGARRMXKOZJKLQLPPTECFFWOEGVWPUKYUAVHNKTEVQNFQXQURHVQIPFJQGGS
Initial received = GIWIKMZBNLCGECBUHYQFSGARRMXXOZNDQBPPCECAFWOEOVWPUKYQAVHNKTEVJWFQXQURHVQIPFJSGGS
3)
    
Message Length = 1664
Error Rate = 0.09668446013422387
4)
    
Message Length = 8439
Error Rate = 0.12638672261669556
5)
    
Message Length = 8160
Error Rate = 0.281784576448056
6)
    
Message Length = 4051
Error Rate = 0.15477304620217414
7)
    
Message Length = 4687
Error Rate = 0.25077157207534734
8)
    
Message Length = 704
Error Rate = 0.46848858099584795
9)
    
Message Length = 3028
Error Rate = 0.05341168236506482

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.