An initial observation is that the final happiness of a resident depends only on whether the resident's final position differs from their initial position by an odd or an even displacement. Therefore, the only important information to describe a state is a permutation representing where the residents end up. We can rephrase the problem as finding a permutation $p_1,\dots ,p_N$ with the smallest number of inversions such that the array $h_i^{\prime }:=(-1{)}^{|i-p_i|}{h}_{p_i}$ for $1\le i\le N$ is nondecreasing.

We will present the solution to subtasks 5 and 6 first as it helps put all the subtasks into a bigger picture.

Subtasks 5 and 6

Consider the element with the largest $|h_i|$, say at index $j$. We must move $h_j$ to either index $1$ or $N$, and it is possible that only one or none of these indices result in $h_j$ having the correct sign in the end. After doing so, we can effectively ignore $h_j$ and continue this reasoning recursively on the remaining elements, except for the fact that where $h_j$ ends up might affect the parity of the final indices of the remaining residents.

This suggests using dynamic programming with a state of the form $dp[k][b]$, representing the minimum number of swaps to put all the $k$ largest $|h_i|$s at an endpoint of the line and with the correct sign, where the number of residents assigned to the left end is $\equiv b(\mathrm{mod}2)$. Note that it suffices to consider greedily making swaps to move the residents into an endpoint in decreasing order of $|h_i|$, as every inversion gets accounted for exactly once this way. Let $l_k$ be the number of residents left of the $k$th largest $|h_i|$ with a higher $|h_i|$ and $r_k$ be the number of residents right of the $k$th largest $|h_i|$ and with a higher $|h_i|$. The transitions are of the form $dp[k][b]+l_k\to dp[k+1][b\oplus 1]$ and $dp[k][b]+r_k\to dp[k+1][b]$, both only considered if the sign is correct. This dynamic programming can be performed in linear time after precalculating $l_k$ and $r_k$.

Finding $l_k$ and $r_k$ naively takes $\mathcal{O}(N^2)$ time, which solves subtask 5, and a binary indexed tree similar to inversion counting can be used to find $l_k$ and $r_k$ in $\mathcal{O}(N\log N)$ time, solving subtask 6.

Interlude

The path to the full solution is more clear after solving subtasks 5 and/or 6. We will still use dynamic programming with a similar state, except we need to consider all the residents with the same $|h_i|$ simultaneously, finding the minimum number of inversions incurred to move all of them to an endpoint while fixing the parity of how many residents are moved towards the left endpoint.

A solution to subtasks 3 and/or 4 will integrate nicely into a full solution, as we can view residents with the same $|h_i|$ as $\pm 1$ and residents with smaller $|h_i|$ in between them as $0$. Subtasks 1 and 2 are easier versions of this task where $0$s are not allowed.

Subtasks 1 and 2

Many different perspectives may lead to a solution, some of which are more obviously correct than others. One of the most direct perspectives (working with the original $h_i$s) can lead to a solution resembling greedy bracket matching. We will present a different perspective that leads more easily to a subtask 3 and 4 solution.

Consider flipping the sign of every other $h_i$. After this transformation, the swaps become normal swaps that do not flip any signs. There are $N+1$ candidates for the final configuration of $h_i$s. For each final configuration, focus on the set of indices where $h_i=1$ in the initial and final states, say $a$ and $b$. If these sets do not have the same number of elements, then this configuration is unreachable. Otherwise, a swap is equivalent to "shifting" an index by $1$ to the left or right, and it follows that the answer is $|a_1-b_1|+|a_2-b_2|+\dots$.

For subtask 1, it suffices to implement the above idea naively in $\mathcal{O}(N^2)$ time. For subtask 2, note that only one value of $b_i$ changes each time as we sweep through the possible final configurations, so a running sum can be maintained to solve the problem in $\mathcal{O}(N)$ time. It may be necessary to consider some cases on whether the number of $1$s in the initial state (after flipping every other $h_i$) is one more or less than $N/2$.

Subtasks 3 and 4

Like in subtasks 1 and 2, we begin by flipping the sign of every other $h_i$. There are $N+1-z$ candidates for the final configuration, where $z$ is the number of $0$s among $h_i$.

For subtask 3, we may consider all these candidates independently. For each configuration, we need to solve the following problem:

Given two length $N$ arrays of elements in $\{-1,0,1\}$, find the minimum number of swaps required to transform one array into the other.

This problem can be modelled using inversion counting: In both arrays, label the $-1$s with $1,2,\dots ,x$ from left to right for some $x$, the $0$s with $x+1,\dots ,y$ for some $y$, and the $1$s with $y+1,\dots ,N$. The answer is the number of inversions between these two permutations. Finding the number of inversions can be done in $\mathcal{O}(N\log N)$ time using a BIT, for a total time complexity of $\mathcal{O}(N^2\log N)$ (since there are only $3$ distinct elements in the arrays, it is also possible to do this in $\mathcal{O}(N^2)$ total).

For subtask 4, note that only a few elements change their inversion count each time as we sweep through the possible final configurations, so we can maintain a running sum instead to solve the problem in $\mathcal{O}(N\log N)$ or $\mathcal{O}(N)$ time. Similar to subtask 2, it may be necessary to consider some cases on whether $z$ is odd and whether the number of $1$s in the initial state is one more or less than $(N-z)/2$.

Subtasks 7 and 8

To solve subtasks 7 and 8, we can combine the solution for subtasks 3 and 4 with the dynamic programming of subtasks 5 and 6.