Problem — [problem:2153D - 18] ↵
↵
My solution — [submission: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<int> 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 ↵
↵
My solution — [submission: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<int> 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 ↵
