### 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).