I was solving this problem -> Problem C
I went through the tutorial which says this ->
The problem was suggested by Lewin Gan lewin. The proof of the transitivity also belongs to him. Let's sort all the strings by comparator a + b < b + a and concatenate them. Let's prove that it's the optimal answer. Let that operator be transitive (so if ). Consider an optimal answer with two strings in reverse order by that operator. Because of the transitivity of operator we can assume that pair of strings are neighbouring. But then we can swap them and get the better answer. Let's prove the transitivity of operator. Consider the strings as the 26-base numbers. Then the relation a + b < b + a equivalent to . The last is simply the relation between real numbers. So we proved the transitivity of the relation a + b < b + a.
I couldn't understand a word of it. Can anyone please help ?
Think about the original number sorting problem. Take bubble sort for example. When there is a pair of a,b such that a>b and a's position < b's position , we swap them. This works beacause of the transitivity of operator < .
We want to find a proper way to define the < operator in this problem so that we can make the sorting algorithm work again. What the tutorial tells is the way to define it and how to prove it.
In short , more intuitively , if your answer is ABC but you find CA < AC, swap them would be better.
when we are using cmp functions like
bool cmp(string a, string b){
return a > b;
}
Here. we are comparing one element with another and hence, deciding their relative order. But in the above com function, we are using
bool cmp(string a , string b) {
return a + b > b + a ;
}
How is this exactly working ? can you please explain with an example please. I am not able to understand the underlying working. Thank you
the comp function is used to determinate how you want to sort the elements, let's say we have an array of integers:
2 -6 -3 4 -1
the default comp function is something like: bool comp(int a,int b){return a<b;}
so the sorted array is : -6 -3 -1 2 4
however, you can change the comp operator, let's say you want to sort the elements by their increasing absolute value, you write comp like:
bool comp(int a,int b){return abs(a)<abs(b);}
so the sorted array is : -1 2 -3 4 -6
hope this helped :)