UGLYF - Editorial

PROBLEM LINK:

Practice
Contest

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

AUTHOR’S, TESTER’S SOLUTIONS:

setter
tester

1 Like

Can anyone tell me where the below solution is going wrong?

https://www.codechef.com/viewsolution/11938982

Can be done without binary search. Complexity will be O(n).
Solution can be referred here :slight_smile:

1 Like

please explain your approach, since reading code seems cumbersome.

The observation here was to try matching same characters in both strings, which are more closer to middle position of their respective strings.

2 Likes

I did it with a complexity of O(max(len1,len2)). And yes it can be done simply without Binary Search.
Here is a link to my solution : https://www.codechef.com/viewsolution/11934832
I kept an array of size 26 and there I stored the location (nearest to the middle of string) of the letter. Then I ran a loop for all 26 letters to check for the minimum value.

7 Likes

It can be done in O(n) … we just have to take that value for each character whose abs(no of character from left-no of character form right ) is minimum and calculate the answer by runnig a loop of 26 .
Here’s my solution https://www.codechef.com/viewsolution/11936792

Please, if any one can help me out, where i am getting wrong…i can expect TLE but its giving WA…please help https://www.codechef.com/viewsolution/11938831

1 Like

@rohit_0801 yeah it seems right

1 Like

my solution in O(n) without binary search
https://www.codechef.com/viewsolution/11933610

Another easy way without binary search is, traverse the s2 string and for all alphabets in it, find the same alphabet in string s1 closest to the mid(length of s1/2) and compute the minimum value for all the matched characters in string s1 and s2.
Here refer to my solution - Solution

@more_practice
You would be very happy after cheating and copying my original code ? won’t you?
I have one advice for you that never copy anyone else’ code because you will never learn anything from it and will always remain a noob.

1 Like

@kay_kay Check your vector clearing phase,you have written .empty() instead of .clear() .

Can anyone point out my mistake, it’s giving WA… i checked many test cases
https://ideone.com/lYEZSD

@rohit_0801 @aayushkapadia

//