Statistics

Problem Statement for "RevengeOfTheSith"

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.

Definition

Class:
RevengeOfTheSith
Method:
move
Parameters:
int[], int, int
Returns:
int
Method signature:
int move(int[] steps, int T, int D)
(be sure your method is public)

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

  1. {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.

  2. {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.

  3. {1,2,3,4,5,6}

    1

    2

    Returns: 30

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

  4. {1,1,1,1,1,1,1}

    3

    3

    Returns: 0

    There's no need to move any platform.

  5. {1,2,3}

    2

    2

    Returns: 0

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

  6. {87,78,16,94}

    2

    36

    Returns: 4735

  7. {50,22,63,28,91,60,64,27,41,27,73,37,12}

    3

    69

    Returns: 0

  8. {83,31,63,24,68,36,30,3,23,59}

    7

    70

    Returns: 0

  9. {57,12,43,30,74,22,20,85,38,99,25,16,71,14}

    7

    27

    Returns: 4088

  10. {57}

    0

    74

    Returns: 0

  11. {97,82,6,26,85,28,37,6,47,30,14}

    0

    58

    Returns: 2826

  12. {83,46,15,68,35,65,44,51,88,9,77,79,89,85,4,52}

    15

    55

    Returns: 10

  13. {61,77,69,40,13,27,87,95,40,96,71,35,79}

    9

    68

    Returns: 0

  14. {3,18,93,53,57,2,81,87,42,66,90,45,20,41,30,32,18,98}

    3

    72

    Returns: 306

  15. {10,28,68,57,98,54,87,66,7,84,20,25,29,72,33,30}

    3

    4

    Returns: 37970

  16. {69,9,16,41,50,97,24,19,46,47,52}

    4

    22

    Returns: 5334

  17. {89,65,29,42,51,94,1,35,65,25,15,88,57,44,92,28,66,60,37,33}

    17

    52

    Returns: 0

  18. {76,8,75,22,59,96,30,38,36}

    5

    94

    Returns: 0

  19. {44,12,29,30,77,5,44,64,14}

    5

    39

    Returns: 0

  20. {70,18,18,97,25,44,71,84,91}

    1

    100

    Returns: 0

  21. {45,91,6,40,55,87}

    2

    70

    Returns: 2

  22. {65,98,8}

    1

    56

    Returns: 81

  23. {100}

    0

    20

    Returns: 6400

  24. {12,23,29,100,44,47,69,41,23}

    1

    12

    Returns: 12094

  25. {2,62,31,79,6,21}

    4

    37

    Returns: 0

  26. {23,66,9,17,83,59,25,38,63,25,1,37,53,100,80,51,69,72,74,32,82,31,34,95,61,64,100}

    11

    82

    Returns: 0

  27. {60,74,14,69,91,96,27,67,85,41,91,85,77,43,37,8,46,57,80,19,88,13,49,73,60,10,37,11,43,88,7,2,14,73,22,56,20,100,22,5,40,12,41,68,6,29,28}

    40

    51

    Returns: 0

  28. {21,25,23,70,97,82,31,85,93}

    8

    73

    Returns: 0

  29. {41,43,99,14,99,91,25,91,10,82,20,37,33,56,95,5,80,70,74,77,51,56,61,43,80,85,94,6,22,68,5,14,62,55,27,60,45,3,3,7,85,22,43,69,29,90,73,9,59,99}

    8

    37

    Returns: 28924

  30. {54,49,4,34,34,49,91,55,68,47,69,30,1,47,89,98,50,91,4,34,64,98,54,93,87,26,53,97,76,89,58,30,37,61,15,22,61,5,29,28,51,49,57,3,95,98,100,44,40,3}

    3

    29

    Returns: 58076

  31. {1,82,48,39,60,52,36,35,40,93,16,28,5,30,50,65,86,30,44,36,78,1,39,72,50,90,68,89,93,96,44,45,30,91,83,41,42,70,27,33,62,43,61,18,24,62,82,10,91,26}

    17

    97

    Returns: 0

  32. {78,35,91,27,25,58,15,69,6,59,13,87,1,47,27,95,17,53,79,30,47,91,48,71,52,81,32,94,58,28,13,87,15,56,13,91,13,80,11,70,90,75,56,42,21,34,88,89,39,67}

    34

    71

    Returns: 0

  33. {57,18,7,61,50,38,6,60,18,19,46,84,74,59,74,38,90,84,8,79,58,15,72,30,1,60,19,39,26,89,75,34,58,82,94,59,71,100,18,40,70,64,23,95,74,48,32,63,83,91}

    41

    33

    Returns: 21683

  34. {58,16,22,58,75,92,48,52,32,22,38,41,55,31,99,26,82,17,17,3,32,40,97,5,39,81,19,22,71,63,13,80,78,86,37,5,77,84,8,60,58,45,100,12,28,51,37,61,19,6}

    49

    64

    Returns: 0

  35. {887,778,916,794,336,387,493,650,422,363,28,691,60,764,927,541,427,173,737,212,369,568,430,783,531,863,124,68,136,930,803,23,59,70}

    3

    168

    Returns: 5471314

  36. {12,43,230,374,422,920,785}

    6

    538

    Returns: 0

  37. {316,371,414,527,92,981,957,874,863,171,997,282,306,926,85,328,337,506,847,730,314,858,125,896,583}

    14

    546

    Returns: 50152

  38. {435,365,44,751,88,809,277,179,789,585,404,652,755,400,933,61,677,369}

    10

    740

    Returns: 0

  39. {587,95,540,796,571,435,379,468,602,98,903,318,493,653,757,302,281,287,442,866,690,445,620,441,730,32,118}

    11

    98

    Returns: 4120235

  40. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    0

    1

    Returns: 49900050

  41. {1,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,999}

    49

    500

    Returns: 0

  42. {1,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,999}

    49

    1

    Returns: 12450050

  43. {2, 3, 5 }

    2

    1

    Returns: 17

  44. {827, 557, 285, 768, 761, 835, 627, 949, 350, 168, 978, 584, 698, 523, 10, 300, 368, 511, 585, 221, 584, 186, 596, 97, 636, 583, 650, 365, 163, 836, 205, 113, 371, 614, 369, 765, 373, 7, 489, 15, 853, 971, 99, 818, 427, 203, 616, 662, 563, 848 }

    10

    500

    Returns: 623647

  45. {4, 1, 9 }

    2

    2

    Returns: 22

  46. {1, 90, 100, 105 }

    2

    1

    Returns: 22598

  47. {1, 7, 19, 24, 50, 78, 200 }

    5

    5

    Returns: 20184

  48. {3, 2, 5, 1, 88, 100, 233, 8, 879, 7, 60, 880, 14, 17, 87, 23, 678, 24, 679, 25, 680 }

    5

    10

    Returns: 1529046

  49. {1, 7, 19, 24, 50, 78, 200, 300, 401, 599, 602, 708, 709, 710, 711, 712, 713, 714, 715, 720, 724, 801, 811, 820, 840, 856, 877, 933, 999 }

    5

    50

    Returns: 10366921

  50. {2, 2, 2 }

    0

    1

    Returns: 3

  51. {7, 1, 1, 1, 1, 7 }

    2

    1

    Returns: 36

  52. {1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1, 1000, 1 }

    20

    1

    Returns: 14970025

  53. {2, 3, 12 }

    2

    4

    Returns: 9

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: