All submissions for this problem are available.
Recently little Chef was challenged by little Devu. Devu asked little Chef to encrypt a given message efficiently which he will send to Churu. Can you help little Chef in doing so ? Problem can be stated formally as follows.
Devu gave little Chef a tree containing N nodes. Each node of the tree contains an lowercase English alphabet (a - z). He also gave a set S of M strings.
Using the set S and the given tree, Chef need to construct another set S1 of size M. To construct the set S1 he does the following
- For each element from the set S, a string ei, he finds the most similar string ai which is present in the given tree. Then he inserts ai (may be null string) into the new set S1. Note that sets S and S1 may contain duplicate elements.
- Most similar string a of a string e is defined as the longest length substring of string e which is present in the tree. If there are multiple such substrings, then the one whose starting index is smallest is taken. Example, e = 'abc' and suppose 'a', 'ab' and 'bc' are present in the tree, then we take 'ab' (not 'bc').
- We say a string a is present in the tree if there exist two nodes n1 and n2 (not necessarily distinct) such that the the string represented by the path going from n1 to n2 is same as a.
- String represented by the path between nodes n1 and n2 is string obtained when we concatenate the characters available at the nodes in the path between n1 and n2.
Outcome of the encryption is also a string str such that all elements of set S1 are present in str as a substring. If there are many such str then the one with smallest length is chosen. If there are still many such str then the one which is lexicographically smallest is chosen. You need to print the encrypted string str. If str is null string then print "-1" without quotes.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space separated integers N and M as described in the problem statement. N represents the size of the tree. M represents the size of the set S.
- Next line contains N space separated characters ('a' to 'z'). ith character represents the character available at the ith node.
- Next N-1 lines each contains two space separated integers u and v denoting there is edge between node u and v.
- Next M lines each contains a string ei. These M strings are the elements of the set S.
In T lines, for each test case output the answer in a new line. Answer to a testcase is the final encrypted message as described in the problem statement.
- 1 ≤ T, M ≤ 10
- 1 ≤ N ≤ 1000
- 1 ≤ u, v (u != v) ≤ N
- Say maximum degree of a node among all the nodes of the tree be maxDeg.
- If (maxDeg <= 2) :
- 1 ≤ Sum of length of strings of set S ≤ 10010
- Else :
- 1 ≤ Sum of length of strings of set S ≤ 3010
Input: 2 4 4 b a b c 1 2 2 3 2 4 ac dbab af g 4 3 b a b c 1 2 2 3 2 4 pq rst uvwz Output: acbab -1
|Time Limit:||2.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.