Assume you are given two strings an and b. You can apply the accompanying activity quite a few times: pick any adjacent substring of an or b, and sort the characters in it in non-dropping request. Let f(a,b) the base number of activities you need to apply to make them equivalent (or f(a,b)=1337 in case it is difficult to make an and b equivalent utilizing these tasks).
Correct answer will be upvoted else downvoted.
Assume you are given two strings an and b. You can apply the accompanying activity quite a few times: pick any adjacent substring of an or b, and sort the characters in it in non-dropping request. Let f(a,b) the base number of activities you need to apply to make them equivalent (or f(a,b)=1337 in case it is difficult to make an and b equivalent utilizing these tasks).
For instance:
f(ab,ab)=0;
f(ba,ab)=1 (in one activity, we can sort the entire first string);
f(ebcda,ecdba)=1 (in one activity, we can sort the substring of the subsequent string beginning from the 2-nd character and finishing with the 4-th character);
f(a,b)=1337.
You are given n strings s1,s2,… ,sk having equivalent length. Compute ∑i=1n∑j=i+1nf(si,sj).
Input :The principal line contains one integer n (1≤n≤2⋅105) — the number of strings. Then, at that point, n lines follow, each line contains one of the strings si, comprising of lowercase Latin letters. |s1|=|s2|=… =|sn|, and n⋅|s1|≤2⋅105. This load of strings are pairwise unmistakable.
Output :Print one integer: ∑i=1n∑j=i+1nf(si,sj).
Step by step
Solved in 3 steps with 1 images
