Learn C++ STL

Lesson 6 of 9 · array and deque: Fixed Size, and Growing at Both Ends

Module 4 · array and deque: Fixed Size, and Growing at Both Ends

CP and Interview Pack: array and deque Patterns, Questions and the Bug Gallery

ProReading

Codeforces Round 569 opened its Div. 1 set with problem 1179A, "Valeriy and Deque" (1180C in Div. 2). A deque holds n numbers. One operation takes the first two, A and B, and puts the larger back at the front and the smaller at the back. Each query asks which pair the m-th operation takes, and m can be far larger than any loop can reach. Bob simulates every step; Amara simulates only n - 1, and her whole solution is pattern 1 below.

Checking what this lesson needs for you…

What is inside CP and Interview Pack: array and deque Patterns, Questions and the Bug Gallery

  1. Pattern 1: a queue simulation
  2. Pattern 2: a circular buffer on an array
  3. Pattern 3: rotation, and the k % n shortcut
  4. Pattern 4: both-ends greedy
  5. Pattern 5: the reverse flag
  6. Two deque patterns that later modules finish
  7. Eight interview questions, with model answers
CP and Interview Pack: array and deque Patterns, Questions and the Bug Gallery | Learn C++ STL | Progsity