650iq's blog

By 650iq, history, 6 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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