Statistics

Problem Statement for "HillHike"

Problem Statement

A hiker has set out to conquer a hill. The trail guide for the hill lists information known about the hill. First, it lists how tall the hill is, and how far it is to the other side of the hill. Next, it gives a list of landmarks that will be encountered while hiking the hill. The only things that are known about these landmarks are their height, and the order in which they appear along the trail. Finally, on this hill, there are three types of terrain: 

     _____
    /:   :\
   / :   : \
  /  :   :  \
 / 1 : 2 : 3 \

Type 1: rising terrain. In this type of terrain, the elevation of the hill rises one meter vertically for every meter that is traveled horizontally.

Type 2: level terrain. In this type of terrain, the elevation of the hill remains constant.

Type 3: falling terrain. This terrain's elevation falls one meter vertically for every meter that is traveled horizontally.

All three types of terrain can last for only multiples of one horizontal meter.

You will be given an int maxHeight (the maximum height of the hill, assuming the hill starts and ends at height 0), an int distance (how far horizontally one must travel to hike over the top and reach the bottom on the other side), and a int[] landmarks, which contains the heights of all the landmarks present on the trail. The order of the elements in landmarks is the order in which they will be encountered on the trail. All landmarks must be at least one horizontal meter apart.

Given all of this information, you must return how many different valid paths that the hiker could be facing. A path on the hill is a sequence consisting only of the three types of terrain for the entire distance of the hill. Two paths are different if and only if for at least one horizontal meter, the terrain type of one path is not the same as the terrain type of another path. A path is valid if and only if the path:
1. Starts at height 0 and ends at height 0
2. Has no other locations with height 0, or height below 0 (otherwise it would be two hills, or a valley)
3. Has at least one point where the height is equal to maxHeight (otherwise, the hill would be smaller)
4. Does not go above maxHeight (otherwise, it would be taller)
5. Is laid out such that the landmarks could be placed in the order given at points on the trail. Note that two landmarks cannot appear at the same point on the trail, even if they are at the same height. they must be at least 1 meter apart

If no valid paths exist, return 0.

Definition

Class:
HillHike
Method:
numPaths
Parameters:
int, int, int[]
Returns:
long
Method signature:
long numPaths(int distance, int maxHeight, int[] landmarks)
(be sure your method is public)

Notes

  • The C++ 64 bit data type is long long

Constraints

  • distance will be between 2 and 100, inclusive.
  • maxHeight will be between 1 and 50, inclusive.
  • landmarks will contain between 0 and 50 elements, inclusive.
  • Each element of landmarks will be between 1 and maxHeight, inclusive.
  • The return value will be less than or equal to 2^63 - 1 (it will fit into a long)

Examples

  1. 5

    2

    {}

    Returns: 3

    There are three paths with a distance of 5 and a height of 2: _ / \ _/\ /\_ / \ / \ / \ Distance: 12345 12345 12345 Notice that the 2nd and 3rd paths are mirror images, but are considered different. The following path cannot be used because it does not have a height of 2, even though it has a length of 5. ___ / \ 12345 The following path has a height of 2 and a length of 5, but the beginning and ending points are not the only points at height 0: /\ / \_ 12345

  2. 2

    45

    {}

    Returns: 0

  3. 5

    2

    {2,2}

    Returns: 1

    The only path which could contain both landmarks is: _ / \ / \ Distance: 12345

  4. 8

    3

    {2,2,3,1}

    Returns: 7

  5. 11

    3

    {3,1,3}

    Returns: 9

  6. 50

    13

    {11,11,2,5,7,8,4,9,4}

    Returns: 1173

  7. 73

    15

    {15,5,10,8,8,13,2,10}

    Returns: 225454034

  8. 51

    12

    {2,11,9,8}

    Returns: 3854869265851196600

  9. 96

    9

    {4,4,4,4,8,9,2,9,5,9,2,2,1,8,6,8,5,9,5,5,2,9,8,8,7,5,5,6,9,7,3}

    Returns: 101

  10. 78

    13

    {5,9,13,6,7,3,10,11,4,1,13}

    Returns: 2659553011489

  11. 59

    20

    {1,9,20,18,11,13,1}

    Returns: 469509251919309

  12. 83

    22

    {14,18,13,7,20}

    Returns: 2274413350842237951

  13. 41

    3

    {1,1,2,3,3,1,2,1,2,2,3}

    Returns: 115742120360885

  14. 97

    7

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

    Returns: 200589656215059748

  15. 64

    3

    {2,1,3,1,2,1,3,3,2,1,2,3,1,3,2,1,3,2,1,3,1,1,1,1,1,1,2,2,3,2,3,2}

    Returns: 601464655614205520

  16. 61

    3

    {3,1,1,2,3,3,1,3,2,3,2,1,1,2,3,3,2,3,3,1,3,3,1,3,3,1,3,2,2,2,3,2,3,2,1,2}

    Returns: 4191247687822

  17. 81

    10

    {2,2,9,8,6,7,9,8,5,6,7,8,5,1,2,7,10,2,2,9,1,1,2}

    Returns: 10608177313701633

  18. 37

    4

    {2,1,3,3,2,3,1,3,3,4,1,1,4,4,4,3,2}

    Returns: 1241333847

  19. 49

    2

    {1,1,1,2,1,1,1,2,1,2,2,1,2,2,1,2,1,2,2,1,2,2,2,1,1,1,1,1,2,2,2,2,1,2,2,2,2,2,2,2}

    Returns: 64441700

  20. 69

    3

    {2,3,2,3,2,1,1,1,3,3,2,2,1,3,2,2,3,2,1,3,3,2,3,2,2,2,3,2,1,1,3,2,2,2,1,1,3,2,1,2,3,3}

    Returns: 215760289078054021

  21. 57

    3

    {1,1,3,3,2,1,1,2,3,3,2,2,3,3,2,2,3,3,3,1,3,3,1,2,3,1}

    Returns: 982621157115627913

  22. 81

    19

    {7,4,5,3,5,11,18,18,18,16,10,9,4,5,11,1,7,3}

    Returns: 779008771

  23. 62

    7

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

    Returns: 611207

  24. 69

    3

    {2,2,1,3,2,3,1,2,2,1,1,3,3,3,3,3,3,2,2,2,3,2,2,1,2,2,2,2,3,3,2,1,3,1,1,3,2,1,3,2}

    Returns: 1001195673637831708

  25. 79

    6

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

    Returns: 27122582

  26. 44

    6

    {3,6,4}

    Returns: 155042220629586212

  27. 61

    25

    {}

    Returns: 1383704396097

  28. 70

    3

    {1,1,1,1,3,2,1,3,2,3,1,3,2,1,3,3,3,2,3,1,3,1,3,1,3,3,1,1,3,2,3,2,1,2,1,3,3,2,2,3,2,3,3,2,2,2,2,2,2}

    Returns: 17409730

  29. 50

    17

    {13,3}

    Returns: 127654173868581

  30. 49

    10

    {1,10,8,4,3,2,8,8,4,5,5,2,6}

    Returns: 2633787

  31. 78

    21

    {11,15,16,5,9,20,13,18,8}

    Returns: 1487951

  32. 35

    7

    {6,2,3,6,5,2,7}

    Returns: 397815

  33. 18

    6

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

    Returns: 133

  34. 22

    7

    {3,4,1,4}

    Returns: 412

  35. 44

    9

    {4,9,2,5,2,2,1}

    Returns: 290771380578796

  36. 18

    6

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

    Returns: 853

  37. 36

    2

    {2,1,2,1,1,1,2,1,2,1,2,2,1,2,1,2,2,2,1,1,1,2,1,1,1,1,1,2,1,1,2,2}

    Returns: 34

  38. 17

    4

    {}

    Returns: 119704

  39. 63

    6

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

    Returns: 14737279

  40. 47

    18

    {7,6,16,14,10,11}

    Returns: 101531088

  41. 65

    10

    {10,6,2,1,2,6,8,4,5,10,10,9,1,1}

    Returns: 29833085548522176

  42. 38

    11

    {4,5,8,5,6}

    Returns: 201667830444

  43. 60

    2

    {1}

    Returns: 144115188075855871

  44. 48

    4

    {1,2,1,1,3,2,4,1,3,2,2,1,4,1,2,1,2,1,1,1,1,4,3}

    Returns: 64935362155

  45. 88

    10

    {8,8,5,1,8,9,1,1,1,6,7,6,6,6,6,8,6,10,1,5,5,6,3,7,7}

    Returns: 898023426

  46. 78

    21

    {3,9,2,2,9,6,9,7,8,18,16,8,12,9}

    Returns: 78543

  47. 51

    12

    {8,5,5,9,4}

    Returns: 17701480714805588

  48. 50

    4

    {3,4,1,3,2,2,2,3,2,1,1,1,4,2,4,1,2,4,1,4,3,2,3,1,2}

    Returns: 22480360

  49. 38

    9

    {9,6,4}

    Returns: 24198365652196

  50. 56

    16

    {2}

    Returns: 4771328739784274850

  51. 41

    17

    {10,7,1,16,1,2,15,8,6,9,7,17,8,10,5,12,12,1,16,10,3,8,3,5,3,7,8,11,2,8,3,9,9,15,5}

    Returns: 0

  52. 95

    25

    {12,14,15,22,5,9,23,23,1,6,18,12,14,7,7,16,1,20,5}

    Returns: 0

  53. 30

    6

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

    Returns: 0

  54. 30

    26

    {21,4,19,18,18,13,14,17,25,26,12,6,14,1,11,24,18,14,25,18,10,25,4,19,7,16,7,2,19,21,7,19,14,6,10,3,4,15,25}

    Returns: 0

  55. 12

    27

    {13,10,1,12,17,23,13,4,2,1,24,12,5,19,20,2,1,10,9,20,23,9,1,4,15,21,6,18,15,12}

    Returns: 0

  56. 66

    28

    {11,25,9,19,3,10,9,21,19,28,23,25,20,5,27,22,3,11,18,1,13}

    Returns: 0

  57. 53

    34

    {31,34,18,3,33,26,4,28,18,1,11}

    Returns: 0

  58. 26

    23

    {20,3,21,7,20,11,3}

    Returns: 0

  59. 27

    12

    {6,10,1,4,3,5}

    Returns: 0

  60. 9

    22

    {17,1,6,1,10}

    Returns: 0

  61. 97

    31

    {18,18,30,26,23,19,11,15,21}

    Returns: 122691900197874159

  62. 100

    42

    {}

    Returns: 8126535387972713166

  63. 72

    4

    {4,2,4,4,3,1,4,4,1,2,3,1,1,2,2,2,3,4,1,4,3,1,1,2,4,4,3,3,3,2,4,1,1,1}

    Returns: 149605094496915649

  64. 10

    5

    {4,2,1,1}

    Returns: 0

  65. 100

    20

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 3344141088478506456

  66. 66

    2

    {}

    Returns: 9223372036854775807

  67. 38

    11

    { 4, 5, 8, 5, 6 }

    Returns: 201667830444

  68. 100

    50

    { }

    Returns: 1

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: