PROBLEM LINK:
Author and Editorialist: Lalit Kundu
Tester: Kamil Debowski
DIFFICULTY:
easy-medium
PREREQUISITES:
binary search, basic maths
PROBLEM:
Given two string S_1 and S_2, a flower is formed by putting strings perpendicular to each other in such a way that they overlap at the same character. A flower’s ugliness is sum of absolute difference of adjacent petal lengths i.e. i.e. if adjacent petal lengths are L_1, L_2$, L_3$, L_4, then ugliness of flower is |L_1 - L_2| + |L_2 - L_3| + |L_3 - L_4| + |L_4 - L_1|. You have to minimise this ugliness.
QUICK EXPLANATION:
======================
Iterate over 26 characters assuming i^{th} English alphabet is the overlapping character. Now, for fixed i, iterate over all positions j in S_1 and find the optimal position k in S_2 such that overlapping strings at positions i in S_1 and j in S_2 will minimise ugliness function. For a fixed j, the ugliness function can be expressed as |x - a_1| + |x - a_2| + |x - a_3| + |x - a_4|, where a_1, a_2, a_3, a_4 are constants dependent on lengths of S_1 and S_2 and j. Among all possible positions in S_2 for variable x, we need to evaluate those closest to a_1, a_2, a_3, a_4, which can be done via binary search.
EXPLANATION:
================
A very intuitive idea is to iterate over all characters of English alphabet assuming that strings will overlap at this character. Let’s denote by L_{1, i} as sorted list of all positions in S_1 where i^{th} English alphabet occurs. Similarly, by L_{2, i} as sorted list of all positions in S_2 where i^{th} English alphabet occurs.
Now, for all i(i.e. i = 1 to 26), we’ll iterate over j \in L_{1, i} assuming that overlap will occur at this position j in string S_1. Let’s say the overlap position is x in S_2, then what will be the ugliness? If you work it out, you’ll see it can be written as f(x) = |x - (l_2 - j -1)| + |x - (l_2 - l_1 + j)| + |x - (l_1 - j - 1)| + |x - j|, where l_1 and l_2 are lengths of S_1 and S_2, respectively. Let’s say it’s of form |x - a_1| + |x - a_2| + |x - a_3| + |x - a_4|.
Now, observe that this graph is discontinuous at points x = a_1, a_2, a_3, a_4 and its minima lies at one of these points. At all other values, this function is a straight line. We have to evaluate this function at all discrete values L_{2, i} and find its minimum value. If we iterate over this whole list, complexity of doing this will be O(l_2) worst case. We need to do something better. We know that minima occurs at one of a_1, a_2, a_3, a_4. For each k(from 1 to 4), we can find a_k in list L_{2,i} using binary search. If it doesn’t exist in the list, we look at points closest to it i.e. just greater and just smaller. We take minimum of all such cases.
Psuedo code to make things more clear:
int L[2][]
scan(s1, s2)
for i = 0 to l1
L[1][s1[i]].push_back(i)
for i = 0 to l2
L[2][s2[i]].push_back(i)
ans = INF
//asumming overlap is character i
for i = A to Z
//assuming j is the overlap position in S1
for j in L[1]
//the list of points where we need to test
a = [l_2 - j -1), (l_2 - l_1 + j), (l_1 - j - 1), j]
for k = 0 to 3:
//use binary search here
if a[k] is present in L[2][i]
//evaluate function f
ans = min(ans, f(a[k]))
else:
p = smallest element in L[2][i] greater than a[k]
q = largest element in L[2][i] less than a[k]
ans = min(ans, f(p), f(q))
print ans
COMPLEXITY:
================
Since we iterate over string S_1 and for each character apply binary search on list L_{1, i} for all i, total complexity is O(l_1 \text{log} l_2).
