Statistics

Problem Statement for "EllysLamps"

Problem Statement

Elly has a row of N lamps, conveniently numbered from 0 to N-1. Some of them are initially lit and the rest are not. She can control the lamps using a controller. On the controller there is a row of N buttons. Clicking the button with index i changes the state of lamp i: it goes off, if it was on, and it goes on if it was off.

Unfortunately the controller has some defects. Each of the buttons correctly changes the state of the corresponding lamp. However, it is possible that some of the buttons also change the state of one or both adjacent lamps as well. This means that pressing the button with index i has the following effects:
  • The state of lamp i changes.
  • If there is a lamp with index i-1, its state might change.
  • If there is a lamp with index i+1, its state might change.
The girl does not initially know which lamps change their state when each of the buttons is pressed. She knows, however, that every time she clicks a particular button, the same set of lamps will change their states.

Elly wants to reach a configuration in which the number of lamps that are turned on is minimized. Help her determine how many of them will remain lit in the worst possible case. (That is, for the worst possible way how the buttons change the state of the lamps.) She can use each of the buttons as many times as she likes, in any order she likes.

You will be given a String lamps, which gives information about the initial state of the lamps. The i-th character of lamps will be 'Y' if the i-th lamp is lit, and 'N', if it is not. Return the minimal number of lit lamps the girl can get in the worst possible case.

Definition

Class:
EllysLamps
Method:
getMin
Parameters:
String
Returns:
int
Method signature:
int getMin(String lamps)
(be sure your method is public)

Notes

  • The defects in the switches might not be symmetric. This means that if a lamp with index i happens to change the state of lamp i+1, this does not necessarily mean that the using the switch of lamp i+1 changes the state of lamp i.

Constraints

  • lamps will contain between 1 and 50 elements, inclusive.
  • Each element of lamps will be either 'Y' or 'N'.

Examples

  1. "YNNYN"

    Returns: 2

    In this case Elly will only make things worse (or the same) by pressing buttons. For example, suppose that: buttons 0 and 1 each change the state of both lamps 0 and 1 buttons 2 and 3 each change the state of both lamps 2 and 3 button 4 only changes the state of lamp 4 In this situation, Elly cannot reach any configuration with fewer than two lit lamps.

  2. "NNN"

    Returns: 0

    Obviously, with no initially lit lamps, Elly can just sit and relax.

  3. "YY"

    Returns: 0

    If one of the lamps influences the other one, then Elly can use it and turn both off with one button press. Otherwise, each button changes the state of its lamp only, thus Elly can turn them both off by pressing both buttons.

  4. "YNYYYNNNY"

    Returns: 3

  5. "YNYYYYNYNNYYNNNNNNYNYNYNYNNYNYYYNY"

    Returns: 13

  6. "Y"

    Returns: 0

  7. "N"

    Returns: 0

  8. "YY"

    Returns: 0

  9. "YN"

    Returns: 1

  10. "NY"

    Returns: 1

  11. "NN"

    Returns: 0

  12. "YYN"

    Returns: 1

  13. "YNY"

    Returns: 1

  14. "YNN"

    Returns: 1

  15. "NYY"

    Returns: 1

  16. "NYN"

    Returns: 1

  17. "NNY"

    Returns: 1

  18. "YYYYYYYYYNYYYYYYYYY"

    Returns: 6

  19. "NNNNNNNNNYNNNNNNNNN"

    Returns: 1

  20. "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY"

    Returns: 16

  21. "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN"

    Returns: 0

  22. "YNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYN"

    Returns: 25

  23. "NYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNY"

    Returns: 25

  24. "NYYNNNNNN"

    Returns: 2

  25. "NYYNYNNNN"

    Returns: 3

  26. "NYNYYNNNNN"

    Returns: 3

  27. "YYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYNYYYYYYYYY"

    Returns: 15

  28. "NNNYNNN"

    Returns: 1

  29. "NNNNYYNNYYNNNNYNYYNYYNNYNNNYNNYN"

    Returns: 11

  30. "NYNNNYNYYNNNNYNNYNYNNYYNNYNY"

    Returns: 11

  31. "YYYNYYYYYYYYYYNYNNNN"

    Returns: 6

  32. "YNNNYNYYYYYNYYYYYNYNNYYYYYY"

    Returns: 10

  33. "YNYNNNYY"

    Returns: 3

  34. "NYYYYYYYYYYYYYYYYNYYYYNNYYYYYYNNYYYYYY"

    Returns: 13

  35. "NNYNNYNNYNNNNNNNNNNYNNYNNNYNNNNNNNNNNNNN"

    Returns: 6

  36. "NYYYNNNYNN"

    Returns: 3

  37. "YYNYYYNYYYYYYYYYYYYNYYNYNYYYYYNYYYYYYNYNYYNNYYN"

    Returns: 18

  38. "NNNNNYNNN"

    Returns: 1

  39. "YNYYYYYYNYYYNYNNYYYNYNYYYYNYNYNYYYYYNNYYYNNNYNYYY"

    Returns: 19

  40. "YYYYYNYYNNNNYYYNYNYY"

    Returns: 6

  41. "YNNNYYYYYYYYNYNYYYYNYYNYYYYYNY"

    Returns: 11

  42. "NNNYYNNNNNNNNYYNNNYNNN"

    Returns: 5

  43. "YNYNYNYNNNYNYNYNNNNY"

    Returns: 8

  44. "NNYYYYYNNYNNYYYNYNYYYNYYYYNYYYYNYYNNNNNYNNYY"

    Returns: 16

  45. "NNNNYYYNNNNYYNNNYYNNNNNNNNNYNYNYNYNNNYNNNNNY"

    Returns: 12

  46. "NYNNNYNNYNNNYNNNNNNYNY"

    Returns: 6

  47. "NYYYYYYYYNNYYYNYYYYYYNYYYYYYYYYNYNYYYYYYYYNY"

    Returns: 16

  48. "NNNYYNNYNNYNNNYYNNNNNNNYNNNNNNNNYN"

    Returns: 8

  49. "NYYNYNNYYYNYYNYNNNNNNYNNNYYYNYYY"

    Returns: 11

  50. "YYNYYYNYYYYNYYNNYNYYYYYYYNNYNYNYYYYNNYYYYYYNY"

    Returns: 17

  51. "YYNYNNNNYNNYNNYN"

    Returns: 5

  52. "YNYYNYNNYNYYYNNNYNNNNYNYNYNNNYNN"

    Returns: 11

  53. "NNYNNYNYYNYYNNYNNY"

    Returns: 7

  54. "NNYNYNNNYYYNYNNYNNYYYNYNNYYYYYYNYNYYYYYY"

    Returns: 15

  55. "YNYNNYYNNYNYYYNYNYY"

    Returns: 8

  56. "NNNYNNNNNNN"

    Returns: 1

  57. "YNYYYNYNNYNNYYYN"

    Returns: 6

  58. "YYNYNYYYYYYYYYNYYYYYYYYYYYYYNYYYYYYYNYYYYYYYYYYY"

    Returns: 17

  59. "YYNYYNYNN"

    Returns: 3

  60. "NYYYYNNNNYYYYYYYYNYYYYYYYYNYYYY"

    Returns: 10

  61. "YYYNNNYNNYYNYNNNNYYNYN"

    Returns: 8

  62. "NYYYNNNYNNYNNNNN"

    Returns: 4

  63. "NNNNNNNNNNNNN"

    Returns: 0

  64. "NYNYNNNNNYNNNNNNNNNNNYNNNN"

    Returns: 4

  65. "YNYYYYYYNNYNNNNYYYYYYNYYYYNYYYNNYYYYY"

    Returns: 12

  66. "NNNNNNNNNN"

    Returns: 0

  67. "YYYYYYYYYYYYYYYYYN"

    Returns: 6

  68. "NYYYNNYYYNYYNYNYYNYYYNYYNNY"

    Returns: 11

  69. "YYYNYYYYNYYYYNYYYYYNNNNNYYYYYYYNNYYNNNNYNYYNNN"

    Returns: 16

  70. "NYNYNYNYNYYYYNYNYYNNYYYNYNY"

    Returns: 12

  71. "NYNN"

    Returns: 1

  72. "NNNNNNNNNNNNNNNNNN"

    Returns: 0

  73. "YNYYNNNNYNNNNNNNYYNNNYNNYY"

    Returns: 7

  74. "YNYNNYYYNNNYNYNYYYNYYYNYYNYNYNYNYYNNYY"

    Returns: 16

  75. "YNYYYYYYYYYYYYYYYYNYYYYYNYYYYYYYYYYYNYYNYYYYYYYY"

    Returns: 16

  76. "YNNYNNNYNNNNNNNNNYNYNNNYNNNYNNNNNNNYNN"

    Returns: 8

  77. "YNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYN"

    Returns: 25

  78. "NNYYNYYYYYNNYYYNNYNYNYYNYYNYYNNYNYYYNNNYNNYNNYNNNY"

    Returns: 19

  79. "NYYNNYYYYYNNNYNYNYYYYNYYYYNYNYYYYYNNYNYNYYYYYYYYYY"

    Returns: 21

  80. "NNYNNYYYNYYNYNYNYYNNYNYYYYNNNYNYNYNYNNYYNYYNYNYNYY"

    Returns: 19

  81. "YNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNYNNYYNNYYNNYYNNYYN"

    Returns: 25

  82. "NYYNNNNYNYNNNYYYNNNYNYNYNYNNNYNYNYYYYNYNYNNYYNNN"

    Returns: 18

  83. "YNNYYYYNYNYYNNYYYNYYNNNYYNYNYNNYYNYNYYNYYNYNYN"

    Returns: 20

  84. "YNYYYYNYNNYYNNNNNNYNYNYNYNNYNYYYNYNYNYNYNYNYNYYYYN"

    Returns: 21

  85. "YNYNYYYYNNNYNYNYNYNNYNNYNNNNYNYNYNYNNNYNYNYNYNY"

    Returns: 19

  86. "YNYYYYNYNNYYNNNNNNYNYNYNYNNYNYYYNYYYYYYYYYYYYYYYYY"

    Returns: 18

  87. "YNNYYYNNYNYNYNYNYNYNNNNYYYNYYYNYYNYNYYYNYNY"

    Returns: 18

  88. "YYYNNYYNNNNNNYYNYNYNNNNYYNNNYYYYYYNYNYNYYY"

    Returns: 15

  89. "YYY"

    Returns: 1

  90. "YYNYYYYYNYYNYNYNYNYNYNYYYNYNNNYYYNYYYYYYNYNYYNYYNY"

    Returns: 19

  91. "NNNNYYNYNNNYYYNNNNNYNYNYYNNNYNNNYYYYNNNNYY"

    Returns: 13

  92. "NNNYNYNYNYYYYYYYYYYNNNNNYNNNYNYNNYNY"

    Returns: 12

  93. "YYYYNNNNNYNYNYYYNNNYNYYYNNN"

    Returns: 9

  94. "YNYYYYNYNNYYYYYYYYYNYNYNYNNYNYYYNYYNNYNNNNNNYYYYYN"

    Returns: 19

  95. "YYYYYNYYYYNYY"

    Returns: 4

  96. "YYYYYY"

    Returns: 2

  97. "YNYYYY"

    Returns: 2

  98. "NYNYNNYNYNYNYYNYNYNYNYNYYYNNYNYNYN"

    Returns: 15

  99. "YYYYYYYYYYYYY"

    Returns: 4

  100. "YYYNNYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYNNNYYY"

    Returns: 16

  101. "YYYY"

    Returns: 1

  102. "YYYYYYYYYYYYYYYY"

    Returns: 5

  103. "YYNY"

    Returns: 1

  104. "YYYNYYNYYYNNNNYNNNYYYNNYYNNNYNYNYYNNYYYNNYNNYYNYYN"

    Returns: 19

  105. "NNYYNN"

    Returns: 2

  106. "YYYYN"

    Returns: 2

  107. "YNNNY"

    Returns: 2

  108. "YYYNY"

    Returns: 2

  109. "YYYYYYYYYY"

    Returns: 3

  110. "YNYYYNY"

    Returns: 3

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: