Here is my proposed algorithm: subject to flaws major and minor:
We make a few random observations that I'm not too sure where they appear in the solution, but let's just list them down first:
1) Total drag = summation x(x-1)/2, where x is the number of flags at each height.
1.1) It doesn't matter what order the flagpoles are arranged in.
2) There exists an optimal solution where the number of flags in each height is non-decreasing as the height gets lower.
Proof: Consider an optimal solution (if it exists) where two consecutive heights are such that the higher height has more flags, then the flags can be shifted down (by Pigeonhole Principle or something, because on the same pole there will exist space for the flags to move down)
3) The objective is to try to spread flags out as far as possible.
"Proof": 3+5>4+4 (by 1 Newton of drag), since well, can't be bothered to explain this.
4) Assuming a/b>c/d, a,b>c,d>0,0 (improvised notation ftw), then (a-c)/(b-d)>c/d.
Proposed Solution Part 1: Definitions
-------------------------------------
Define the highest level of the highest flagpole to have height 1, the second highest level to be 2 and so on, until n.
Define g(i) to be the maximum number of flags you can fly at equal to or higher than the level i.
Define f(j,k)= |g(j)-g(k)/(k-j)| (modulus function ftw).
Proposed Solution Part 2: Calculating g(i)
------------------------------------------
Raise all flags to the maximum. The number of flags at or above height i is now g(i).
To calculate all g(i) in O(N) time, we let the flags at each flagpole by represented by a range (after being raised to the maximum).
The sum of the total length of all parts of all ranges above i is then g(i).
Hence, at the start of each range, we add 1 to an array, and minus 1 after the end of each range. (ie a[0]=0, a[1]=a[0]+number of ranges starting at 1 - number of ranges ending at 0)
g(i) is then the sum of a[0]+a[1]+...+a[i] (or something like that).
Proposed Solution Part 3: The Idea
----------------------------------
Since we wish to spread out the flags among heights evenly, we will try to see whether we can do this 100% efficient. As it turns out, we cannot, because the higher levels will not fit as many flags.
So, we will probably wish to stuff as many flags into the higher levels as possible before moving on to the lower levels.
Say for the highest 6 levels we can fit 5, 14, 14, 16, 17, 18 flags respectively. Then clearly the most optimal solution involves putting 3 flags in each level (assuming there are a lot of flags past the 6th level).
After that, we realise we have reduced the problem, but the condition "(assuming there are a lot of flags past the 6th level)" is a bit iffy, so let's formalise it.
If g(k)/k is minimal among all k from 1 to n, then:
1. The heights above k can have either floor(g(k)/k) or ceiling (g(k)/k) flags.
2. That is the most optimal way of arranging the flags.
Hence, if we can find the minimal g(i)/i, we can reduce the problem.
Proposed Solution Part 4: The Problem
-------------------------------------
If the i that minimises g(i)/i is say, 1, then the reduced problem will have different g(i)/i, since the maximal number of flags above a certain level j in the reduced problem is actually equivalent to |f(i,j)*(i-j)| (stupid definitions). Or I think I should say, f(i,j) is not equal to f(0,j). Yep. That makes more sense. Hence the next minimal f(i,j) might not be the minimal f(0,j). Which means that we have to recalculate everything, which is a lot too slow (O(n^2)).
Proposed Solution Part 5: The Win
---------------------------------
We shall pretend we are stupid (slightly) to solve the problem.
At each height, if f(i, i+1) is more than the previous minimum f(a,i), then we plonk it into a list of minimums. (Like, if say g(3)/3 is the true minimum value of g(i)/i, then f(3,4) may be the minimum value of f(3,i)
If f(i, i+1) is less than the previous minimum f(a,i), then it must be true (by Observation 4) that f(a,i+1)
After this mess, we now know the minimum g(i)/i. We also know the minimum g(i)/i in the reduced problem, the doubly-reduced problem and so on. Hence, we can calculate the minimum drag the flags add to the ship.
