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.

Authors: r3mark

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}| + \ldots + |v_i - w_{i-1}| + |v_j - w_i|.

The sum |v_{j+1} - w_j| + |v_{j+2} - w_{j+1}| + \ldots + |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) &\ \  v_j \ge w_i \\ (prefix[i] + w_i) + (dp[j-1] - prefix[j] - v_j) &\ \  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)


Comments

There are no comments at the moment.