TopCoder problem "BidirectionalQueue" used in TCO09 Qual 3 (Division I Level One)



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

0)
    
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.
1)
    
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.
2)
    
32
{27, 16, 30, 11, 6, 23}
Returns: 59
3)
    
10
{1, 6, 3, 2, 7, 9, 8, 4, 10, 5}
Returns: 14

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10331

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13758&pm=10331

Writer:

Nickolas

Testers:

PabloGilberto , vorthys , ivan_metelsky

Problem categories:

Simulation