Churu and his Sequence
All submissions for this problem are available.
Given a list of N numbers, say A[1..N]. And a set of integers S. Each A[i] belongs to the set S. Being said that let us first define if a array is ‘good’ or not good. We say a array, Ar[M] of size ‘M’, good if
for every pair of index (A[i] !=A[j] and 1 ≤ i, j ≤ M) there exist some index k (1 ≤ k < M) such that at-least one of the following condition hold
- Ar[k] = Ar[i] and A[k+1] = Ar[j]
- Ar[k] = Ar[j] and Ar[k+1] = Ar[i]
If it holds for every valid pair of index then we say that array Ar is good otherwise we say Ar is not good.
The given array A[N] may not be good initially and Churu want to make it good. To make the list A[N] good Churu can only do the following -
- Select an integer from the given set S.
- Then append this selected integer at the end of the list.
Churu can do these operations as many times as he wish.But appending an integer in the array is not for free. Churu has to spend some money to append an integer at the end. This amount depends on the integer that he wants to add (say e1) and the last element of the list (say it e2) after which he will append e1. Exact cost can be found from the cost matrix that will be given. Let the size of the set S be s = |S|. A symmetric cost matrix C[s][s] will be given. C[i][j] represents the cost of adding integer S[i] on an list if the last element of the list is S[j]. Now Churu wants to make the array good in minimum possible expenditure. Help him. Print the minimum cost to make resulting list which is good. Note that the input list, A, must be a prefix of the output list and final list and A must end with same number. Also include the initial cost to make the matrix. Assume 1st element was added free of cost.
- The first line of the input contains an integer N denoting the size of A.
- Next line contains N space separated integrs denoting the initial array A.
- Next line contains single integer s denoting the size of set S.
- Next line contains s space separated integrs denoting the set S.
- All elements in S will be distinct.
- Next s lines contain s space separated integers, jth element of ith line denotes cost of appending S[i] after S[j].
- Cost matrix will be symmetric.
Output a single integer denoting the minimum total cost required to make the sequence good.
- 1 ≤ N ≤ 104
- 1 ≤ A[i] ≤ 103
- 1 ≤ s ≤ 200
- All elements of A belong to S
- 1 ≤ S[i] ≤ 103 for all 1 ≤ i ≤ |S|
- 1 ≤ c[i][j] ≤ 103 for all 1 ≤ i,j ≤ |S|
Input: 3 1 2 3 4 1 3 4 2 1 1 1 1 1 2 2 2 1 2 3 3 1 2 3 4 Output: 5
The optimal good sequence for the sample example will be - out = 1 2 3 1 3. Given sequence 1 2 3 is prefix of this sequence. Also for each valid pair of index (i, j), out[i] and out[j] occurs consecutively somewhere in the output list. Total cost = Initial cost + Additional cost = cost due of 1-2 + cost due to 2-3 + cost due to 3-1 + cost due to 1-3 = 1 + 2 + 1 + 1 = 5. First three terms are due to the initial list and rest two terms are due to additional elements appended.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.