BidirectionalQueue | Topcoder Archive

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:

Extract first element. After applying this operation, queue a₁, ..., a_K becomes a₂, ..., a_K.
Shift queue elements left. After applying this operation, queue a₁, ..., a_K becomes a₂, ..., a_K, a₁.
Shift queue elements right. After applying this operation, queue a₁, ..., a_K becomes a_K, a₁, ..., a_K-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

```
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.
```
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.
```
32
```
```
{27, 16, 30, 11, 6, 23}
```
```
Returns: 59
```

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

Returns: 14

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.