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