If we don't perfom swap on ceils $$$n$$$ and $$$n + 1$$$, then the answer is difference between number of inversions in a first half and a second half. If we perfom swap on ceils $$$n$$$ and $$$n + 1$$$ we can notice, that in an optimal solution we either will move some number of 1's from a second half to a first half either we will move some number of 1's from a first half to a second half and after we finish 1s movement, we also need to add difference between inversions in a first half and a second half.

So, the solution is as follows:

Fix the direction in which we will move 1's.
Move each 1 one by one, maintain number of inversions in a first and a second half.
Relax answer with difference between inversions + actions that we spent on 1's movement.

I'm not sure my solution counts as DP but I used memoization to recursively fill the DP.

My state was $$$dp[rightmost element][number of groups]$$$. I precomputed the cost for all subarrays in $$$O(N^3)$$$, then each transition is $$$O(N)$$$.

1. A valley is uniquely defined by the maximum height in the area. So you can enumerate possible valleys by fixing maximum height and finding the connected component that has heights all less or equal to it.

2. Now you have $$$O(n^2)$$$ candidate, but you want to see whether the component has a hole. However, you can count a number of "global" holes, because it's a number of connected components in 8 direction.

3. Preprocess the number of "global" holes, and let's try step 1 again. Maintain a disjoint set that contains each connected component, and the num of holes that each component has. If a component is merged, then basically all holes in each components are preserved. But, there is a "small" difference in the number of holes — that difference, could be traced because all the difference in "global" holes is attributed to that merges, thus the number is identical.

I solved it with Euler's formula, which stated that number of faces in a connected planar graph is equal to (# of edges) - (# of vertices) + 2.

I add cells into the graph one by one from the lowest to the hightest. For each connected component, it can be considered as a planner graph, with neighboring cells forming an edge, and each cell as a vertex.

I maintained # of edges and # of vertices in each connected component. These are easy to maintain.

I also maintained # of 2 by 2 squares in each component, because each of them forms a face when turning into graph, but that's not what we considered a "hole". When adding new cells, this could be updated by directly checking whether this cells forms a 2 by 2 square.

After updating each counter, I checked whether (# of edges) - (# of vertices) + 2 - (# of 2 by 2 squares) is equal to one (region outside the component is also considered a face). If not, then there must be a hole in it.

I did a weird dp: dp[r][b][s] = {min cost, #ways} , where r = row processed, b = whether hor edges in that row have been processed, and s = connectivity state, which represents how the nodes in the last row are related (ie 112211 means node in pos 0,1,4,5 are in one component and pos 2,3 are another). For k=6, there are only around 130 total connectivity states, and if you precompute the state transitions it runs pretty quickly.

Answer is MOD-48n-84(k-1).

I forget the problem. I can't access 2019US OPEN's problem on USACO now? Can you tell me what the problem is? Please.

I feel like it's going to be 750, as there was significant partials available and the difficulty wasn't too bad.

Wait so long. I forget the problem Gold 2. I can't access 2019US OPEN's problem on USACO now? Can you tell me what the problem is?

Results are finally out at http://usaco.org/index.php?page=open19results!