Editorial for DMOPC '18 Contest 5 P5 - A Hat Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: r3mark

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

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

For the second subtask, let $dp[i]$ $d p [i]$ be the least unhappiness if person $i$ $i$ leaves without trading the next person. Say that they leave with the hat originally from person $j$ $j$ . For that hat to have travelled all the way there, person $j-1$ $j - 1$ must have not traded with the next person and everyone from $j$ $j$ to $i-1$ $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|.$ $d p [i] = d p [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}|$ $| v_{j + 1} - w_{j} | + | v_{j + 2} - w_{j + 1} | + \dots + | v_{i} - w_{i - 1} |$ can be computed in $\mathcal{O}(1)$ $O (1)$ with a prefix sum array.

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

For the final subtask, we analyze the $dp$ $d p$ 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}$ $d p [i] = min_{j \leq i} {\begin{cases} (p r e f i x [i] - w_{i}) + (d p [j - 1] - p r e f i x [j] + v_{j}) & if v_{j} \geq w_{i} \\ (p r e f i x [i] + w_{i}) + (d p [j - 1] - p r e f i x [j] - v_{j}) & if v_{j} < w_{i} \end{cases}$

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

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

Comments

There are no comments at the moment.