Statistics

Problem Statement for "RotatingBot"

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

We had a rectangular grid that consisted of W x H square cells. We placed a robot on one of the cells. The robot then followed the rules given below.
  • Initially, the robot is facing east.
  • The robot moves in steps. In each step it moves to the adjacent cell in the direction it currently faces.
  • The robot may not leave the grid.
  • The robot may not visit the same cell twice. (This also means that it may not reenter the starting cell.)
  • If a step forward does not cause the robot to break the above rules, the robot takes the step.
  • Otherwise, the robot rotates 90 degrees to the left (counter-clockwise) and checks whether a step forward still breaks the above rules. If not, the robot takes the step and continues executing this program (still rotated in the new direction).
  • If the rotation left did not help, the robot terminates the execution of this program.
  • We can also terminate the execution of the program manually, at any moment.
For example, the following seven images show a series of moves made by the robot in a 12 x 11 board:



We forgot the dimensions of the grid and the original (x,y) coordinates of the cell on which the robot was originally placed, but we do remember its movement. You are given a int[] moves. This sequence of positive integers shall be interpreted as follows: The robot performed moves[0] steps eastwards, turned left, performed moves[1] steps northwards, turned left, and so on. After performing the last sequence of steps, the robot stopped. (Either it detected that it should terminate, or we stopped it manually.) We are not sure if the sequence of moves is valid. If the sequence of moves is impossible, return -1. Else, return the minimum area of a grid in which the sequence of moves is possible. (I.e., the return value is the smallest possible value of the product of W and H.).

Definition

Class:
RotatingBot
Method:
minArea
Parameters:
int[]
Returns:
int
Method signature:
int minArea(int[] moves)
(be sure your method is public)

Constraints

  • moves will contain between 1 and 50 elements, inclusive.
  • Each element of moves will be between 1 and 50, inclusive.

Examples

  1. {15}

    Returns: 16

    The smallest valid board is a 16x1 board, with the robot starting on the west end of the board.

  2. {3,10}

    Returns: 44

    The smallest solution is to place the robot into the southwest corner of a 4 x 11 board.

  3. {1,1,1,1}

    Returns: -1

    This sequence of moves is not possible because the robot would return to its initial location which is forbidden.

  4. {9,5,11,10,11,4,10}

    Returns: 132

    These moves match the image from the problem statement.

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

    Returns: -1

  6. {47}

    Returns: 48

  7. {13,5,17,6,17}

    Returns: 126

  8. {3,1,34,1,30}

    Returns: 70

  9. {17,3,18,16,18,12,17,11,16,10,15,9,14,8,13,7,12,6,11,5,10,4,9,3,8,2,7,1,6}

    Returns: 323

  10. {8,8,12,38,12,29,11,28,10,27,9,26,8,25,7,24,6,23,5,22,4,21,3,20,2}

    Returns: 507

  11. {2,1,48,13,48,11}

    Returns: 686

  12. {12,1,27,14,27,12,26,11,25,10,24,9,23,8,22,7,21,6,20,5,19,4,18,3,17,2,16,1,15}

    Returns: 420

  13. {6}

    Returns: 7

  14. {31,14,36,23,36,8,35,7,34,6,33,5,32,4,31,3,30,2,29,1,28}

    Returns: 888

  15. {11,2,46,15,46,12,45,11}

    Returns: 752

  16. {1,10,8,21,8,10,7,9,6,8,5,7,4,6,3,5,2,4}

    Returns: 198

  17. {10,3,12,4,12}

    Returns: 65

  18. {6,20,40,37,40,16,39,15,38,14,37,13,36,12,35,11,34,10,33,9,32,8,31,7,30,6,29,5,28,4,27,3,26,2,25,1}

    Returns: 1558

  19. {13,27,27,34,27,6,26,5,25,4,24,3,23,2,22,1,21}

    Returns: 980

  20. {14,4,38,31,38,26,37,25,36,24,35,23,34,22,33,21,32,20,31,19,30,18,29,17,28,16,27,15,26,14,25,13,24,12,23,11,22,10,21,9,20,8,19,7,18}

    Returns: 1248

  21. {12,18,22,19,22}

    Returns: 460

  22. {6,5,10,17,10,11,9,10,8,9,7,8,6,7,5,6,4,5,3,4,2,3,1,2}

    Returns: 198

  23. {21,13,26,43,26,29,25,28,24,27,23,26,22,25,21,24,20,23,19,22,18,21,17,20,16,19,15,18,14,17,13,16,12,15,11,14,10,13,9}

    Returns: 1188

  24. {27,10,44,49,44,38,43,37,42,36,41,35,40,34,39,33,38}

    Returns: 2250

  25. {19}

    Returns: 20

  26. {10,1,10}

    Returns: 22

  27. {23,4,42,23,42,18,41,17,40}

    Returns: 1032

  28. {21,10,28,14,28,3,27,2,26,1,25}

    Returns: 435

  29. {7,33,16,35,16,1,15}

    Returns: 612

  30. {12,12,23,15,23,2,22,1,21}

    Returns: 384

  31. {6,17,24,23,24,5,23,4,22,3,21,2,20,1,19}

    Returns: 600

  32. {14,7,19,8,19}

    Returns: 180

  33. {1,36,39,37,39}

    Returns: 1520

  34. {7,2,8,14,8,11,7,10,6,9,5,8,4,7,3,6,2,5}

    Returns: 135

  35. {35,11,41,23,41,11,40,10,39,9,38,8,37,7,36,6,35,5,34,4,33,3,32,2,31}

    Returns: 1008

  36. {14}

    Returns: 15

  37. {13,5,17,6,17}

    Returns: 126

  38. {3,1,34,1,30}

    Returns: 70

  39. {17,3,18,16,18,12,17,11,16,10,15,9,14,8,13,7,12,6,11,5,10,4,9,3,8,2,7,1,6}

    Returns: 323

  40. {8,8,12,38,12,29,11,28,10,27,9,26,8,25,7,24,6,23,5,22,4,21,3,20,2}

    Returns: 507

  41. {2,1,48,13,48,11}

    Returns: 686

  42. {12,1,27,14,27,12,26,11,25,10,24,9,23,8,22,7,21,6,20,5,19,4,18,3,17,2,16,1,15}

    Returns: 420

  43. {6}

    Returns: 7

  44. {31,14,36,23,36,8,35,7,34,6,33,5,32,4,31,3,30,2,29,1,28}

    Returns: 888

  45. {11,2,46,15,46,12,45,11}

    Returns: 752

  46. {1,10,8,21,8,10,7,9,6,8,5,7,4,6,3,5,2,4}

    Returns: 198

  47. {10,3,12,4,12}

    Returns: 65

  48. {6,20,40,37,40,16,39,15,38,14,37,13,36,12,35,11,34,10,33,9,32,8,31,7,30,6,29,5,28,4,27,3,26,2,25,1}

    Returns: 1558

  49. {13,27,27,34,27,6,26,5,25,4,24,3,23,2,22,1,21}

    Returns: 980

  50. {14,4,38,31,38,26,37,25,36,24,35,23,34,22,33,21,32,20,31,19,30,18,29,17,28,16,27,15,26,14,25,13,24,12,23,11,22,10,21,9,20,8,19,7,18}

    Returns: 1248

  51. {12,18,22,19,22}

    Returns: 460

  52. {6,5,10,17,10,11,9,10,8,9,7,8,6,7,5,6,4,5,3,4,2,3,1,2}

    Returns: 198

  53. {21,13,26,43,26,29,25,28,24,27,23,26,22,25,21,24,20,23,19,22,18,21,17,20,16,19,15,18,14,17,13,16,12,15,11,14,10,13,9}

    Returns: 1188

  54. {27,10,44,49,44,38,43,37,42,36,41,35,40,34,39,33,38}

    Returns: 2250

  55. {19}

    Returns: 20

  56. {10,1,10}

    Returns: 22

  57. {23,4,42,23,42,18,41,17,40}

    Returns: 1032

  58. {21,10,28,14,28,3,27,2,26,1,25}

    Returns: 435

  59. {7,33,16,35,16,1,15}

    Returns: 612

  60. {12,12,23,15,23,2,22,1,21}

    Returns: 384

  61. {6,17,24,23,24,5,23,4,22,3,21,2,20,1,19}

    Returns: 600

  62. {14,7,19,8,19}

    Returns: 180

  63. {1,36,39,37,39}

    Returns: 1520

  64. {7,2,8,14,8,11,7,10,6,9,5,8,4,7,3,6,2,5}

    Returns: 135

  65. {35,11,41,23,41,11,40,10,39,9,38,8,37,7,36,6,35,5,34,4,33,3,32,2,31}

    Returns: 1008

  66. {14}

    Returns: 15

  67. {4,22,16,27,15,4,14,3,13,2,12,1,11}

    Returns: -1

  68. {18,2,41,30,40,27}

    Returns: -1

  69. {8,23,11,34,11,10,10,9,10,8}

    Returns: -1

  70. {10,2,16,5,16,1,15}

    Returns: -1

  71. {7,7,11,8,10}

    Returns: 108

  72. {2,27,2,25,1,24}

    Returns: -1

  73. {6,9,15,14,15,4,14,3,13,2,12,1,12}

    Returns: -1

  74. {12,11,22,14,22,2,21,1,20}

    Returns: 345

  75. {24,22,36,24,36}

    Returns: 925

  76. {17,17,19,24,19,6,18,5,17,4,16,3,14,2,14,1,13}

    Returns: -1

  77. {1,30,14}

    Returns: 465

  78. {3,15,43,21,43,5,42,4,41,3,40,3,39,1,38}

    Returns: -1

  79. {29,15,48,41,47,25,46,24,45,23,44,22,43,21,42,20}

    Returns: -1

  80. {8,29,16,44,16,14,15,13,14,12,13,11,12,10,11,9,10,8,9,7,8,6,7,5,6,4,5,3,3,2,3,1,2}

    Returns: -1

  81. {35,8,40,11,40,3,39,2,38,1,37}

    Returns: -1

  82. {8}

    Returns: 9

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

    Returns: -1

  84. {2,3,14,16,14,12,13,11,12,10,11,9,10,8,9,7,8,6,7,5,7,4,5,3}

    Returns: -1

  85. {3,4,49,4,49}

    Returns: -1

  86. {6,5,13,13,13,7,12,6,12,5,10,4,9,3,8,2,7,1,6}

    Returns: -1

  87. {3,35,10,35,6,34,5,33,5,32,3,31,2,30,1,29}

    Returns: -1

  88. {11,7,11,6,10,5,9,4,8,3,7,2,6,2,5}

    Returns: -1

  89. {21,5,27,21,27,14,26,13}

    Returns: -1

  90. {11,40,16,46,16,4,15,4,14,3,13,2,12,1,11}

    Returns: -1

  91. {18,17,32,34,32,16,31,15,30,13,29,13,28,12,27}

    Returns: -1

  92. {14,3,24,15,24}

    Returns: 400

  93. {16,31,31,36,31,4,30,3,28,2,28,1,27}

    Returns: -1

  94. {20}

    Returns: 21

  95. {2,3,4,10,3,6}

    Returns: -1

  96. {1}

    Returns: 2

  97. {50,50,50,49}

    Returns: 2601

  98. {8,6,6,1}

    Returns: -1

  99. {8,6,6}

    Returns: 63

  100. {5,4,5,3,3}

    Returns: 30

  101. {4,5,4,4,3,2}

    Returns: 30

  102. {9,6,9,5,8}

    Returns: 70

  103. {3,3,3,2,2}

    Returns: 16

  104. {1,4,3,4,1,2}

    Returns: 20

  105. {4,3,4,2,1}

    Returns: 20

  106. {8, 6, 6, 1 }

    Returns: -1

  107. {50, 50, 50, 49, 1, 48, 48, 48, 47, 1, 46, 46, 46, 45, 1, 44, 44, 44, 43, 1, 42, 42, 42, 41, 1, 40, 40, 40, 39, 1, 38, 38, 38, 37, 1, 36, 36, 36, 35, 1, 34, 34, 34, 33, 1, 32, 32, 32, 31, 1 }

    Returns: -1

  108. {20, 5, 30, 5, 10 }

    Returns: -1

  109. {12, 1, 27, 14, 27, 12, 26, 11, 25, 10, 24, 9, 23, 8, 22, 7, 21, 6, 20, 5, 19, 4, 18, 3, 17, 2, 16, 1, 15 }

    Returns: 420

  110. {8, 6, 6 }

    Returns: 63

  111. {15 }

    Returns: 16

  112. {10, 5, 12, 2, 3 }

    Returns: -1

  113. {1, 2, 3, 4, 5 }

    Returns: -1

  114. {10, 10, 7, 2, 3 }

    Returns: -1

  115. {1, 1, 2, 2, 3 }

    Returns: -1

  116. {3, 4, 1 }

    Returns: 20

  117. {5, 4, 2, 1 }

    Returns: -1

  118. {1, 1, 2, 2, 4 }

    Returns: -1

  119. {9, 8, 9, 6, 3 }

    Returns: -1

  120. {50, 50 }

    Returns: 2601

  121. {2, 2, 1, 1 }

    Returns: -1

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

    Returns: -1

  123. {2, 4, 4, 8, 10 }

    Returns: -1

  124. {5, 4, 5, 3, 3 }

    Returns: 30

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

    Returns: -1

  126. {10, 5, 20, 10, 30 }

    Returns: -1

  127. {2, 2, 3, 3, 1, 1 }

    Returns: -1

  128. {9, 5, 11, 10, 11, 4, 10, 4 }

    Returns: -1

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

    Returns: -1

  130. {5, 5, 2, 1 }

    Returns: -1

  131. {5, 5, 10, 10, 20 }

    Returns: -1

  132. {1, 1, 2, 3, 5 }

    Returns: -1

  133. {50, 1, 1, 1, 50, 1, 1, 1, 50 }

    Returns: -1

  134. {10, 10, 5, 5, 1 }

    Returns: -1

  135. {1, 1, 50 }

    Returns: 102

  136. {50, 50, 49, 1 }

    Returns: -1

  137. {8, 6, 9, 4, 2 }

    Returns: -1

  138. {8, 6, 6, 2 }

    Returns: -1

  139. {1, 1, 2, 2, 2, 2 }

    Returns: -1

  140. {3, 2, 2, 2 }

    Returns: -1

  141. {1, 1 }

    Returns: 4

  142. {8, 6, 8, 4, 1 }

    Returns: -1

  143. {2, 2, 3, 4, 6, 4 }

    Returns: -1

  144. {9, 5, 11, 10, 12, 8 }

    Returns: -1

  145. {4, 10, 2, 1 }

    Returns: -1

  146. {1, 1, 2, 2, 1, 1 }

    Returns: -1

  147. {5, 4, 10, 40, 12 }

    Returns: -1

  148. {2, 1, 3, 3, 1, 1 }

    Returns: -1

  149. {16, 8, 7, 4, 3 }

    Returns: -1

  150. {1, 1, 2, 2, 10 }

    Returns: -1

  151. {9, 5, 11, 10, 16, 4, 10 }

    Returns: -1

  152. {5, 5, 2 }

    Returns: 36

  153. {10, 5, 15, 20 }

    Returns: 336

  154. {5, 4, 5, 3, 4, 2, 2, 1, 1 }

    Returns: -1

  155. {2, 1, 4, 5, 10 }

    Returns: -1

  156. {6, 6, 8, 1 }

    Returns: 63

  157. {6, 6, 6, 1 }

    Returns: 49

  158. {1, 5, 10, 20, 50 }

    Returns: -1

  159. {1, 1, 2, 2, 3, 3 }

    Returns: -1

  160. {1, 1, 2, 2, 3, 2 }

    Returns: -1

  161. {2, 2, 3, 1, 1 }

    Returns: -1

  162. {9, 5, 11, 10, 11, 3, 9 }

    Returns: -1

  163. {1, 2, 1, 1 }

    Returns: 6

  164. {2, 3, 4, 5, 5, 5 }

    Returns: -1

  165. {2, 2, 4, 2, 1, 1 }

    Returns: 15

  166. {5, 5, 10, 2 }

    Returns: 66

  167. {1, 2, 50 }

    Returns: 153

  168. {8, 6, 8, 1 }

    Returns: 63

  169. {20 }

    Returns: 21

  170. {5, 10, 5 }

    Returns: 66

  171. {4, 2, 10, 6, 50 }

    Returns: -1

  172. {50, 50, 50 }

    Returns: 2601

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

    Returns: -1

  174. {1, 2, 3, 2, 1, 1, 1 }

    Returns: -1

  175. {1, 1, 2, 5, 2, 1, 1 }

    Returns: -1

  176. {1, 1, 5, 5, 1, 1 }

    Returns: -1

  177. {2, 1, 3, 2, 4 }

    Returns: -1

  178. {5, 4, 5, 2, 1 }

    Returns: -1

  179. {1, 2, 4, 3, 5 }

    Returns: -1

  180. {10, 2, 50, 10, 1, 1 }

    Returns: -1

  181. {4, 3, 5, 2, 3, 1 }

    Returns: -1

  182. {10, 3, 1, 1 }

    Returns: -1

  183. {8, 10, 20, 13, 2 }

    Returns: 294

  184. {2, 2, 3, 3, 4 }

    Returns: -1

  185. {6, 6, 10, 12, 35 }

    Returns: -1

  186. {9, 5, 11, 10, 16, 4 }

    Returns: -1

  187. {1, 1, 3, 3, 10 }

    Returns: -1

  188. {2, 2, 4, 4, 6, 6 }

    Returns: -1

  189. {6, 6, 6, 4, 4, 2, 2 }

    Returns: -1

  190. {3, 5, 5, 5, 1 }

    Returns: 36

  191. {10, 10, 20, 20, 1, 1 }

    Returns: -1

  192. {2, 1, 3, 3, 2, 1 }

    Returns: -1

  193. {3, 1, 4, 4, 4, 2, 3, 1, 1 }

    Returns: 25

  194. {10, 20, 20, 10, 10 }

    Returns: -1

  195. {1, 2, 2, 1, 1 }

    Returns: -1

  196. {5, 5, 6, 1, 4 }

    Returns: -1

  197. {5, 5, 3, 2 }

    Returns: -1

  198. {2, 1, 1 }

    Returns: 6

  199. {1, 2, 4, 8, 16, 32 }

    Returns: -1

  200. {8, 6, 8, 5, 2, 4 }

    Returns: -1

  201. {3, 3, 3, 1, 1 }

    Returns: -1

  202. {10, 10, 10, 9, 9, 6, 3 }

    Returns: -1

  203. {9, 5, 11, 10, 11, 4, 9, 2 }

    Returns: -1

  204. {1, 1, 2, 2, 3, 3, 4, 4 }

    Returns: -1

  205. {1, 1, 1, 1 }

    Returns: -1

  206. {9, 2, 8, 6 }

    Returns: -1

  207. {10, 5, 15, 20, 25 }

    Returns: -1

  208. {2, 2, 2, 1, 1 }

    Returns: 9

  209. {2, 2, 3, 2, 2 }

    Returns: -1

  210. {9, 5, 11, 10, 11, 4, 10 }

    Returns: 132

  211. {48, 49, 50 }

    Returns: 2550

  212. {5, 2, 6, 1, 1 }

    Returns: -1

  213. {2, 2, 4, 4, 4, 1, 3, 2 }

    Returns: -1

  214. {6, 6, 6, 5, 5, 3, 1 }

    Returns: -1

  215. {1, 1, 2, 1, 1 }

    Returns: -1

  216. {10, 20, 30, 40, 50 }

    Returns: -1

  217. {4, 1, 7, 1, 6 }

    Returns: -1

  218. {10, 5, 10, 4, 9, 3, 5 }

    Returns: 66

  219. {1, 1, 2, 2, 3, 4, 4, 6, 6, 9, 6, 2, 5, 1, 4 }

    Returns: -1

  220. {2, 2, 3 }

    Returns: 12

  221. {5, 4, 5, 3 }

    Returns: 30

  222. {8, 8, 6, 1 }

    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: