# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

Setter: Shivam Yadav

Tester: Anshu Garg

# DIFFICULTY:

EASY

# PREREQUISITES:

# PROBLEM:

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.

# EXPLANATION:

First, calculate the minimum cost to make titan i face East/West, for each i.

## How?

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 |
---|---|---|

East | 0 | \min(2*X,2*Y) |

West | \min(2*X,2*Y) | 0 |

North | \min(X,3*Y) | \min(3*X,Y) |

South | \min(3*X,Y) | \min(X,3*Y) |

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.

## How?

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!)

# TIME COMPLEXITY:

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:

# SOLUTIONS:

Editorialist’s solution can be found here

**Experimental:** For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters