Editorial for DMOPC '18 Contest 5 P5 - A Hat Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
Each person has two choices, so there are possibilities. Trying each of these possibilities passes in time for subtask 1.
For the second subtask, let be the least unhappiness if person leaves without trading the next person. Say that they leave with the hat originally from person . For that hat to have travelled all the way there, person must have not traded with the next person and everyone from to must have. It is then easy to see that in this case,
The sum can be computed in with a prefix sum array.
For the final subtask, we analyze the from above. Splitting the absolute value into two cases yields the following:
Note that each sum can be split into a component that depends only on , and a component that depends only on . So we create two segment trees storing the component depending on . More precisely, we update each segment tree at index with value and . Then we can query the two segment trees to compute each value.