Statistics

Problem Statement for "EllysTSP"

Problem Statement

Everybody who has lived in a village knows how expensive the things from the city are. And everybody who has lived in the city knows how expensive the things from the village are. Elly decided to use these observations to make some profit. She will start at some city or village, buy cheap stuff there, go to a place of the opposite type (village if she started in a city, or city if she started in a village) and sell it at a profit there, buying new stuff for the next place (again of the opposite type) and so on. Shortly after she leaves a city or village, the inhabitants realize how she tricked them and get angry at her, so she cannot go to the same place twice.

Elly cannot predict the actual profits she will make while using this strategy. Therefore she decided that she simply wants to visit as many places as possible. Of course, she has to alternate between visiting a village and visiting a city, and she may not visit the same place twice.

You are given a String places that describes all places Elly can visit. The i-th character of places is 'V' if the i-th place is a village, or 'C' if it is a city. Return the maximal number of places she can visit according to the rules above.

Definition

Class:
EllysTSP
Method:
getMax
Parameters:
String
Returns:
int
Method signature:
int getMax(String places)
(be sure your method is public)

Notes

  • Elly can travel directly between any two places.
  • The minimal answer is 1 as she can start by visiting any one of the available places.
  • The answer will never exceed the length of places, since she is not allowed to visit the same place more than once.

Constraints

  • places will contain between 1 and 50 characters, inclusive.
  • Each character of places will be either 'V' or 'C'.

Examples

  1. "CVVVC"

    Returns: 5

    It is possible to visit all 5 places. One solution is to start at place 1 (a village), go to place 0 (a city), then to place 2 (a village), place 4 (a city), and finally to place 3 (a village).

  2. "VVV"

    Returns: 1

    She may start by visiting any of the three villages. As there are no cities, she cannot make any more travels.

  3. "VVVVCVV"

    Returns: 3

    There is only one city among the places. Elly can go to any of the villages, then go to the city, and then to one of the other villages. Thus, the optimal result is 3.

  4. "CVCVCVC"

    Returns: 7

    Just visit the locations in the order in which they are given.

  5. "C"

    Returns: 1

  6. "V"

    Returns: 1

    With only one place there is not much choice what to do.

  7. "CV"

    Returns: 2

  8. "VC"

    Returns: 2

  9. "CCCCCC"

    Returns: 1

  10. "VVVCCC"

    Returns: 6

  11. "VCVCCVVCCCVCCVCVVCVCVVCVVVCCCVCVCVCC"

    Returns: 35

  12. "CCC"

    Returns: 1

  13. "CVVCCCCVVCCVCVCVCCVCVCVVCCCCVVCCCC"

    Returns: 27

  14. "CVCVCCVVVCVVCVCVCCVCVVVVVCCVVCVCCCCVVVVCCVCVCVCVVC"

    Returns: 47

  15. "VCCCVVCVCVVVVVCVCCCVCCCCCCCVCCVVCCCVVVCVCVVCCVCVCC"

    Returns: 45

  16. "CVVVCVVCVVCCVCCVVCVCCCVCCCCCCCCVVCVV"

    Returns: 33

  17. "CCVCCVVVCVCVVCVV"

    Returns: 15

  18. "VCCCCVCCCCVCCVCCCCVVVCCCVCCVCVC"

    Returns: 21

  19. "VCCVCVCVVCVCCVVCVVCVCVCVVVCCCCVVCCCCVCCCVV"

    Returns: 41

  20. "CVVCVVCCCCCVVCVCVVCVV"

    Returns: 21

  21. "CVCVVCCVVVCVCVCVCVVVCCVCCV"

    Returns: 25

  22. "VCCVVVVCCCVCCV"

    Returns: 14

  23. "CCVCVCVVVCCCVCCVCVCCCCVCVCCCVCCCCCCCVCVVVC"

    Returns: 31

  24. "VCVCCVVVVVCCVVCVVCVCVVVCVVCCVCCVVVVCVCCCCVVCVVCCCV"

    Returns: 45

  25. "CCVVVVCVCVVCVCVCCCCVVCVCVCCCVCVCCCVVVCCVVCVVCCVVVV"

    Returns: 49

  26. "CCVVCCCVVCVCCCVVCCVVVVCCV"

    Returns: 25

  27. "CCVVVCCVVCVCVVCVVCVCCVCCVVVVVVCVVV"

    Returns: 27

  28. "CVVCCCCVVVVVCCCVCCCCVCCCVCVCV"

    Returns: 25

  29. "CCCCVCVVVVCVCCCVVCCCVVVCV"

    Returns: 25

  30. "VCVCCCCCCCCVCVCCVCCCCVVVCCCVVVCCVVCCVCCVCVVCCCCVCC"

    Returns: 37

  31. "VCCCVCVVVVCC"

    Returns: 12

  32. "VVVCCCVCCV"

    Returns: 10

  33. "V"

    Returns: 1

  34. "CVVVVVVVCVVVVVVCVVCVCVVVVCCVC"

    Returns: 17

  35. "CVVVCCCCCVVCVVC"

    Returns: 15

  36. "CVCVCV"

    Returns: 6

  37. "CCCVCVVVCCCCVCCVCVCCCV"

    Returns: 17

  38. "VVVCCVVVVVVVCCCCCVCCVVCVCCVCCCVCCVCVCCCVVCVCCCCCVV"

    Returns: 47

  39. "VCCVCCVCVVVVV"

    Returns: 11

  40. "VCVCCVCCCVVCVVVCCCVCVCCVCVCVCVVVCCVCVVCCVVVVVCC"

    Returns: 47

  41. "VVCCVVVVCVVCCVCCVCVVCCVVVCVCCCCVVCVC"

    Returns: 35

  42. "CCVVCVVCVVCVCCVVVVCCCVCVVVVVCCCCVCCCVVCCVCCCVCCVVC"

    Returns: 49

  43. "VCCCVCCVCC"

    Returns: 7

  44. "VVCCCCCVVVCVCVCVCVCVVCVCVVCVCVCCVCVVVCCVVCVCVVCVCC"

    Returns: 49

  45. "VVVVVCCVCCVVVCCVVVVCVCCVVVVCCVVCCVCVVCCVVVCCCCVVVC"

    Returns: 43

  46. "CVVCCCCCCCVVCV"

    Returns: 11

  47. "CVCVVVCCVVV"

    Returns: 9

  48. "CCVVCVVCVCVVVCVCVCCVVC"

    Returns: 21

  49. "VVCVVVVVCVCVVVVVVCCCCVVCCVCVCVVCCVCCCVCCCCV"

    Returns: 41

  50. "CCVCVCVVVVCVCCVCCCVCVCCCVCVVCVCVCCCCCCVVVCVCV"

    Returns: 41

  51. "CVVVCCVVVVVVVCCVCVCCC"

    Returns: 19

  52. "VCVCVCVVCVVCCCCCCVCVVVCCV"

    Returns: 25

  53. "CVCVCVCVCCVCVCCVCVVCVCCCVCVVVVCVVVCCVC"

    Returns: 38

  54. "CCVVVVVCCVVVVVCVCCCVCVCCVVCVCVC"

    Returns: 29

  55. "CCVVCCCVVVCCCCCCCVVVCCV"

    Returns: 19

  56. "CCCVCVVCCVCVCVCCCCVCCCVVCCVCCCVVCVVCVCCCVVCCCCCCCC"

    Returns: 35

  57. "CCVVCVVVVVVCVCV"

    Returns: 11

  58. "VVCVCCVCVVCCVVCCCVVCCCVCCCCVVVCCVVCVVVC"

    Returns: 39

  59. "CVCVVCVCCCVVCCVCVCVCVVVCCCCVCVCCVVCVCVVCVCCCCCCCCC"

    Returns: 41

  60. "VCCVVCVVVCVVCCCCCVVCVVVCCCCCCVVCCCVCCVVCVCCCCCVV"

    Returns: 43

  61. "VVVVCCCCVVVCVVCVCC"

    Returns: 17

  62. "VVVVCV"

    Returns: 3

  63. "CCCVCVCVCVVCVCVVCCVVCVCCCCVCVVCVCCCVCCCCVVVCVVCVCV"

    Returns: 47

  64. "VCVCCVCCCVCCVVCCCVVVCCVCVVVCVCVVCVVVVCVCCVCVCVCCCV"

    Returns: 50

  65. "CCCVCCVVCCCVCCVCVCCVVVVVVVC"

    Returns: 27

  66. "VCCVCCCVVCCVVVCCCVCCCVVCCCCVCCVVVCCVVVCVVVVVVVCCVV"

    Returns: 49

  67. "VVVVVVCVCVCVVCVVVVCCVCCCVCVCVCVCVVCVCC"

    Returns: 33

  68. "VCCCCCVVVVCC"

    Returns: 11

  69. "CCVCVCVCVVVCCCCCVCVVVVVVVVVCVCCVCVVCVCCCCVCVCCCC"

    Returns: 47

  70. "VCVVVCVVCCCCCCVVVCCVCVCCCVCCVCCCVCVCVCCCCCCVVVCVCV"

    Returns: 43

  71. "CCVCVCCCCVC"

    Returns: 7

  72. "CVVCVVCCVCCVCVCVCVVCCVCCCCVVVVCVVCCVCVCCCCCCCCCVCV"

    Returns: 43

  73. "VVCCCVCVVC"

    Returns: 10

  74. "VVVCCCVCVCCCVVVVCCVCVCVVVCCCVCVCVCVVCCCCCCVCVVVCVC"

    Returns: 49

  75. "CCCCCVVVVVCCVVCCVVCVVCCCVVCCVCCCCCCCVVCCVVVVVVCCCC"

    Returns: 45

  76. "CC"

    Returns: 1

  77. "VCVCCCVCCVCVVVCVVVCCVCVCVCVCVVVVVVCVVCCCCCCCVVVCCC"

    Returns: 50

  78. "CCCCVVCVVCVCCVCCVCCCCCVVCCVCVVVCCCVCVCCCCVCCCCVVC"

    Returns: 37

  79. "VCVVCVVCVVV"

    Returns: 7

  80. "VCVCVVVVCCCCCVCVVCVCCVVCVCCCCCVCCVCVVVVVCCCCCCCCCC"

    Returns: 41

  81. "CVVCVCVVCVVCCVVCCVVCVVCVCCVVVVCVCCCVCCCVCCCVCVVV"

    Returns: 47

  82. "VVCVVCCVCCCCVCVCVCVVVCCCVVVVC"

    Returns: 29

  83. "CCVVCVVVCCCCCVVCVVCCCVCVVVVVCVCCVCCCCVCVC"

    Returns: 39

  84. "VVCCCVCCCCCCCVVVVVVVCCVCCCVCCCVCVVCVC"

    Returns: 33

  85. "VVCCCCVVVCVCCVC"

    Returns: 15

  86. "CVVCCCCVVCVVV"

    Returns: 13

  87. "CCCCCVCCVVCCCCVCVCVVCVVVVVVCVVVVCVVCVVVCCVVCCVVVVV"

    Returns: 43

  88. "CVCVVCCCCCVVVVCCCVVCVCCVVVCVCVCCCCV"

    Returns: 33

  89. "VCCVVVCVVVCC"

    Returns: 11

  90. "CVCCCCCCVVVCV"

    Returns: 11

  91. "VVVCVVVVVCCVCCVVVCCVCVCVVVCCCCVCCVCVCVCVVVVCVCVVVV"

    Returns: 41

  92. "CVVVCVCCCCVVVCVCCCV"

    Returns: 19

  93. "VCVVVVVCVCCCCCVVCVCCCCVVVVCCVCCCCCVCCVCCVVCVC"

    Returns: 41

  94. "CVVCCCCCCCCCVCCVVVCCVVVVCCCCCVCVCVV"

    Returns: 29

  95. "CVCVVCCCCVCCVCVCVCCCVCCCCVCVVVCVVCCCVCVCCVCCCVCCCC"

    Returns: 37

  96. "CCVVVVVVCCCCCCV"

    Returns: 15

  97. "VCVCVVCCCCCVVVVVCCVCCCVVVC"

    Returns: 26

  98. "VVVCVVVVVCCCCCCVCCVVVCVCVCVVCVCC"

    Returns: 31

  99. "CVVCCVCCCCVVVVVCVVVCVCCCCVVVVCCCCVC"

    Returns: 35

  100. "VCVVVVVVCVCVCVVCCCVCVVC"

    Returns: 19

  101. "CCVV"

    Returns: 4

  102. "CCCVVV"

    Returns: 6

  103. "VVCC"

    Returns: 4

  104. "CVCV"

    Returns: 4

  105. "VCVC"

    Returns: 4

  106. "CCVVVVV"

    Returns: 5

  107. "VCVCVC"

    Returns: 6

  108. "CCVVV"

    Returns: 5

  109. "CCCVVVVV"

    Returns: 7

  110. "VVVCCCCC"

    Returns: 7

  111. "VVVVVCC"

    Returns: 5

  112. "CVVC"

    Returns: 4

  113. "VVCCCCCC"

    Returns: 5

  114. "CVCVCVCV"

    Returns: 8

  115. "VVVVCCCCCCCCC"

    Returns: 9

  116. "CCCCCCVVVV"

    Returns: 9

  117. "VVVCCCVVVV"

    Returns: 7

  118. "VVVVVVCCCCCCCCCCC"

    Returns: 13

  119. "CVVVVVVVVVVVC"

    Returns: 5

  120. "CCCCCVCVVVVVCCCCCVCVVVVVV"

    Returns: 25

  121. "VVVVVVVVVCC"

    Returns: 5

  122. "VVVVVVVCCC"

    Returns: 7

  123. "VVVC"

    Returns: 3

  124. "CVCVCVCVCVCVCV"

    Returns: 14

  125. "CCCCCVVVVV"

    Returns: 10

  126. "CCCVVVVVVV"

    Returns: 7

  127. "VVVVVCCC"

    Returns: 7

  128. "VVVVVVVVVVVVVCC"

    Returns: 5

  129. "CCCVVVVVVVVVV"

    Returns: 7

  130. "VCVCVCVCCVCVCVCVVCVVCC"

    Returns: 22

  131. "CCCCCCVVVVVV"

    Returns: 12

  132. "VVCCCC"

    Returns: 5

  133. "CVCVCVCCC"

    Returns: 7

  134. "CCCCCVVV"

    Returns: 7

  135. "CCCCCCVVV"

    Returns: 7

  136. "CCCCVVVVVVVV"

    Returns: 9

  137. "VVVCC"

    Returns: 5

  138. "VVVCCCCCCCC"

    Returns: 7

  139. "CCCCVVVVVV"

    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: