Optimal Chain Cutting
Chain production department (CPD) has been asked to deliver a non-standard specimen of a chain.
Chains produced by CPD are made of links of different sizes. This unusual feature simplifies
tracking of their movement, when they are operated in heavy industry automatized environments
which depend on reliable computer image recognition.
The demand specifies exact sequence of link sizes in the finished product.
Currently, the machinery at CPD produces only one type of chain which may be subsequently modified to
fit other demanded specimen parameters. It is called standard chain.
This chain type has fixed length and also the sequence of sizes of all links in the chain is fixed.
It clearly does not match the demand. It is longer, and the sequence of link sizes is different.
Engineers at CPD can utilize three approved chain operations to construct the demanded chain.
The Cut out operation produces a piece of chain of arbitrary length by
cutting it out from a standard chain produced by CPD.
It is a heavy cut and it has to be done by machinery belonging to another department in the factory.
Although the cost of this operation is effectively zero to CPD,
the remaining part(s) of the original chain is claimed by the other department
and CPD looses any access to it.
The Clip operation is more sophisticated.
It disconnects a chain at two different places, each time between two joined links.
It then disposes of the chain piece located between those two places and merges together the
remaining two parts of the chain by joining the two links which were
disconnected from the removed part. The cost of the operation is equal to the sum
of sizes of the two disconnected links in the removed part, multiplied by the so-called Clip factor,
which is a small integer number.
The machine performing Clip operation is quite sensitive and it can remove even a single link from a chain.
In such case, the cost is equal only to the size of the removed link multiplied by the Clip factor.
The Replace operation removes a single link from a chain and substitutes it (at the same place in the chain)
by a link of different size. The cost of one substitution is equal to the
difference of sizes of the two involved links, multiplied by the so-called Replacement factor.
All sizes of replacement links are always available.
None of the Clip or the Replace operations can be applied to the whole standard chain produced by CPD, the chain is too heavy for the machines.
With the help of the given operations, CPD can meet the demand.
They can produce a standard chain, cut out from it a piece of demanded length and then
replace in it one link after another, until the result matches perfectly the demand.
Also, in a more clever scenario, CPD may first cut out a longer piece of chain
than it is demanded, and then reduce replacement costs by applying Clip operation one or more times
at strategically selected places in the cut out chain.
The machine performing Clip operations has important limitations. It can remove from a chain only such
shorter piece which it is preprogrammed to recognize. The description of each recognized
chain piece is called a Clip scheme and it is stored in the machine in the form of complete sequence of link sizes in the piece.
The removed piece must match exactly, link after link, one of these descriptions.
It is obvious to the engineers at CPD, that the costs of different scenarios are different and
that the cost of producing the demanded chain should be minimized by a selection of
an appropriate piece of the standard chain, followed by a sequence of appropriately
chosen Clip and Replace operations.
that there should be a sequence of Clip and Replace operations which minimizes the cost of producing the demanded chain,
when a suitable piece of chain is cut out from a standard chain.
Each chain and a piece of chain involved in the process has defined front end and rear end.
The shape of the chain links is asymmetrical and thus a reversed chain or its piece cannot be utilized in any way.
Figure 1. An example of the problem and its solution. The demanded chain and the standard chain produced at CPD are depicted at the top.
Available clip schemes are depicted on the left. The sizes of chain links are written above or below the links.
The front ends of chains are their left ends in the image.
A sequence of applied operations on the selected part of the standard chain is depicted in the middle, from top to bottom.
The operations result at the bottom matches the demand exactly. The total cost of the operations depends on the values of the Clip and Replacement factors.
When these are equal to 1 and 5, respectively, the depicted sequence of operations yields a minimum total cost equal to 17.
Note that one of the Clip schemes remains unused.
There is another sequence of operations which yields the same cost. It processes the piece of original chain at positions from 10 to 16
(position indexes are 1-based). The depiction illustrates Example 1 below.
|
The task
You are given the description of the current chain type produced by CPD,
the description of the demanded chain and the list of descriptions of all chain specimens
in the depot. Also, you are given the values of the Clip and Replacement factors.
Calculate the minimum cost of producing the demanded chain.
Coding scheme
For simplicity, all link sizes, which are 1, 2, 3, ..., 20 are coded by small characters of English alphabet a, b, c, ..., t.
Any chain is represented as a sequence of characters coding the link sizes in the chain, from the front end of the chain.
The exact sequence of link sizes in the standard chain is generated by a Code matrix which is a rectangular array of characters.
Each cell in a Code matrix contains a single character.
A path in the matrix is a sequence of cells in the matrix. The first cell on a path may be any cell in the matrix top row.
Each subsequent cell on the path lies in the subsequent row and it is adjacent to the previous cell in the path
either vertically (the cells share borders) or diagonally (the cells share one corner).
Note that the length of all paths in the matrix is the same and it is equal to the number of rows in the matrix.
A path p1 is smaller than another path p2 when either the start of p1
lies to the left of the start of p2,
or when initials parts of p1 and p2 coincide down to a row k,
and then on the row k+1, the cell in p1 lies to the left of the cell in p2.
The contents of the path is the sequence of characters in the cells forming the path, arranged in the same order.
The standard chain description is equal to the contents of all different paths listed in ascending order of the paths.
For example, in the matrix
ab
cd
ef
there are 8 different paths, each of length 3. Their contents, in ascending order of the paths are:
ace acf ade adf bce bcf bde bdf
The standard chain description coded by the matrix is the same character sequence, only with spaces removed:
aceacfadeadfbcebcfbdebdf
Coding scheme is highly effective, a Code matrix of size 10 × 10
describes a chain with 1369460 links.
Input
The first line contains six positive integers R, C, LD, CS, CF, RF
separated by space and representing (in this order) the number of rows in the production matrix, the number of columns in the same matrix,
the length of the demanded chain to be produced, the number of Clip schemes available, the Clip factor, and the Replacement factor.
Next, there are R lines specifying the production matrix. Each line contains a string of C characters.
The next line specifies the demanded chain.
Next, there are CS lines specifying the available Clip schemes. Each line specifies one scheme.
It holds, 2 ≤ R, C ≤ 15, LD ≤ 500,
CS ≤ 500, CF, RF ≤ 10.
The length of the standard chain is less than 2.5×105. The length of any Clip scheme less than 20.
There are no blank spaces in any line after the first line.
Output
The output consists of one line containing 3 integers separated by spaces.
The first integer represents the position in the standard chain of the first link of the piece obtained by the Cut out operation.
The second integer represents the length of the same piece.
The third integer represents the cost of subsequent modification of this piece which turns it into the demanded chain.
The modification cost is minimum possible.
When there are more possibilities of cutting out a chain piece which lead to the same minimal cost,
the shorter piece is preferred. When the lengths of such pieces are equal, the one which was cut out closer
to the front end of the standard chain is preferred. The position indexes are 1-based.
Example 1
Input
3 2 5 2 1 5
aa
bc
da
bcadb
aa
dac
Output
8 7 17
The standard chain in Example 1 is coded by the sequence abdabaacdacaabdabaacdaca.
Example 2
Input
3 2 7 6 2 9
ab
cd
aa
baaadcbd
acaad
bc
bdab
cb
daad
abcab
Output
2 22 42
The standard chain in Example 2 is coded by the sequence acaacaadaadabcabcabdabda.
Example 3
Input
2 3 8 4 4 4
aaa
dcb
abcdabcd
a
bac
cab
cad
Output
3 8 32
The standard chain in Example 3 is coded by the sequence adacadacabacab.
The same minimum cost 32 can be achieved by Cut out operation producing the chain piece acadacabac . However, the length of this piece is 10, it is not preferred.
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set