SET OF STRINGS
All submissions for this problem are available.
Naman and Pratik are playing a game as follows. Initially Naman has a set of strings S1 of size N1 and Pratik has a set S2 of size N2. Now they play alternatively and select a string from their respective sets and insert it into a set S if it satisfies the following conditions –
- If Naman has selected a string from set ,S1 to insert into set S then LCS(Longest Common Subsequence of this string with all the strings in set S, taken individually, which have been inserted by Pratik should be at most K.
- If Pratik has selected a string from set S2 to insert into set S then LCS of this string with all the strings in set S, taken individually, which have been inserted by Naman should be at most K.
- In all other cases, the selected string can’t be inserted into the set S.
Since Naman and Pratik are best friends they aren’t playing against each other and decide to play this game optimally to maximize the size of set S.
Note that if one player runs out of strings to select the other keeps on playing until he has finished all his strings.
Your job is to find the maximum size of set S that Naman and Pratik can achieve and print it.
- 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 three integers N1,N2and Kas given in the problem statement .
- Next N1 lines contain one string each which denote the strings belonging to set S1.
- Next N2 lines contain one string each which denote the strings belonging to set S2
Print a single integer for each test case on a new line which is the answer to the given problem.
- 1 ≤ T ≤ 10
- 1 ≤ N1 ,N2≤ 250
- 1 ≤ K ≤ 50
- 1 ≤ size of string in S1 and S2 ≤ 50
Sum of N1 and N2 over all test cases doesn't exceed 500.
3 3 1
|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, CLOJ, COB, FS|
Fetching successful submissions