Each person has two choices, so there are ~2^N~ possibilities. Trying each of these ~2^N~ possibilities passes in time for subtask 1.

Time Complexity: ~\mathcal{O}(N\cdot 2^N)~

For the second subtask, let ~dp[i]~ be the least unhappiness if person ~i~ leaves without trading the next person. Say that they leave with the hat originally from person ~j~. For that hat to have travelled all the way there, person ~j-1~ must have not traded with the next person and everyone from ~j~ to ~i-1~ must have. It is then easy to see that in this case, $$\displaystyle dp[i] = dp[j-1] + |v_{j+1} - w_j| + |v_{j+2} - w_{j+1}| + \dots + |v_i - w_{i-1}| + |v_j - w_i|.$$

The sum ~|v_{j+1} - w_j| + |v_{j+2} - w_{j+1}| + \dots + |v_i - w_{i-1}|~ can be computed in ~\mathcal{O}(1)~ with a prefix sum array.

Time Complexity: ~\mathcal{O}(N^2)~

For the final subtask, we analyze the ~dp~ from above. Splitting the absolute value into two cases yields the following:

$$\displaystyle dp[i] = \min_{j \le i} \begin{cases} (prefix[i] - w_i) + (dp[j-1] - prefix[j] + v_j) & \text{if }v_j \ge w_i \\ (prefix[i] + w_i) + (dp[j-1] - prefix[j] - v_j) & \text{if }v_j < w_i \end{cases}$$

Note that each sum can be split into a component that depends only on ~i~, and a component that depends only on ~j~. So we create two segment trees storing the component depending on ~j~. More precisely, we update each segment tree at index ~v_j~ with value ~dp[j-1]-prefix[j] + v_j~ and ~dp[j-1]-prefix[j] - v_j~. Then we can query the two segment trees to compute each ~dp~ value.

Time Complexity: ~\mathcal{O}(N\log N)~