Need help on this problem

Revision en1, by skpro19, 2016-03-12 06:13:22

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 ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English skpro19 2016-03-12 06:13:22 967 Initial revision (published)