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.
It's abc163_e.
Thanks a lot
I believe there is a greedy solution here that works in $$$O(n \log n)$$$ time
Strategy : 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 proof
Suppose $$$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 $$$k<i$$$ and $$$r+i-2k$$$ if $$$i<k<r$$$ and $$$i-r$$$ if $$$k>r$$$
For $$$k<i$$$ we get $$$h_k(r-i)+h_j(r-i)\geq0$$$
For $$$i<k<r$$$ we get $$$h_k(i+r-2k)+h_j(r-i) > 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 described
Hope 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