Decidophobia

I originally thought of this as potentially a dynamic programming problem — but DP usually wants an ordering, and there is no natural ordering here, because of the cyclical nature of the problem (the candidates literally sit in a circle around a table).

(We will be using this observation almost as a given from here on.)

In a way, our problem is a max-cut problem on the circle-window graph. However, Max Cut is NP-hard in general (I believe), so this can't work as-is for a linear-time target — but specialized graphs often admit cleaner solutions, and the min-cut problem (non-negative weights, minimize) is polynomial via the max-flow min-cut theorem. So I started wondering: can I solve this with a max-flow algorithm on this graph, or some modified variant? The graph is also highly symmetric, since each node's neighbors are just the interval $[i-D, i+D]$ around it.

Three candidate algorithms came out of this:

1. Greedy. Start with nobody gifted. Repeatedly pick a person and gift them if that increases the total; otherwise leave them ungifted.
2. Augmenting path. Start with nobody gifted. When gifting person $i$ hurts because some ungifted neighbor $j$ contributes a large negative, try gifting $j$ too; or if some gifted neighbor's contribution just dropped to zero, try un-gifting them — a BFS-like search for a chain of flips that collectively improves the score, like the augmenting step in max-flow.
3. Greedy sweep, largest first. Gift people in decreasing order of $A[i]$, as long as each addition doesn't decrease the score.

The first is just a greedy simplification of the second, and given the symmetry of the problem it felt like a simpler variant should work here; the third exploits the symmetry a bit more.

          1
        /   \
       6     4        gifted:   {4, 5, 6}
       |     |        ungifted: {1, 2}
       2 --- 5
 
pairs:  4-1 = 3,  5-2 = 3,  6-2 = 4,  6-1 = 5     total = 15

There's a Key Question hiding in here that I should have asked myself — "under what conditions does gifting a person actually increase the score versus decrease it?" — but I did not, and kept poking at examples instead.

I spent most of my time exploring variants of the three algorithms above. Ironically (spoiler alert), it turns out that the greedy algorithm actually does work here, but I wasn't able to prove it by now. I kept flip-flopping between the greedy and the augmenting-path framing, trying to understand what could work. More or less got stuck.

What kept getting me: the relationship between gifting some person $i$ and un-gifting some person $j$ seemed complicated, because the neighborhoods all overlap with no obvious starting point. I kept playing with the $A[i] - A[j]$ versus $A[j] - A[i]$ relationships and it was stumping me.

In Idea 1, through a variety of framings, we arrived at some kind of greedy algorithm (gift a person if it increases the score) or an augmenting-path variant (gift some, un-gift others) — with not much luck making either into a working solution. Here are some observations made along the way:

This was good — it started to imply even more of a greedy structure.

Overall though, intuitively, it felt like there was symmetry in the constraints waiting to be exploited. It all hinged on when we should greedily gift an element versus not, based on the configuration of its neighbors — and I didn't have a good answer for that.

After struggling with this long enough, I finally asked myself the Key Question...

Consider person $i$: say they have $m$ gifted neighbors with weights $X_1, \ldots, X_m$, and $k$ ungifted neighbors with weights $Y_1, \ldots, Y_k$. Using Key Observation 1, the total contribution of all pairs involving $i$:

If $i$ is ungifted, each gifted neighbor forms a pair with $i$:

If $i$ is gifted, each ungifted neighbor forms a pair with $i$:

It's better to gift $i$ iff $\text{Contribution}_{\text{gifted}} > \text{Contribution}_{\text{ungifted}}$, so we literally just write it out:

Miraculously, this simplified with $A[i]$ alone on one side. And the really cool part: $\sum X_j + \sum Y_j$ is just the sum over all neighbors of $i$ — gifted or not — and $m + k = 2D$ is the total number of neighbors. The gifted/ungifted split canceled out entirely.

This all follows from writing out the formula explicitly and simplifying. It yields a pretty nice algorithm:

Given n, A[1..n], and D
 
# pick the optimal set using the greedy rule
for each person i:
    sum_of_neighbors = sum of A[j] over the 2D neighbors j of i
                       (wrap around the circle; exclude i itself)
    if A[i] >= sum_of_neighbors / (2D):  gift person i
 
# compute the answer with the original formula
answer = 0
for each person i:
    if i gifted:  answer += A[i] * (ungifted neighbors of i)
    else:         answer -= A[i] * (gifted neighbors of i)

At this point we're effectively done, and it's a matter of implementing this in $O(n)$, using two relatively standard techniques:

So here is the final algorithm with all the details:

Given n, A[1..n], and D
X[i] := 1 iff person i is gifted;  X[1..n] = 0
 
triple A for wrap-around:  A[1..3n] = A + A + A
prefix sums:               S[i] = S[i-1] + A[i]   for i = 1..3n
 
for each person i (using tripled index i+n):
    # the window [i+n-D, i+n+D] covers 2D+1 people INCLUDING i — subtract i
    sum_of_neighbors = S[i+n+D] - S[i+n-D-1] - A[i+n]
    if A[i] >= sum_of_neighbors / (2D):  X[i] = 1
 
triple X for wrap-around:  X[1..3n] = X + X + X
prefix counts:             cnt[i] = cnt[i-1] + X[i]  for i = 1..3n
 
answer = 0
for each person i (using tripled index i+n):
    gifted_neighbors = cnt[i+n+D] - cnt[i+n-D-1] - X[i+n]   # exclude i again
    ungifted_neighbors = 2D - gifted_neighbors
    if X[i]:  answer += A[i] * ungifted_neighbors
    else:     answer -= A[i] * gifted_neighbors
 
print answer

Tada!

At this point we have a correct solution, but Key Observation 2 did not sit well with me. Why? Because it didn't seem intuitive — and still doesn't quite — that a person must be gifted iff their weight exceeds the average of all their neighbors. It seemed to just miraculously pop out of the algebra, which I didn't fully understand beyond "it just works." But... why? Can we think this through to a more intuitive understanding — one I could have reached faster?

Therefore the total change from gifting person $i$ is:

which is positive iff

— exactly the condition we derived earlier. It's effectively the same formula, but now we can see the core of why it works. It feels more like an "aha!" to me: gifting $i$ always adds $A[i] - A[j]$ across all neighbors $j$, so if $A[i]$ beats the neighbor average, the sum of those terms is positive — independent of everyone else's gifts.

And here we are. I think we're done.