Connection Status:
Competition Arena > BidirectionalQueue

BidirectionalQueue

TCO09 Qual 3 · 2009-02-24 · by Nickolas

TCO09 Qual 3 · 2009-02-24 · by Nickolas · Simulation
Class Name: BidirectionalQueue
Return Type: int
Method Name: extractElements
Arg Types: (int, vector<int>)
Problem Statement

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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

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)
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
3)
1
{1}
Returns: 0
4)
32
{27, 16, 30, 11, 6, 23}
Returns: 59

Submissions are judged against all 94 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BidirectionalQueue with a public method int extractElements(int N, vector<int> indices) · 94 test cases · 2 s / 256 MB per case

Submitting as anonymous