TopCoder problem "StringDecryption" used in SRM 480 (Division I Level Three)



Problem Statement

    TopCoder Security Agency (TSA) has successfully obtained the string encryption scheme used by the enemy to encrypt strings of digits. This encryption scheme can be described as follows:



Each non-empty maximum set of identical consecutive digits in the original string is replaced by an integer followed by a digit. The integer is the number of consecutive digits that are going to be replaced (without leading zeroes) while the digit is the same digit as those which are going to be replaced. For example, "122" will be replaced by "1122".



The procedure above is applied twice, first to the original string, and then to the result of the first application. For example, "122" becomes "1122" after one application, and becomes "2122" after the next application.



Although encryption is easily implemented with this procedure, retrieving the original data is not since there may be multiple original strings encrypted into the same resulting string. For example, "2122" may be the result of the encryption of the following strings: "122", a string consisting of 112 copies of digit '2' and a string consisting of 22222....22222 (211 '2's) copies of digit '2'.



It is conjectured that the enemy transmits some additional data that allows the encrypted string to be uniquely decrypted. However, TSA has no access to this data, so their only chance to decrypt the messages is to check all possible decryptions.



You are given a String[] code. Concatenate all elements of code in the order in which they are given to obtain a single string S. Compute the number of different strings that will be encrypted to S according to the scheme described above. Return this number modulo 1,000,000,009. If there are no such strings, return 0.
 

Definition

    
Class:StringDecryption
Method:decrypt
Parameters:String[]
Returns:int
Method signature:int decrypt(String[] code)
(be sure your method is public)
    
 

Constraints

-code will contain between 1 and 10 elements, inclusive.
-Each element of code will contain between 1 and 50 characters, inclusive.
-Each character in code will be a digit ('0'-'9').
 

Examples

0)
    
{"2122"}
Returns: 3
The example from the problem statement.
1)
    
{"012345"}
Returns: 0
2)
    
{"123","4056","789"}
Returns: 1555366
3)
    
{"1"}
Returns: 0
4)
    
{"10000000101"}
Returns: 1
5)
    
{"36029876684872327223276091861774662608610223162723",
 "03488815136338720301059585173865765204966825388127",
 "28905156607840356770675251838346615448480878517234",
 "48346801533058114299540857443030369316232988018148",
 "10266938012137248616925283167856138261491565599857",
 "63098906296356837907112034583226442670798371015701",
 "04431120878401385924047425666758653777487585276695",
 "60451685064284613241730873806124686837402534256835",
 "74510620643600499901411494702324867762597665590427",
 "82564618006706585886295436740966342057330943523869"}
Returns: 882582353
6)
    
{"11111111111111111111111111111111111111111111111111",
 "12222222222222211122222222222221112222222222222111",
 "12000000000000211120000000000021112000000000002111",
 "12222220222222211120222222222221112022222222202111",
 "11111120211111111120222222222221112022222222202111",
 "11111120211111111120000000000021112000000000002111",
 "11111120211111111122222222222021112022222222202111",
 "11111120211111111122222222222021112021111111202111",
 "11111120211111111120000000000021112021111111202111",
 "11111122211111111122222222222221112221111111222111"}
Returns: 371459312
7)
    
{"89210"}
Returns: 95

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10748

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14159&pm=10748

Writer:

dolphinigle

Testers:

PabloGilberto , ivan_metelsky , it4.kp

Problem categories:

Dynamic Programming, Encryption/Compression