Help Utkarsh solution codechef

Help Utkarsh solution codechef

Utkarsh is a cool guy and had fun throughout the year. Now his exams are approaching and he hasn’t studied for them at all!

Utkarsh has to read several chapters for his exams, but he is smart and realized that he doesn’t actually need to read each and every one of them thoroughly. Several chapters share the same content, so he can skip some parts of some chapters to save time.

Each chapter is a non-empty string of lowercase characters. Utkarsh has to read NN distinct chapters for the exam, denoted by the set S={S1,S2,,SN}S={S1,S2,…,SN}. He will read all NN chapters in some order.

Help Utkarsh solution codechef

For each chapter SiSi, he can skip reading some part of it by considering at most two other chapters that he has read already.

Formally, he has 33 options for the chapter Si:Si:

  1. Suppose there exist two chapters Sj,SkSSj,Sk∈S (jj can be equal to kk) that he has previously read, and three (possibly empty) strings of lowercase alphabets AABB, and CC such that Si=A+Sj+B+Sk+CSi=A+Sj+B+Sk+C (where ++ denotes string concatenation). Then he has to read only |A|+|B|+|C||A|+|B|+|C| characters.

  2. Suppose there exists a chapter SjSSj∈S that he has previously read, along with two (possibly empty) strings AA and BB of lowercase alphabets such that Si=A+Sj+BSi=A+Sj+B. Then he has to read only |A|+|B||A|+|B| characters.

  3. Finally, he can also choose to read chapter SiSi completely, requiring |Si||Si| characters.

Note that there is no forced hierarchy among the options, i.e, Utkarsh is free to choose how he reads SiSi chapter among all choices available to him.

Find the minimum amount of characters Utkarsh has to read in total if he chooses an optimal ordering of the chapters.

Input Format

Help Utkarsh solution codechef

  • The first line of input contains a single integer TT, the number of test cases. The description of TT test cases follows.
  • Each test case consists of N+1N+1 lines.
  • The first line contains a single integer NN, the number of chapters.
  • Each of the following NN lines contains a non-empty lowercase string.

Output Format

Help Utkarsh solution codechef

For each test case, print a single line containing one integer denoting the minimum number of characters Utkarsh has to read over all chapters.

Constraints

  • 1T1031≤T≤103
  • 1N1051≤N≤105
  • 1|Si|31051≤|Si|≤3⋅105
  • Sum of |Si||Si| over all test cases doesn’t exceed 21062⋅106.

Sample Input 1

Help Utkarsh solution codechef

3
5
a
aba
aabc
bc
c
2
aaa
bb
3
z
zz
zzz

Sample Output 1 

5
5
1

Explanation

Help Utkarsh solution codechef

Test case 1:

Ukarsh reads the chapters in the following order :

  • aa (reads 11 character)
  • cc (reads 11 character)
  • aba=a+b+aaba=a+b+a (first and last aa already read, reads 11 character)
  • bc=b+cbc=b+c (cc already read, reads 11 character)
  • aabc=a+a+bcaabc=a+a+bc (first aa and bcbc already read, reads 11 character)

Thus, 55 characters are read in total.

Test case 2:

Ukarsh reads the chapters in the following order :

  • aaaaaa (reads 33 characters)
  • bbbb (reads 22 characters)

Thus 55 characters are read in total.

Test case 3:

Ukarsh reads the chapters in the following order :

  • zz (reads 11 character)
  • zz=z+zzz=z+z (first and last zz already read,reads 00 characters)
  • zzz=z+zzzzz=z+zz (zz and zzzz are already read,reads 00 characters)

Thus 11 character is read in total.

Leave a Comment

Your email address will not be published. Required fields are marked *