| 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 well-defined.
**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 i-th (1-based) 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 i-th (1-based) 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:
- N is chosen between 4 and 8, inclusive.
**limits** is generated as an int[] containing N elements, with each element being chosen between 16 and 32, inclusive.
**data** is generated in several steps:
`order` is chosen as a permutation of {1, 2, ..., N} such that its last element is equal to 1.
- Strings S[1], S[2], ..., S[N] are generated in the following order: first S[
`order`[1]], then S[`order`[2]], ...,
finally S[`order`[N]].
- Each S[
`order`[i]] is generated as follows. Its length is set to **limits**[`order`[i]]. Each character is initially set to '?'. Then, for each j, 1 <= j < i, in order from i-1 down to 1,
r distinct '?' characters are chosen and replaced with `order`[j] characters, where r is generated an min{m, random integer between 1 and 4} and m is the number of remaining '?' characters. Finally, if there are any '?' characters left, each of them is replaced with a random lowercase letter.
- Strings S[1], S[2], ..., S[N] are decompressed into
**data**.
- If the length of
**data** is greater than 100000, then **data** is replaced with the prefix of **data** containing first 100000 characters.
- Real number
`errors` is generated as 0.0, random value between 0.0 and 0.04, random value between 0.04 and 0.16, random value between 0.16 and 0.64 or random value between 0.64 and 2.56 (each of these 5 cases is equiprobable).
- X times the following procedure is repeated: a random position within
**data** is chosen and the character at this position is replaced with a random lowercase letter. X is calculated as floor(`errors` * length(**data**)).
**Tools**
An offline tester is provided. You can check its source code for the exact scoring and test case generation implementations. |