Question
Chain Power
Ram has an array of N strings, each made of only ‘x’ and ‘y’. He considers a permutation {p1, p2, ..., pN} of the first N natural numbers to form a string S = s[p1] + s[p2] + ... + s[pN], where s[i] denotes the ith string.
Identify a permutation that maximizes S’s strength, defined as the count of ‘xy’ subsequences, or the number of pairs (i, j) where i < j, S[i] = ‘x’, and S[j] = ‘y’.
Input
The first line of the input contains a single integer N, the size of the array.
The next N lines contain the strings s[1], s[2],. s[N].
The next N lines contain the strings s[1], s[2],. s[N].
Output
Print the maximum possible strength of the string.
Example
Sample Input
4
xxy
yx
x
yyyx
Sample Output
18
Explanation
For N = 4 strings ["xxy", "yx", "x", "yyyx"], maximize 'xy' subsequences by permuting them. Count x's and y's: s[1]=(2x,1y, diff=1), s[2]=(1x,1y, diff=0), s[3]=(1x,0y, diff=1), s[4]=(1x,3y, diff=-2). Sort by diff descending: permutation [1, 3, 2, 4] gives S = "xxy" + "x" + "yx" + "yyyx". 'xy' pairs: (s[1], s[2]): 2.1=2, (s[1], s[4]): 2.3 = 6, (s[3], s[2]): 1.1 = 1, (s[3], s[4]): 1.3 = 3, (s[2],s[4]): 1.3 = 3. Total = 2 + 6 + 1 + 3 + 3 = 18.
4
xxy
yx
x
yyyx
Sample Output
18
Explanation
For N = 4 strings ["xxy", "yx", "x", "yyyx"], maximize 'xy' subsequences by permuting them. Count x's and y's: s[1]=(2x,1y, diff=1), s[2]=(1x,1y, diff=0), s[3]=(1x,0y, diff=1), s[4]=(1x,3y, diff=-2). Sort by diff descending: permutation [1, 3, 2, 4] gives S = "xxy" + "x" + "yx" + "yyyx". 'xy' pairs: (s[1], s[2]): 2.1=2, (s[1], s[4]): 2.3 = 6, (s[3], s[2]): 1.1 = 1, (s[3], s[4]): 1.3 = 3, (s[2],s[4]): 1.3 = 3. Total = 2 + 6 + 1 + 3 + 3 = 18.