Challenge Overview
Problem Statement  
In this task we will consider a certain method of data compression. The compressed representation of data is a vector of N strings (S[1], S[2], ..., S[N]), where N <= 8. Each character in each string S[i] is a digit or a lowercase letter ('a''z'). Only the digits between '2' and N, inclusive, are allowed, so, for example, for N = 5 the set of allowed digits is {'2', '3', '4', '5'}.
In order to decompress such vector of strings into a single string, it's necessary to call decompress(1) and take the return value. The pseudocode for decompress function is shown below: string decompress(int id) { string res = ""; for (int i = 0; i < length(S[id]); i++) { if (S[id][i] is a letter) { res += S[id][i] } else { res += decompress(parseInt(S[id][i])); } } }In other words, the function goes through the characters of S[id], from left to right. Each letter is directly appended to decompression result. Each digit corresponds to a certain string from S (for example, '3' corresponds to S[3]). We call decompress for the corresponding string and append the return value to decompression result. In some cases, the decompression routine falls into infinite recursion, making it impossible to decompress the data. Therefore, we impose an additional restriction on the compressed data. Consider a directed graph containing N vertices 1, 2, ..., N. There is an arc from vertex i to vertex j in this graph if and only if S[i] contains an occurrence of digit j. In this task, only such compressed data is allowed that corresponding directed graph doesn't contain a cycle reachable from vertex 1. Note that loop arc is also considered to be a cycle. With this additional restriction, the recursion is always finite and decompression result is welldefined. Implementation details You will need to implement the method compress that takes String data and int[] limits as its input parameters. You should compress data into a vector (S[1], S[2], ..., S[N]) as described above. The value of N must be equal to the number of elements in limits. The length of each S[i] should not exceed the value given in ith (1based) elements of limits. The return value must be a String[] containing Strings S[1], S[2], ..., S[N], in this exact order. The decompression result of your return value must not be exactly equal to data, but it must be as similar to data as possible. The similarity between two strings A and B is defined as the number of positions i such that 1 <= i <= min{length(A), length(B)} and ith (1based) characters in A and B are the same. Scoring Suppose that your return for a test case has a valid format and decompresses to a string ret. Then your score for this test case will be equal to (similarity between ret and data) / length(data). Your overall score is calculated as follows: for each test case, you get the amount of points equal to YOUR_SCORE / MAX_SCORE, where YOUR_SCORE is your score for this test case and MAX_SCORE is the maximum among scores for this test case achieved by all competitors. There is one exception: if MAX_SCORE = 0, then all competitors get 0 points for this test case. Test case generation In the text below, words "chosen" and "random" always imply that uniform distrubution is used, unless another distribution is specified. Each test case will be generated as follows:
An offline tester is provided. You can check its source code for the exact scoring and test case generation implementations.  
Definition  
 
Notes  
  The memory limit is 1024 MB and the time limit is 30 seconds (which includes only time spent in your code).  
  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.  
  The processing server specifications can be found here.  
  There are 10 example test cases and 100 full submission test cases.  
Examples  
0)  
 
1)  
 
2)  
 
3)  
 
4)  
 
5)  
 
6)  
 
7)  
 
8)  
 
9)  

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)2020, TopCoder, Inc. All rights reserved.