Statistics

Problem Statement for "BidirectionalQueue"

Problem Statement

You are given a bidirectional cyclical queue which contains N elements. You need to extract several elements from this queue.
You can do 3 kinds of operations with this queue:
  1. Extract first element. After applying this operation, queue a1, ..., aK becomes a2, ..., aK.
  2. Shift queue elements left. After applying this operation, queue a1, ..., aK becomes a2, ..., aK, a1.
  3. Shift queue elements right. After applying this operation, queue a1, ..., aK becomes aK, a1, ..., aK-1.
You are given the initial number of elements in the queue N and a int[] indices which contains the initial (1-based) positions of wanted elements in the queue. Return the minimal number of left and right shifts you'll have to perform to extract the wanted elements in the given order.

Definition

Class:
BidirectionalQueue
Method:
extractElements
Parameters:
int, int[]
Returns:
int
Method signature:
int extractElements(int N, int[] indices)
(be sure your method is public)

Constraints

  • N will be between 1 and 50, inclusive.
  • indices will contain between 1 and N elements, inclusive.
  • Each element of indices will be between 1 and N, inclusive.
  • All elements of indices will be distinct.

Examples

  1. 10

    {1, 2, 3}

    Returns: 0

    The elements are extracted in the same order as they appear in the queue, so no shifts are required.

  2. 10

    {2, 9, 5}

    Returns: 8

    To extract the first wanted element, 1 left shift is required. After this the next wanted element will be 7th in a queue with 9 elements, so to extract it 3 right shifts are required. Finally, the last wanted element will be 5th in a queue with 8 elements, so either 4 left shifts or 4 right shifts are required.

  3. 50

    {26, 1, 27, 2, 28, 3, 29, 4, 30, 5, 31, 6, 32, 7, 33, 8, 34, 9, 35, 10, 36, 11, 37, 12, 38, 13, 39, 14, 40, 15, 41, 16, 42, 17, 43, 18, 44, 19, 45, 20, 46, 21, 47, 22, 48, 23, 49, 24, 50, 25}

    Returns: 625

  4. 1

    {1}

    Returns: 0

  5. 32

    {27, 16, 30, 11, 6, 23}

    Returns: 59

  6. 39

    {14,4,20,37,9,16,32,13,10,39,22,1,2,5,11,35,18,25,31,15,28,33,7,36,8,30,17,12,19,3,26,38,29,23}

    Returns: 220

  7. 19

    {12,15,10,7,1,19,9,8,6,2,4,18,13,16,14,17}

    Returns: 44

  8. 27

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

    Returns: 89

  9. 28

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

    Returns: 105

  10. 10

    {6,1,8,9,4,5,3}

    Returns: 16

  11. 33

    {18,25,2,28,8,26,22,9,30,27,1,29,14,10,21,13,20,33,15,19,5,3,23,31,32,12,7,11,24}

    Returns: 162

  12. 28

    {23,28,17,1,9,8,7,16,26,5,22,10,19,12,20,14,18,13,24,6,21,2,4}

    Returns: 101

  13. 49

    {37,33,31,14,13,21,28,20,40,3,24,46,29,11,23,1,41,26,48}

    Returns: 191

  14. 29

    {15,8,14,23,25,12,26,11,17}

    Returns: 65

  15. 48

    {47,21,35,5,40,39,19,18,25,16,15,4,6,28,33,31,9,8,22,20,36,32,30,29,14,44,34,1,27,17,42,48,46,7}

    Returns: 218

  16. 32

    {5,12,15,8,29,19,21,10,30,23,2,31}

    Returns: 74

  17. 7

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

    Returns: 7

  18. 32

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

    Returns: 120

  19. 25

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

    Returns: 100

  20. 37

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

    Returns: 217

  21. 41

    {7,17,4,12,20,28,32,27,40,35,5,18,2,34,6,23,15,22,31,1,24,13,29,36}

    Returns: 163

  22. 15

    {11,4,13,3,14,1,9,7,8,10,15}

    Returns: 34

  23. 8

    {2,6}

    Returns: 4

  24. 15

    {5,12,11,8,6,7,9,14,4,10}

    Returns: 21

  25. 32

    {25,32,1,15,19}

    Returns: 30

  26. 40

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

    Returns: 247

  27. 4

    {1,3}

    Returns: 1

  28. 47

    {4,13,10,32,38,36,16,41,1,25,29,3,34,28,43,20,19,46,27,23,6,35}

    Returns: 212

  29. 8

    {4,1,7,6}

    Returns: 9

  30. 39

    {35,19,28,37,18,33,5,31,16}

    Returns: 94

  31. 9

    {4,3,1,2}

    Returns: 6

  32. 37

    {36,9,8,6,5,22,2,20}

    Returns: 56

  33. 46

    {38,30,3,32,34,42,23,31,17,37,11,26,7,1,22,36,21,35,33,28,27,39,29,40,12,2,46,15,24,45}

    Returns: 230

  34. 36

    {27,22,19,35,33,25,11,9,3,34,26,23,13,21,4,5}

    Returns: 95

  35. 28

    {15,14,12,17,8,1,4}

    Returns: 34

  36. 23

    {21,14,13,19,23,22,5,7}

    Returns: 23

  37. 15

    {5,11,1,7,4,15}

    Returns: 22

  38. 31

    {4,29,19,27,10,5,7,25,16,23,18,30,24,28,3}

    Returns: 82

  39. 28

    {6,14,25,21,4,7,17,15,13,27,8,23}

    Returns: 68

  40. 32

    {5,16}

    Returns: 14

  41. 17

    {10,15,1,5,9,3,14}

    Returns: 29

  42. 23

    {1,14,13,12,18,23,7,16,5,3,17,10,20,8,19,22}

    Returns: 59

  43. 12

    {3,10,7,2,4,8,6,12,9,11,5,1}

    Returns: 22

  44. 47

    {38,12,44,43,7,26,20,11,3,14,6}

    Returns: 105

  45. 50

    {9,34,39,33,40,31,48,25,13,12,45,23,17,4,50,6,47,32,36,38,19,27,16,30,49,21,14,24,44,29,46,2,11,20,22,18,35,42,37,5,26}

    Returns: 268

  46. 47

    {5,41,22,11,31,8,29,21,16,30,44,9,15,6,3,37}

    Returns: 167

  47. 3

    {3,1,2}

    Returns: 1

  48. 5

    {1,3,4}

    Returns: 1

  49. 23

    {16}

    Returns: 8

  50. 46

    {10,3,15,41,24,16,17,36,4,9,26,45,14,13,32,44,33,2,18,7,46,38,30,5,11,31,1,25,42,23,40,27,20,39,43,37,8,34,19}

    Returns: 286

  51. 10

    {7,4,6,10}

    Returns: 10

  52. 26

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

    Returns: 76

  53. 27

    {13,15,18,24,16,2,26,5,8,7,6,1,23,10,4,25,22,19,9,20,12,3}

    Returns: 81

  54. 22

    {5,16,9,21,18,6}

    Returns: 40

  55. 47

    {10,28,16,13,27,22,3,46,25,24,7,37,15,12,33,31,29,40,36,38,34,6,39,4,47,32,26,18,43,42,2,30,5,17,44,1,20,35,8,41,21,45,23,9,19,11,14}

    Returns: 270

  56. 23

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

    Returns: 61

  57. 27

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

    Returns: 96

  58. 10

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

    Returns: 14

  59. 28

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

    Returns: 90

  60. 18

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

    Returns: 39

  61. 24

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

    Returns: 91

  62. 22

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

    Returns: 66

  63. 25

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

    Returns: 82

  64. 50

    {29,4,6,8,40,27,15,41,18,36,42,16,44,38,24,50,17,3,32,37,20,10,25,35,49,48,39,9,26,14,2,23,13,43,21,45,11,30,47,33,22,34,31,7,5,46,28,12,1,19}

    Returns: 387

  65. 18

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

    Returns: 39

  66. 50

    {19,50,49,41,3,1,7,6,13,12,48,8,32,33,18,22,36,24,2,23,35,16,45,37,39,21,40,5,47,11,27,14,20,29,9,46,15,43,34,4,28,26,44,10,31,25,38,17,30,42}

    Returns: 279

  67. 22

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

    Returns: 60

  68. 26

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

    Returns: 97

  69. 44

    {21,28,43,26,20,44,6,30,40,23,7,33,37,32,14,24,25,3,34,10,4,27,18,11,31,17,19,2,38,16,8,15,35,22,36,39,13,5,42,12,41,9,29,1}

    Returns: 290

  70. 34

    {10,5,18,4,33,27,26,31,34,16,17,15,3,30,14,2,12,6,7,29,13,1,20,8,23,25,9,32,24,19,28,22,11,21}

    Returns: 143

  71. 21

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

    Returns: 56

  72. 25

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

    Returns: 94

  73. 28

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

    Returns: 114

  74. 50

    {15,3,35,7,28,22,5,46,38,45,17,48,18,37,42,1,50,36,25,39,24,2,13,19,43,9,12,8,10,49,21,31,6,33,47,29,23,20,11,32,4,40,16,14,41,34,44,27,30,26}

    Returns: 343

  75. 4

    {4,3,1,2}

    Returns: 2

  76. 11

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

    Returns: 14

  77. 2

    {1,2}

    Returns: 0

  78. 31

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

    Returns: 105

  79. 38

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

    Returns: 192

  80. 32

    {27, 16, 30, 11, 6, 23 }

    Returns: 59

  81. 10

    {2, 9, 5 }

    Returns: 8

  82. 3

    {3, 2, 1 }

    Returns: 2

  83. 10

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

    Returns: 14

  84. 32

    {27, 16, 30, 15, 6, 23 }

    Returns: 64

  85. 50

    {23, 31, 24, 12, 13, 1, 2, 49, 48 }

    Returns: 61

  86. 32

    {27, 16, 30, 11, 6, 26 }

    Returns: 56

  87. 50

    {24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 6, 5, 3, 2, 40, 45, 33, 32, 31 }

    Returns: 74

  88. 22

    {16, 14, 17, 7, 22, 21, 11, 2, 12, 3, 9, 20, 1, 19, 4, 18, 15, 13, 5, 10 }

    Returns: 67

  89. 50

    {50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

    Returns: 49

  90. 50

    {25, 1, 26, 50, 24, 2, 27, 3, 28, 30, 5, 33, 21, 31, 41, 15, 44, 12, 40, 13, 23, 6, 45, 7 }

    Returns: 361

  91. 5

    {2 }

    Returns: 1

  92. 10

    {1, 2, 3 }

    Returns: 0

  93. 50

    {40, 36, 45, 26, 49, 25, 27, 9, 8, 43, 38, 33, 23, 12, 41, 39, 5, 11, 7, 18, 19, 10, 1, 28, 13, 16, 50, 34, 44, 20, 14, 47, 46, 37, 24, 42, 6, 22, 2, 4, 35, 15, 30, 29, 21, 32, 31, 17, 48, 3 }

    Returns: 285

  94. 50

    {1, 50, 2, 30, 41, 17, 49, 6, 7, 8, 32, 15 }

    Returns: 105

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: