Statistics

Problem Statement for "SurveillanceSystem"

Problem Statement

There is a long narrow storehouse. The storehouse is divided into a sequence of N identical sectors, labeled 0 through N-1. Each sector is large enough to contain a single container. Currently, some sectors are empty and some sectors are filled by containers. The storehouse also contains a surveillance system that is described below.

We are going to break into the storehouse. As a part of preparation for the heist, we already found out some information about the warehouse. In particular, we know exactly how the containers are currently placed in the warehouse. You are given a String containers consisting of N characters. For each i, character i of containers is 'X' if sector i contains a container, and it is '-' if sector i is empty.

We also discovered some information about the surveillance system. The system consists of several hidden cameras. You are given a int L with the following meaning: Each of the cameras monitors exactly L consecutive sectors. The segments of sectors monitored by different cameras might overlap, but no two cameras watch exactly the same segment. (In other words, each sector may be monitored by multiple cameras, but each camera monitors a different set of consecutive sectors.)

Finally, we know something about what the cameras currently see. You are given a int[] reports. Each element of reports corresponds to one of the cameras (in no particular order). More precisely, reports[i] is the number of containers stored in the sectors monitored by the corresponding camera.

It is guaranteed that all our information is correct and consistent.

Your task is to use the provided information to deduce which sectors are monitored by at least one surveillance camera. Return a String containing N characters. For each i, character i of the return value should be one of '+', '?', and '-'. Character '+' represents that sector i is certainly monitored by at least one camera. Character '-' represents that sector i is certainly not monitored by any of the cameras. Character '?' represents the remaining case: given the information we have, it is possible that sector i is monitored, but it is also possible that it is not monitored.

Definition

Class:
SurveillanceSystem
Method:
getContainerInfo
Parameters:
String, int[], int
Returns:
String
Method signature:
String getContainerInfo(String containers, int[] reports, int L)
(be sure your method is public)

Constraints

  • containers will contain N elements, where N is between 1 and 50, inclusive.
  • Each character in containers will be either 'X' or '-'.
  • L will be between 1 and N, inclusive.
  • reports will contain between 1 and N-L+1 elements, inclusive.
  • Each element of reports will be between 0 and L, inclusive.
  • The given information will be consistent.

Examples

  1. "-X--XX"

    {1, 2}

    3

    Returns: "??++++"

    This storehouse has 6 sectors. There are containers in sectors 1, 4, and 5. There are two cameras: camera #0 monitors 1 container, and camera #1 monitors 2 containers. Clearly, camera #1 must be watching sectors 3, 4, and 5. Camera #0 may be watching sectors (0, 1, 2), (1, 2, 3), or (2, 3, 4). Thus, camera #0 is surely monitoring sector 2. Sectors 0 and 1 may or may not be monitored.

  2. "-XXXXX-"

    {2}

    3

    Returns: "???-???"

    The camera is monitoring either the leftmost or the rightmost segment, thus the middle sector is surely not under surveillance.

  3. "------X-XX-"

    {3, 0, 2, 0}

    5

    Returns: "++++++++++?"

    We can deduce that cameras #1 and #3 are watching segments (0, 1, 2, 3, 4) and (1, 2, 3, 4, 5). Camera #2 is monitoring the segment (4, 5, 6, 7, 8), since this is the only segment with two occupied sectors. Camera #0 is either watching (5, 6, 7, 8, 9) or (6, 7, 8, 9, 10), thus the rightmost sector might have slipped from the surveillance.

  4. "-XXXXX---X--"

    {2, 1, 0, 1}

    3

    Returns: "???-??++++??"

  5. "-XX--X-XX-X-X--X---XX-X---XXXX-----X"

    {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}

    7

    Returns: "???++++?++++++++++++++++++++??????--"

  6. "X"

    {1}

    1

    Returns: "+"

  7. "X-"

    {1}

    2

    Returns: "++"

  8. "XX"

    {1,1}

    1

    Returns: "++"

  9. "--X-X--X----X--X-X-X----"

    {7,7,7}

    22

    Returns: "++++++++++++++++++++++++"

  10. "---"

    {0,0}

    2

    Returns: "+++"

  11. "-X-XXX-X-XXXX--XX-XX-X---XX----XX---X-XX--X-X-X-"

    {11,9}

    18

    Returns: "?????????++++++++++++++++++++????---------------"

  12. "-X--X---XX"

    {3}

    8

    Returns: "-?+++++++?"

  13. "X--XX-X-----"

    {3,4,2,3,3}

    8

    Returns: "++++++++++++"

  14. "---XXX----X---X-XX-X-XXXX-X-XX-XX-X-X--XX--X"

    {19,20,21,20,20}

    39

    Returns: "++++++++++++++++++++++++++++++++++++++++++++"

  15. "-X-X------X-XX-X-XX-----XXXX-X-X--X-X---XX"

    {2,3,5,5}

    10

    Returns: "??++++++++??????????????????????????????--"

  16. "XXXX--XXX-XXX-X--X-X---X-XXX----XXX-"

    {9,9,11,7,7,11,8,8,7,10}

    17

    Returns: "+++++++++++++++++++++++++++++++++???"

  17. "-XXXX-XXXX-XX-X-XXX-----XXX---X--X-X"

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

    4

    Returns: "????????????????????????????????????"

  18. "-X--XX---XXXXXX-X--X-X"

    {6}

    11

    Returns: "-?++++++++++?---------"

  19. "------X-XX-X-"

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

    2

    Returns: "?????????????"

  20. "X-X-XX----XX-XXXXX-XX---XXX-X--X"

    {14}

    25

    Returns: "???????++++++++++++++++++???????"

  21. "X--X-XX--X--XX-X-X---X--XX--XX-X-XX--X--X-XX--X-X"

    {5,4,4,5,3,4,4,4,5,5,3,4,4,5,4,4,5,4,5,4,5,4,4,4,4,3,4,4,5,4,3,4,4}

    9

    Returns: "??????+++++++++++++++++++++++++++++++++++++??????"

  22. "-XX--X-X--"

    {3,2,3,2}

    6

    Returns: "?+++++++++"

  23. "---XX-X-XX---XX-X--X---XX--X-X--XXX----XX---X---X"

    {11,12,13}

    29

    Returns: "?????????????++++++++++++++++++++++++++??????????"

  24. "-X-XX---"

    {1,2,2,1,2}

    3

    Returns: "+++++++-"

  25. "X-XX-X---XXXXX-X----X------XXX"

    {11,10,10,10,11}

    25

    Returns: "++++++++++++++++++++++++++++++"

  26. "X--XX--XXX-XX-X-X-"

    {7,7,8,7,7,7,7}

    12

    Returns: "++++++++++++++++++"

  27. "-XX--"

    {2,1,2}

    3

    Returns: "+++++"

  28. "--X------XX"

    {2,1,1,1,0}

    6

    Returns: "?++++++++++"

  29. "-X--XXX-XXX-X-X-X---X---X--X--X--X"

    {14,14}

    32

    Returns: "?++++++++++++++++++++++++++++++++?"

  30. "-XX-XX-X-X---X-XX----XX-X-XXXX"

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

    5

    Returns: "??????????+++????++++?????????"

  31. "-X--XXX------XX-X-XXX-XX-XXXXXXX---X--XXX-"

    {12,15,16,16,16,16,13,15,14,16,15,14}

    24

    Returns: "??++++++++++++++++++++++++++++++++++++++++"

  32. "-X---XX--X--X-XX--X--XX-XXXX-XX-XX--"

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

    5

    Returns: "????????????????????????????????????"

  33. "XXX--X"

    {3}

    5

    Returns: "?++++?"

  34. "XXX-----XXX-XXXX--XXXXXXX--XXX-XXX-X-X---X---"

    {23,22,21}

    35

    Returns: "????????+++++++++++++++++++++++++++++++++++++"

  35. "-X--XXXX----X-XXXX"

    {3,4}

    6

    Returns: "?????????????????-"

  36. "---X-XX-XX-X"

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

    3

    Returns: "++++++++++??"

  37. "X-XX--XX--XXX-X-XXXX-XX--X-X-X---XXXX-------X--X--"

    {19,16,19,17,20,19,16,18}

    36

    Returns: "---+++++++++++++++++++++++++++++++++++++++++++++++"

  38. "-XX--X-------XX--X-X-XX-X--X-X--XX-XX-X---X-XXX-X"

    {18,17,19}

    42

    Returns: "???++++++++++++++++++++++++++++++++++++++++++++??"

  39. "--XXX--XX----X---XXX-XXXX----X-XXXX--XXXXX----X-XX"

    {21,23,22,23,23,22}

    43

    Returns: "?+++++++++++++++++++++++++++++++++++++++++++++++??"

  40. "X--------XX-X-X--XX-XXX--XX-XXXX-X-X-XX--"

    {19,19}

    38

    Returns: "??+++++++++++++++++++++++++++++++++++++??"

  41. "--X--X--X-X---X--XXX-"

    {5,6,6,5}

    14

    Returns: "-?++++++++++++++++++?"

  42. "-X---X----X--XX-XXXXX-X-X----X-XX-X-X-X----X--XX-"

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

    4

    Returns: "????????????????+++++????????????????????????????"

  43. "-XX--XXXXXX-X-X-X-X-----X--X-XX--XX---XX--X-XXXX-"

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

    4

    Returns: "??+++?++++??++++++??++++++???++++++???++++???+???"

  44. "-XX---X---XXX---XXX---X---XXXXXX-X-X-"

    {6,4,4,4,4,4}

    10

    Returns: "-????????????????????????????????----"

  45. "-X---X--XX-"

    {4,3,3}

    9

    Returns: "+++++++++++"

  46. "XXX----"

    {2,3,1}

    5

    Returns: "+++++++"

  47. "X------XX"

    {3}

    9

    Returns: "+++++++++"

  48. "XXX--X-XX----X--X-X-X-XXX"

    {5,4,6,4,4,5,7}

    12

    Returns: "???????++++++++++++++++++"

  49. "-X-XXX---XX-X--"

    {5,5,5,5}

    9

    Returns: "-++++++++++++--"

  50. "X-X------X-XX"

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

    5

    Returns: "?++++++++++?-"

  51. "-X------XXXXXX-X--XXX------XXX-"

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

    9

    Returns: "+++++++++++++++++++++++++++++++"

  52. "XX--X-XXX-X--X-XXXXXX-XX--X-XX-X--X-XXX--X-X-"

    {21}

    34

    Returns: "----??++++++++++++++++++++++++++++++++??-----"

  53. "X-X"

    {1}

    2

    Returns: "?+?"

  54. "X--X-X-XXX----X----"

    {7,6,5}

    15

    Returns: "+++++++++++++++++++"

  55. "-XX--X-X-XXXXX"

    {4,2,3}

    5

    Returns: "????+???++++?-"

  56. "XXX-XX--XX--X--XX--X--X-X--XX---X--X--"

    {6,7,6,7,6,7,7,6,6,6,7,9,8,6,7,6,7,6,9}

    16

    Returns: "+++++++++++++++++++++++++++++++++++++?"

  57. "XX-XX---XXXXX--X---XX-----XX--XX---X--XXX-XX-XXX"

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

    10

    Returns: "++++++++++++++++++++++++++++++++++++++++++++++++"

  58. "X--XX-X---XX--XX-XXXX---X---X-X---X-----"

    {14,14,12,12,14,13}

    31

    Returns: "-?+++++++++++++++++++++++++++++++++++++?"

  59. "XXXXXXXX-"

    {6,5}

    6

    Returns: "??+++++++"

  60. "--X----X--X-X--XXX----XXXXXXX-X-XXXXX-"

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

    4

    Returns: "??+++++++?+?++??????????+++???????????"

  61. "--X"

    {0}

    2

    Returns: "++-"

  62. "---"

    {0}

    2

    Returns: "?+?"

  63. "-XXXX"

    {1,1}

    1

    Returns: "-????"

  64. "-X-XX--------X-X-"

    {1,1}

    7

    Returns: "----???+++++++?--"

  65. "X---XXX-"

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

    1

    Returns: "?+++???+"

  66. "-XXXX-X-X---XXX-X---X-XXX"

    {2,3,4,5,5}

    7

    Returns: "?+++++++?????????????????"

  67. "XX--XX---X-X--"

    {2}

    6

    Returns: "--????????????"

  68. "X--X---X--XX---X----"

    {5,5,6}

    17

    Returns: "+++++++++++++++++++?"

  69. "XXXXX-X--XX-XXXX------X--X---XXX-XXXXXXX-XX-X-X-"

    {19,19,19,19}

    35

    Returns: "??????++++++++++++++++++++++++++++++++??????????"

  70. "XXX--XXXX-------XX-XX"

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

    1

    Returns: "?????????????????????"

  71. "-X---X-XX------XX-XXX-X-XX-----XX---XX-X-"

    {15,15,16,14,14}

    35

    Returns: "?+++++++++++++++++++++++++++++++++++++++?"

  72. "-X-XXXXX-X--XX-X--XXX-XXX-X-X--XX"

    {12,14,12,13,13,15}

    22

    Returns: "???++++++++++++++++++++++++++++??"

  73. "---XXXX---"

    {4,4,4}

    7

    Returns: "?++++++++?"

  74. "--X----XX---X-XXX--XX--XX"

    {7,6,8}

    14

    Returns: "--???????++++++++++++????"

  75. "XX-X-XXXX-XXXXX---XXX-X-X-XXX"

    {8,6,7,9,7,7,6,6,7,7,5,7,7,8,6}

    10

    Returns: "?+++++++++++++++++++++++++++?"

  76. "X-XXX--XXX--XXXXXX----XX---XX-X-X---"

    {9,8,6,6,10,8,9,6,9,9,6,8,8,6,11,7,9,7,10}

    15

    Returns: "?+++++++++++++++++++++++++++++++++++"

  77. "---X-XXX-XXX-X-XX-"

    {10}

    17

    Returns: "?++++++++++++++++?"

  78. "X-X----X-XX--X--XX----XX--XXX-----XXX-"

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

    2

    Returns: "??????????????????????????????????????"

  79. "X---XX--X--X-XXX--XX---XXXXX--X---X-X-X-XXXXXX---"

    {15,16,15,14,16,15,16,15,16,17,15,14,14,14,15,16,15,15,15,17}

    29

    Returns: "+++++++++++++++++++++++++++++++++++++++++++++++++"

  80. "XXXX-X--XX--X--XX-XX--X-X--X---X-XX"

    {6,5}

    13

    Returns: "--???????????????????+++++++++?????"

  81. "--X--X---XXXXXX-----XX---XX-XX-"

    {8,7,8,8,7,7,8,7,8,8,8,8}

    16

    Returns: "??+++++++++++++++++++++++++++?-"

  82. "-X--XXX--XXXXX------X--X---XXXX--XX"

    {16}

    34

    Returns: "++++++++++++++++++++++++++++++++++-"

  83. "-XX-------XX--"

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

    4

    Returns: "?++++++++++++?"

  84. "XXX-------XX-X--X-X-XXX--XX"

    {10,10,9}

    22

    Returns: "?+++++++++++++++++++++++???"

  85. "XX-X--XX--XXXX---XXX"

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

    4

    Returns: "??++++???????+++++??"

  86. "XXX---X---X-X-"

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

    7

    Returns: "-?++++++++++++"

  87. "XXXX----XXX"

    {3,4}

    4

    Returns: "++++?--????"

  88. "--XXX-XXX---XX-XX--X-X---XXXX--XX--XXXX-X-X---"

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

    9

    Returns: "????????++++++++++++++++++++++??+??++++???????"

  89. "X--X---XXXX-XXX----XX--X-XXX-XXX--XX-XX-XX--X--XX-"

    {20,20}

    37

    Returns: "???????????+++++++++++++++++++++++++++????????????"

  90. "XXX-X-XXXX-XX-X-XXX---XX--X---XXXX---X-------XXX--"

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

    12

    Returns: "+++++++++++++++++++++++++++++++++++++++++++++++++?"

  91. "XX-X-X-XX-X-XXX-X-X-X-XXXXX--X---XX---XXXXXXXXX--X"

    {16,18,17,18,19,17,19,19,18,17,18}

    30

    Returns: "???????++++++++++++++++++++++++++++++++++++++++???"

  92. "--XXX--XX-X-XXX----X-X-X--X-XXX---XX---X-XX--XXX-X"

    {6,7,5,4,7,7,6,6,6,6,6,7,6,7,5,5,8,6,6,6,6,7,7,6,7,6,9,6,8,6,5}

    13

    Returns: "?+++++++++++++++++++++++++++++++++++++++++++++++??"

  93. "--X--X--XXX--X---X-X-XX-X---X-XX-X-XXX---X--X-XX--"

    {10,12,11,10,9,10,11,10,10,10,11,11,10,10,10,11,11,9,10,11,10,12,10,10,10,10}

    22

    Returns: "??+++++++++++++++++++++++++++++++++++++++++++++++?"

  94. "XXX-XXX-XXXX----XXX-X--XX-XX--XXX--X-X---X---X-X-X"

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

    3

    Returns: "?????????++++++++??+++++???++++?+++++++++++++++++?"

  95. "--X--XXX--XX-X--XX-XX------XX--XX-XX-XXXX----XXXX-"

    {23}

    46

    Returns: "-++++++++++++++++++++++++++++++++++++++++++++++---"

  96. "--XXXX--XXXXX--X-X--X-XXXX-XXX-X-XXX-XX-X-X-XX-XX-"

    {19, 17}

    29

    Returns: "-????????????+++++++++++++++++++++++++++++????????"

  97. "----XX---XXX--X-XX-XX--XX-X--XX-X-XX--XX-XXX-XX---"

    {16,20,19,20,19,19,18,18,18}

    34

    Returns: "++++++++++++++++++++++++++++++++++++++++++++++????"

  98. "-----X-XXXXX-----X--XX-X--X----X---X--XX--X--X--X-"

    {15,15,15,13,15,16,15}

    38

    Returns: "???++++++++++++++++++++++++++++++++++++++++++????-"

  99. "XXXX----XXXX--XXXX"

    {4, 4}

    4

    Returns: "????----????--????"

  100. "-XX--X-XX-X-X--X---XX-X---XXXX-----X"

    {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 }

    7

    Returns: "???++++?++++++++++++++++++++??????--"

  101. "------X-XX-"

    {3, 0, 2, 0 }

    5

    Returns: "++++++++++?"

  102. "-XXXXX---X--"

    {2, 1, 0, 1 }

    3

    Returns: "???-??++++??"

  103. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 }

    3

    Returns: "??????????????????????????????????????????????????"

  104. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    {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, 1, 1 }

    1

    Returns: "++++++++++++++++++++++++++++++++++++++++++++++++++"

  105. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 }

    3

    Returns: "??++++++++++++++++++++++++++++++++++++++++++++++??"

  106. "XXXX"

    {4 }

    4

    Returns: "++++"

  107. "-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X"

    {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 }

    2

    Returns: "??????????????????????????????????????????????????"

  108. "-XX--X-XX-X-X--X---XX-X---XXXX-----X-XX--X-XX-X-X-"

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

    7

    Returns: "?????????+++++++++++++++++???++++++++++++?????----"

  109. "XXXXXX"

    {6 }

    6

    Returns: "++++++"

  110. "XXXXXX---X"

    {2, 5 }

    5

    Returns: "?++++++++?"

  111. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    {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: "++++++++++++++++++++++++++++++++++++++++"

  112. "XX--XX-XXX-XX--XX-XX-X---"

    {5, 7, 6, 6, 6, 5, 6, 5, 6, 7, 6, 7, 7, 6 }

    10

    Returns: "+++++++++++++++++++++++++"

  113. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    {50 }

    50

    Returns: "++++++++++++++++++++++++++++++++++++++++++++++++++"

  114. "-XXXXX-"

    {2 }

    3

    Returns: "???-???"

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: