CHFSQN - Editorial

PROBLEM LINK:

Practice

Contest

Author: rahul_ojha_07

DIFFICULTY:
EASY

PREREQUISITES:
Simple Math

PROBLEM:
Given the Sequence a1, a2, …, an and Defining the strength of the sequence to be |a1 - a2| + |a2 - a3| + … + |an-1 - an| + |an - a1| find the maximum strength by rearranging the sequence.

QUICK EXPLANATION:
Sort the sequence then arrange it as an ,an ,a2 ,an-2… a(n/2),a(n/2)-1 this is the new sequence through which we can find the maximum strenth of the sequence.

EXPLANATION:

First, sort the numbers. Now, a1 < a2 < a3, … < an.

Then arrange the numbers like the following:

a1, an, a2, an-1, … a(n/2), a(n/2+1)

It should not be hard to see that this arrangement produces the optimal answer, as all of a1, a2, … an/2 are subtracted twice, while all of a(n/2)+1, … an are added twice. In addition, one nice property of the above sequence is that the elements of the constructed sequence alternate between increasing and decreasing. So, by calculating the strength by above sequence we can find the maximum possible strength

Author’s solution can be found here.

1 Like