STRSUM - EDITORIAL

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Lewin Gan
Tester: Lewin Gan and Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY:

Hard

PREREQUISITES:

Observation, Implementation.

PROBLEM:

Suppose we have an array S of N string. We make all possible pairs (i, j), i \neq j and make another list of strings, where for every pair (i,j) we insert S_i+S_j to this list. In the problem, we are given the second list and asked to find out the first list or determine if no such valid first list for given second list.

QUICK EXPLANATION

  • Let us sort the strings in the given list by length, and breaking ties using lexicographical order. (Other orderings might/might not work). The idea is, that now the shortest string of the valid S is either the prefix or suffix of the first string of the second set.
  • Assumed Strings of the first set are ordered first by length, and then by lexicographical order. Formally, |S_1| \leq |S_2| \ldots \leq S_N.
  • We try fixing all prefixes and all suffixes of the first string in the second set (up to half the length of string) as the smallest string. Fixing first string, we try to determine the remaining strings.
  • Now, when we find xth string, we remove all S_x+S_i and S_i+S_x from second list and now, the important thing to notice is that the first string shall either be S_1+S_{x+1} or S_{x+1}+S_1. Since we have fixed the first string, we can check if S_1 is prefix or suffix (can be both, but handled implicitly). After finding candidates for S_{x+1}, check if both S_1+S_{x+1} or S_{x+1}+S_1 are present in array.
  • If yes, we have found the next string, otherwise no valid first set exist.

EXPLANATION

While performing all steps of the following solution, if at any step we cannot perform the next step, the answer is impossible.

Let us order the strings in the array S by their lengths, and breaking ties by lexicographically smaller. It can be seen that the first string in the second list contains S_1 either as a prefix or as a suffix. So, we try all possible prefix and suffix of first string (up to half the length of the substring, since |S_1| \leq |S_2|) and check if this is the first string.

Suppose we have fixed the first string, which happens to be smallest in length. Now, Since the second string is smaller or equal in length than other strings, the first string present in T shall be either S_1+S_2 or S_2+S_1. So, we check for the first string of list T, if it contains S_1 as the prefix or as a suffix or as both. This way, we have found candidates for S_2. We can check if S_2 is valid, by checking the presence of both S_1+S_2 and S_2+S_1 in list T. If both of them are present, we have found S_2. Now, We shall remove S_1+S_2 and S_2+S_1 from list T.

Now, try to analyze the first string of list T after removing the above strings. It can be seen, that first string shall be either S_1+S_3 or S_3+S_1 (Due to smallest lengths). This leads us to find out String S_3.

The important thing here is that after we find string S_i, we should remove all combinations of S_i with already found strings. So, after removing those, all remaining strings say S_a+S_b shall have either a > i or b > i or both. String S_{i+1} has the smallest length out of those. So, There must be a string S_1+S_{i+1} present in T having the minimum length. So, this way, we can just find the smallest string now present in T and check if S_1 is prefix or suffix. We get the candidate for S_{i+1}.

Corner case: What if S_1 is both prefix and suffix of smallest string at any time?

We can consider both cases. If S_1 is the prefix, we can consider the remaining suffix as a candidate and if S_1 is a suffix, consider remaining prefix as a candidate.

For a candidate X to be a valid candidate, We can check the presence of both S_1+X and X+S_1 in T. If both of them are present, the current candidate is a valid choice for S_{i+1}.

This process can be repeated to find all strings in S. If at any point we do not find any valid candidate for next string, no possible set #S# exists.

Time Complexity

Time complexity is of order O(N^2*|sum(l_i)|*log(N)) where l_i is length of string.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile: