(Challenge) Interleaving Strings

All submissions for this problem are available.
Chef has $N$ decimal strings $S_1, S_2, \ldots, S_N$ with him (that is, each of these strings contains only characters '0' through '9'). The characters in all strings are indexed starting from $1$. Chef wants to form a single long string $W$ by *interleaving* all these strings. A string $W$ is said to be formed by interleaving $S_1, S_2, \ldots, S_N$ if the characters of $W$ can be partitioned into $N$ subsequences $T_1, T_2, \ldots, T_N$ such that for each valid $i$, $T_i$ is identical to the string $S_i$. Formally, for each valid $i$, the subsequence $T_i$ must have length $S_i$; let's denote $T_i = (T_{i, 1}, T_{i, 2}, \ldots, T_{i, S_i})$, where $1 \le T_{i, j} \le N$ and $T_{i, j} \lt T_{i, j+1}$ for each valid $j$. Each integer between $1$ and $W = S_1 + S_2 + \ldots + S_N$ inclusive must occur in exactly one of these subsequences, and for each valid $i$ and $j$, the $T_{i, j}$th character of $W$ must be identical to the $j$th character of $S_i$. For example, if $S_1$ is "123", $S_2$ is "456" and $S_3$ is "789", then the strings "124758963" and "123456789" are formed by interleaving these strings, but "123456798" is not. The *cost* of the interleaved string $W$ is defined as $\sum_{i=2}^{W} W_i  W_{i1}^2$, where $W_i$ denotes the integer represented by the $i$th character of $W$. For example, if $W$ is "124", then its cost is $2  1^2 + 4  2^2 = 1 + 4 = 5$. Chef wants you to find an interleaved string $W$. The cost of this string should be as low as possible. ### Input  The first line of the input contains a single integer $N$.  $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains a single string $S_i$. ### Output  Print a single line containing $W = S_1 + S_2 + \ldots + S_N$ spaceseparated integers. For each valid $i$, the $i$th of these integers (let's denote it by $x$) should denote that the $i$th character of your interleaved string comes from the string $S_x$.  Your output will be considered valid if for each $i$ ($1 \le i \le N$), your output contains the integer $i$ exactly $S_i$ times. ### Constraints  $N = 10,000$  $S_i = 100$ for each valid $i$  $S_1, S_2, \ldots, S_N$ contain only decimal digits, i.e. characters '0' through '9' ### Scoring The score of each test case (and therefore each test file) is the cost of the string $W$ described by your output, i.e. $\sum_{i=2}^{W} W_i  W_{i1}^2$. The score of a submission is the sum of scores of all test files. Your goal is to minimise the score of your submission. If your output is invalid, the verdict of your submission will be Wrong Answer. There are twenty test files  ten of each type described below. During the contest, the displayed score will account for exactly four test files, i.e. your score reflects your submission's performance on 20% (4/20) of the test files, two for each of the types described below. However, if your program gets a nonAC verdict on any test file, your submission's verdict will be nonAC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program's scores over the other sixteen test files. ### Example Input ``` 3 123 456 789 ``` ### Example Output ``` 1 1 2 3 2 3 3 2 1 ``` ### Explanation The output corresponds to the string "124758963". The score for this test file would be the cost of this string, which is $46$. ### Test Generation Process There are two types of test files. **Type 1**: Each character of each string is chosen uniformly randomly from the set {'0', '1', ..., '9'}. **Type 2**: Each character of each string is chosen randomly from the set {'0', '1', ..., '9'}. The probability of '0' being chosen is $0.4$, the probability of '1' being chosen is also $0.4$ and the probability of each of the remaining 8 characters being chosen is $0.025$.Author:  admin3 
Tags  admin3 
Date Added:  5032019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions