Problem — 2153D - 18 - Not Alone

My solution — 343107994

Explanation of the solution ---------------------------

A nice array consists only of groups of equal consecutive elements (each group size ≥ 2). We can cover the array with blocks of length 2 or 3: - Cost to make 2 adjacent equal = |x − y| - Cost to make 3 adjacent equal = sum of distances to their median

Let dp[i] = minimum cost to make the first i elements nice (linear case): dp[i] = min( dp[i-2] + cost2(i-2), dp[i-3] + cost3(i-3) ) where cost2(i)=|a[i]-a[i+1]| and cost3(i) = total distance to median of 3 numbers. Because the array is circular, the last elements may connect to the first. We only need to test three rotations — starts at 0, n-1, and n-2 — since segments are length ≤ 3. Take the minimum DP result among them.

There is an efficient way of making this shift by making use of modulo as pasted below

vector starts; starts.push_back(0); if (n-1 != 0) starts.push_back(n-1); if (n-2 >= 0) starts.push_back(n-2);

for (int s : starts) {
    vector<ll> b(n);
    for (int i = 0; i < n; ++i) b[i] = a[(s + i) % n];
    ans = min(ans, solve_linear(b));
}

See the submission attached for the whole code