Connection Status:
Competition Arena > RevengeOfTheSith

RevengeOfTheSith

SRM 678 · 2016-01-04 · by ltaravilse

SRM 678 · 2016-01-04 · by ltaravilse · Brute Force, Dynamic Programming
Class Name: RevengeOfTheSith
Return Type: int
Method Name: move
Arg Types: (vector<int>, int, int)
Problem Statement

Problem Statement

In order to become a Sith, Anakin Skywalker must descend a dangerous staircase and join his master who waits for him at the bottom. The staircase consists of the bottom floor, N-1 floating platforms, and the top floor. Hence, Anakin must make exactly N steps in order to get from the top to the bottom. (He must step on each platform exactly once.)

You are given a int[] steps that contains N elements: the height differences between consecutive platforms, from the bottom to the top.
That is, the bottom floor is currently at height 0, the first floating platform is at steps[0], the second floating platform is at steps[0]+steps[1], and so on, until at the end we get to the top floor which is at height sum(steps).
For example, if steps={2,3,5}, the floating platforms are currently at heights 2 and 5 (= 2+3), and the top floor is at height 10 (= 2+3+5).

Whenever Anakin descends a large distance in a single step, he gets hurt and loses some life.
More precisely, it works as follows:
If the height difference H between consecutive platforms is D or less, Anakin can take the step without any harm.
If the height difference H is more than D, Anakin will lose (H - D)^2 life points when he takes the step.


Before he starts his descent, Anakin can use the Force to shift at most T of the floating platforms.
There are some restrictions:
  • He is not allowed to shift the bottom floor or the top floor, only the floating platforms between them.
  • Each platform can only be shifted up or down.
  • Each platform can only be shifted by an integer distance.
  • At the end, after all the shifting, the entire staircase must still go upwards if you go from the bottom to the top. That is, if you list the heights of the bottom floor, all floating platforms in their original order, and then the top floor, you must still get a strictly increasing sequence of integers.
Also note that Anakin can only start his descent after he finishes moving all the platforms.

Continuing the above example, suppose that T=1.
If Anakin decides to shift the second floating platform (the one that is currently at height 5), he can shift it to one of the following heights: 3, 4, 6, 7, 8, or 9.
If he had T=2 in the same situation, he could also do many other things.
For example, he could shift the two platforms from heights 2 and 5 to heights 1 and 2, respectively.

You are given the int steps and the ints D and T as defined above.
Compute and return the smallest total number of life points Anakin will lose if he uses the Force wisely.

Constraints

  • steps will contain between 1 and 50 integers.
  • Each element of steps will be between 1 and 1000.
  • D will be between 1 and 1000.
  • T will be between 0 and N-1 where N is the number of elements of steps.
Examples
0)
{2,3,5}
1
1
Returns: 19

An optimal strategy is to move the second floating platform one unit higher. After the change, the floating platforms are at heights 2 and 6, and the top floor is still at height 10. Anakin's three steps downwards correspond to the distances 10-6 = 4, 6-2 = 4, and 2-0 = 2. The total amount of life points lost during the descent is (4-1)^2 + (4-1)^2 + (2-1)^2 = 19.

1)
{2,3,5}
2
1
Returns: 17

The same example as the previous one but now Anakin can move two platforms. One optimal strategy is to shift the two platforms to heights 3 and 7.

2)
{1,2,3,4,5,6}
1
2
Returns: 30

As you go up the stairs the difference between platforms increases.

3)
{1,1,1,1,1,1,1}
3
3
Returns: 0

There's no need to move any platform.

4)
{1,2,3}
2
2
Returns: 0

In this example Anakin needs to move both platforms one unit of distance higher than they are.

Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RevengeOfTheSith with a public method int move(vector<int> steps, int T, int D) · 53 test cases · 2 s / 256 MB per case

Submitting as anonymous