CF1535F String Distance

Suppose you are given two strings $ a $ and $ b $ . You can apply the following operation any number of times: choose any contiguous substring of $ a $ or $ b $ , and sort the characters in it in non-descending order. Let $ f(a, b) $ the minimum number of operations you have to apply in order to make them equal (or $ f(a, b) = 1337 $ if it is impossible to make $ a $ and $ b $ equal using these operations). For example: - $ f(\text{ab}, \text{ab}) = 0 $ ; - $ f(\text{ba}, \text{ab}) = 1 $ (in one operation, we can sort the whole first string); - $ f(\text{ebcda}, \text{ecdba}) = 1 $ (in one operation, we can sort the substring of the second string starting from the $ 2 $ -nd character and ending with the $ 4 $ -th character); - $ f(\text{a}, \text{b}) = 1337 $ . You are given $ n $ strings $ s_1, s_2, \dots, s_k $ having equal length. Calculate $ \sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j) $ .

N/A

N/A