### 650iq's blog

By 650iq, history, 6 months ago,

There are N towers arranged in a single line. You want to rearrange all the towers.

Given an array H of size N, where Hi denotes the height of tower i. You can rearrange this array in whatever way you like.

Beauty is defined as follows:

If j is the position of the tower i in the final arrangement, you add Hi*abs(i-j) to the Beauty.

Your task is to find the maximum Beauty you can achieve, after rearranging the towers.

I could only come with bitmask dp solution but here N is 10^3 so it won't work.

• 0

 » 6 months ago, # | ← Rev. 4 →   0 It's abc163_e. There is an editorial in English. However, note that the problem may be quite hard for you (it's rated $2037$ on AtCoder).
•  » » 6 months ago, # ^ |   0 Thanks a lot
 » 6 months ago, # | ← Rev. 2 →   0 I believe there is a greedy solution here that works in $O(n \log n)$ timeStrategy : You sort the towers with height and take the highest tower and put it at the most corner point possible, and you repeat.Ex: [5, 3, 1, 2, 7] --> [7, 2, 1, 3, 5] (greedy solution)Explanation : put 7 at the other corner, put 5 at opposite corner, put 3 at next opposite corner, put 2 at next opposite corner. Finally last element stays at its place. (only place possible for 1 is its initial position)Proof: I'll sketch the basic idea of the proofSuppose $O$ is optimal arrangement of towers and suppose there is an inversion i.e. there exist pairs $(h_j, h_k)$ such that $h_j$ is placed at $r$ and $h_k$ is placed at $i$ with $h_j>h_k$ and $h_j$ is farther from $i$ than $r$.Swap these two towers, change in score = (new-score)$(h_k \times |k-r| + h_j \times |j-i|)-$ (old-score)$(h_k \times |i-k| + h_j \times |j-r|)$ = $h_k(|k-r|-|i-k|)+h_j(|j-i|-|j-r|)$Assume WLOG $i < r$ and so $i < r< j$.Now $|k-r|-|i-k| = r-i$ if $kr$For $k h_k(i-r)+h_j(r-i) = (h_j-h_k)(r-i)\geq 0$For $k>r$ we get $h_k(i-r) + h_j(r-i) = (h_j-h_k)(r-i)\geq 0$ Thus, we can improve our score using these swaps and our optimal solution can be converted to greedy solution produced by the algorithm describedHope this was helpful!PS: I realised it is lot more subtle than that, you need to identify the correct corner to push large towers to