Statistics

Problem Statement for "ExploringEuropa"

Problem Statement

You are working for NASA and your job is to seek out life on other worlds within our Solar System. In this mission you are remotely controlling a probe that explores the deep ocean floor of Jupiter's moon Europa. Researchers have concluded that if there is any extraterrestrial life to be found, the first places to look are the hydrothermal vents. Basically the probe has to settle around a vent and explore it, but there is one major problem: communication delay. The probe is continuously sending status messages back to Earth, but each of them is only received after delay units of time. Analogously, if new instructions are sent from Earth, the probe needs delay units of time to receive them. The strategy employed is to move the probe on a single axis, at a constant speed. Initially the probe is situated at location 0. Your goal is to make it stop at one of the vents as soon as possible.

Your probe can receive one of the following three commands: 
FORWARD:
- This command is only given once, at time 0. The probe starts moving after delay units of time. 
REVERSE:
- You may issue this command when a new vent has been detected. After delay units of time, the probe instantly starts moving in the opposite direction. 
STOP:
- You issue this command if and only if, according to the information you gathered so far, you can be certain that the probe will stop at one of the vents. This is the last command you give and the probe stops after delay units of time.

Suppose delay is 5 and we have two vents, at locations 5 and 11, respectively. The procedure of remote controlling the probe goes like this:
time 0: You issue the "forward" signal.
time 5: The probe starts moving.
time 10: The probe reaches the vent at location 5.
time 15: You receive the signal that the probe has reached the vent and issue the "reverse" command.
time 16: The probe reaches the vent at location 11.
time 20: The probe receives the "reverse" signal and starts moving back. Its current position is at location 15.
time 21: You receive the signal that the probe has reached the vent at location 11. The probe is on its way back, currently at location 14. Unfortunately, we will miss this vent. Even if the "stop" command is issued now, by the time it is received, the probe will have already moved away to location 9. You now have to decide whether another "reverse" command is appropriate. Currently, the probe will stop after 30 units of time at the vent at location 5. However, by issuing the "reverse" command again, the probe will stop after 28 units of time at the vent at location 11.
time 23: You issue the "stop" signal. The probe is at location 12 and moves left (towards smaller locations).
time 24: The probe passes the vent at location 11.
time 26: The probe receives the "reverse" signal issued at time 21, is currently at location 9, and starts moving right.
time 28: The probe stops and the vent at location 11 can now be explored.

You are given a String surface, where 'S' is the first character and denotes the starting position, '-' denotes regular ocean floor and 'V' denotes a vent. Assume that the surface is plain after the end of the input ("SV" is the same as "SV--------------"). You are also given an int delay, denoting the time needed for a signal to travel between Earth and Europa. Return an int representing the amount of time elapsed between the FORWARD command and the moment the probe stops.

Definition

Class:
ExploringEuropa
Method:
travelTime
Parameters:
String, int
Returns:
int
Method signature:
int travelTime(String surface, int delay)
(be sure your method is public)

Notes

  • Keep in mind that a reverse command is only meaningful when aiming for the last detected vent. Do not issue it in other cases!
  • No more than 2 reverse commands are ever needed.

Constraints

  • surface will contain between 2 and 50 characters, inclusive.
  • The first character of surface will be an 'S'.
  • surface will contain at least one 'V' character.
  • Each character of surface, except the first, is either a '-' or a 'V'.
  • delay is between 1 and 50, inclusive.

Examples

  1. "S----V-----V----"

    5

    Returns: 28

    This is the example from the problem statement.

  2. "S----VV---------"

    5

    Returns: 29

  3. "S---V"

    10

    Returns: 54

  4. "SVVVVV"

    1

    Returns: 5

  5. "S------------------------------V-----------V"

    22

    Returns: 129

  6. "S----V------V---"

    5

    Returns: 30

  7. "S----V-------V--"

    5

    Returns: 30

  8. "S----V-------V--"

    5

    Returns: 30

  9. "S----V--------V-"

    5

    Returns: 30

  10. "S----V---------V"

    5

    Returns: 30

  11. "S----V----V-----"

    5

    Returns: 25

  12. "S----V---V------"

    5

    Returns: 26

  13. "S----V--V-------"

    5

    Returns: 27

  14. "S----V-V--------"

    5

    Returns: 28

  15. "S----V-V--------V-------------------V-"

    9

    Returns: 47

  16. "S----V-----------V-------------------V-"

    9

    Returns: 50

  17. "S------------------------V----V------------------V"

    18

    Returns: 110

  18. "S-------------------VV----------------------------"

    9

    Returns: 64

  19. "S---------------------V--V-V----------------------"

    28

    Returns: 157

  20. "S---V--------V----------------V-------------------"

    20

    Returns: 95

  21. "SV-V-V--V-VV---V-----V----V---V---VV-----------V--"

    22

    Returns: 91

  22. "S----------V------------------------V--------V----"

    14

    Returns: 81

  23. "SV-----------V------V-----------------------------"

    12

    Returns: 49

  24. "S----------------------------------V----V---V-----"

    20

    Returns: 126

  25. "S----------------------V-------------------V--V---"

    36

    Returns: 180

  26. "S------------V-V----VVVV--------V------V----V-----"

    10

    Returns: 53

  27. "S--------------------------------V----------V-----"

    14

    Returns: 92

  28. "SV------------V----V------------------------------"

    7

    Returns: 36

  29. "S----V------------V------------------------V------"

    23

    Returns: 107

  30. "S-----------V-----------V------V------------------"

    15

    Returns: 75

  31. "S-V-VV-V----VVV-V------VV----VV-VVV---V--V-V--VVV-"

    17

    Returns: 73

  32. "S--------V------V--------------------------V------"

    13

    Returns: 67

  33. "S-------------------V----------------V------V-----"

    8

    Returns: 60

  34. "S------------------------------V--V------------V--"

    6

    Returns: 58

  35. "SV----------------------------------V-------------"

    18

    Returns: 91

  36. "S-V--VVV-----V-----------V-----V----------V-------"

    8

    Returns: 37

  37. "S----------V-------------V------------V-----------"

    24

    Returns: 116

  38. "S----VV--------V----------------------------------"

    40

    Returns: 195

  39. "S--------V-------V----------------V---------------"

    11

    Returns: 56

  40. "S----------V-----------V-------------------V------"

    10

    Returns: 57

  41. "SV-V--V-V-V-V-VV----V--VVV-VV----V-VV---V--V---V--"

    6

    Returns: 26

  42. "S---------V------------------------------------V-V"

    25

    Returns: 135

  43. "S-----VV--------------------------------------V---"

    16

    Returns: 85

  44. "S----V-V-----------------------------------------V"

    7

    Returns: 38

  45. "S--------------------------V-V--V-----------------"

    17

    Returns: 107

  46. "SV-VV----V----V-V--VV-----V-----V----V--V----V-V-V"

    25

    Returns: 101

  47. "S----------------V-------------------V------V-----"

    8

    Returns: 57

  48. "S---------------------V------------V--V-----------"

    20

    Returns: 106

  49. "S----V---V------V-------------------V-"

    9

    Returns: 46

  50. "S-------V--------V--------------V-----------------"

    19

    Returns: 94

  51. "S--V---V-----VVV-V---V---VVV-V--VV---V-V------V---"

    18

    Returns: 75

  52. "S---V--V---------------V--------------------------"

    23

    Returns: 100

  53. "S-------------------V--------V-------V------------"

    18

    Returns: 93

  54. "SV---V-----------------V--------------------------"

    8

    Returns: 37

  55. "S-------V--------------------------V---V----------"

    14

    Returns: 78

  56. "S-VV-----V--V-V--VV-------V--VV---V--VV---V----V--"

    6

    Returns: 29

  57. "S---V----------------------------------V---------V"

    22

    Returns: 114

  58. "SV-----------------------V-----------------------V"

    17

    Returns: 86

  59. "S-------------V-------V--V------------------------"

    10

    Returns: 56

  60. "S-----------------V-------V--------------V--------"

    18

    Returns: 100

  61. "S------VVVVV------V--V-VVV---VV----V--VVV-------V-"

    15

    Returns: 68

  62. "S-----------V---------------------V-----V---------"

    24

    Returns: 110

  63. "S---------------V-------------V-----------------V-"

    16

    Returns: 82

  64. "S----V----V--------------------------V------------"

    25

    Returns: 125

  65. "S---------------------------V-----------V-------V-"

    5

    Returns: 53

  66. "S----------V----V--V-V-VV----VVVV--VV----V-VV--V--"

    23

    Returns: 105

  67. "S--------V-------V-------------------------------V"

    25

    Returns: 126

  68. "S----------V------------------V------------V------"

    44

    Returns: 199

  69. "S----------------V-----V---------V----------------"

    15

    Returns: 80

  70. "S--------------V------------VV--------------------"

    12

    Returns: 66

  71. "SV-V-V------V---V-----V-V----V-V--------VVV--V---V"

    19

    Returns: 81

  72. "S-----------------------------V---------V------V--"

    20

    Returns: 113

  73. "S------------------------------------V-VV---------"

    6

    Returns: 64

  74. "S------V-------------V-------------------------V--"

    24

    Returns: 113

  75. "S---------------V-V-----------V-------------------"

    16

    Returns: 82

  76. "S-VV-V----V----V-----V-V---V--V------V------V---V-"

    12

    Returns: 53

  77. "S--V----------------V----------V------------------"

    17

    Returns: 71

  78. "S-------------------------V----V----------------V-"

    11

    Returns: 76

  79. "S-----------------V-------------------V----------V"

    17

    Returns: 95

  80. "S------------------V----------V-V-----------------"

    16

    Returns: 86

  81. "S-V-V---VV------V-----V-----V-V---V-VV-VVV--V-V--V"

    25

    Returns: 105

  82. "S------V------------V---------V-------------------"

    9

    Returns: 52

  83. "S---------------V----V-----------------V----------"

    20

    Returns: 105

  84. "S--------------------------V-----------V---V------"

    17

    Returns: 96

  85. "S--------V--------V-----------------------V-------"

    16

    Returns: 80

  86. "S--V-------VV---V--VVV--V--V-VV-------V---V-V---VV"

    22

    Returns: 92

  87. "S--------V------V----------------V----------------"

    16

    Returns: 82

  88. "S------------V-----V---------------V--------------"

    48

    Returns: 231

  89. "S--------------V-------------V--------V-----------"

    19

    Returns: 96

  90. "S--------------V---------------------------VV-----"

    15

    Returns: 90

  91. "S-----V--V-V-----VV--V--VVVV--VV--V--V------V-----"

    27

    Returns: 116

  92. "S------V-------------------------V---------V------"

    5

    Returns: 32

  93. "S---V-------------------------------V-V-----------"

    6

    Returns: 34

  94. "S--V---V-------------------------V----------------"

    11

    Returns: 54

  95. "S-----V---------------------------V------------V--"

    11

    Returns: 61

  96. "S---VV-V----V---VV-V-V---------VV----V-------V---V"

    20

    Returns: 87

  97. "SV-------V-------V--------------------------------"

    7

    Returns: 32

  98. "S-V---------V---------------------------V---------"

    22

    Returns: 102

  99. "S-------V---------------------V--------V----------"

    13

    Returns: 73

  100. "S---------V-----------------------------V------V--"

    14

    Returns: 80

  101. "S----VVV-V----V-----------V---------V-------V--VV-"

    21

    Returns: 89

  102. "S----------V-----------------------------------V-V"

    20

    Returns: 111

  103. "S--------V-------------------------------------VV-"

    20

    Returns: 109

  104. "S-----------V-------V-----------------------V-----"

    12

    Returns: 64

  105. "S-------V--------V-------V------------------------"

    9

    Returns: 44

  106. "S--V----V------VV-VV-V--VVV----V-VV-V---V-V--V--V-"

    5

    Returns: 23

  107. "S--------V--------------------------------V--V----"

    12

    Returns: 69

  108. "S---------------------------V---------------V-----"

    18

    Returns: 102

  109. "S-V---------------V----V--------------------------"

    10

    Returns: 52

  110. "S-------------V--------V------V-------------------"

    18

    Returns: 88

  111. "S--------V---V---VV--VV-V-VVV--V----V-------VV-V--"

    15

    Returns: 69

  112. "S--------------V---------V-------------------V----"

    22

    Returns: 115

  113. "S-------------------------------V--V-----V--------"

    10

    Returns: 73

  114. "S-V--------V--------V-----------------------------"

    14

    Returns: 63

  115. "S---V-------------------------V----------V--------"

    25

    Returns: 107

  116. "S--V-V--VVVVV---VVV---V-----V-V--------V--V-V-----"

    21

    Returns: 89

  117. "S------------------------------------------------V"

    50

    Returns: 299

  118. "SVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV"

    50

    Returns: 203

  119. "SVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV"

    1

    Returns: 5

  120. "SVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV"

    23

    Returns: 93

  121. "SV"

    1

    Returns: 6

  122. "SV"

    50

    Returns: 251

  123. "S---V"

    10

    Returns: 54

  124. "S------------------V-V-V--VV-V-V-V-V-V-V-V-VV"

    7

    Returns: 47

  125. "SV--------"

    31

    Returns: 156

  126. "SV"

    50

    Returns: 251

  127. "SVV----V"

    5

    Returns: 24

  128. "S-V------------V------------"

    7

    Returns: 37

  129. "S----V---VVVVVVV"

    5

    Returns: 25

  130. "S-VVV--V-"

    4

    Returns: 20

  131. "S-------------------------VV--VVVVVV-----------V"

    3

    Returns: 40

  132. "S----V-V-VV"

    5

    Returns: 25

  133. "SVVVVV"

    1

    Returns: 5

  134. "SVVV"

    2

    Returns: 9

  135. "S-----------VVV"

    10

    Returns: 60

  136. "S----VVV--------"

    5

    Returns: 28

  137. "SVV----V-V"

    5

    Returns: 24

  138. "SV"

    1

    Returns: 6

  139. "S---V--------V-------------------V"

    49

    Returns: 220

  140. "S----VV---------"

    34

    Returns: 174

  141. "SV--------------------V"

    15

    Returns: 76

  142. "SVVVVVV---VVVVVVVVVVVVV"

    50

    Returns: 230

  143. "S----VV----V----"

    5

    Returns: 28

  144. "S----V-----------V---"

    10

    Returns: 51

  145. "S-----V------V----"

    6

    Returns: 33

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: