Given N titans in a line, each facing either North, South, East or West. It costs X and Y energy to rotate any titan 90\degree clockwise and anticlockwise, respectively. Determine the minimum cost to rotate all titans such that, the first i titans face East and the remaining titans face West, for some optimal i.
First, calculate the minimum cost to make titan i face East/West, for each i.
A bit of case work is required here. For each of the 4 directions the titan may initially face, determine the minimum cost to make him face East/West.
The table of values is given below (deductions are trivial).
|Current direction||Min cost to face East||Min cost to face West|
Next, for each i, determine the minimum cost to make the first i titans face East. Also determine the minimum cost to make the last i titans face West.
Let minE_i represent the minimum cost to make titan i face East. Similarly, let minW_i represent the minimum cost to make titan i face West.
Then, calculate the prefix/suffix sums of array minE/minW.
Finally, for each valid i, the minimum cost to place Eren between titans i and i+1 is equal to: minimum cost to make first i titans face East + minimum cost to make last N-i titans face West.
The required answer is then the least cost over all i (don’t forget to calculate the cost when Eren is placed at the East/West end of the line!)
Determining the minimum cost to make each titan face East/West takes O(N). Calculating step 2 using prefix/suffix sums takes O(N). Calculating the answer requires iterating once over the N terms, so O(N).
The final complexity is therefore:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)