Overview

This problem asks us to store items arriving in a different order onto shelves in the order from \(1\) to \(N\). Items that cannot be stored immediately can be temporarily placed on \(K\) holding areas (stacks). We want to find the minimum number of holding areas \(K\) required to store all items on the shelves in the correct order, using binary search and a greedy approach.

Analysis

Feasibility of Binary Search

Intuitively, we can see that having more holding areas \(K\) makes the task easier (if \(K=N\), it is always possible). In other words, there is monotonicity in the condition “is it possible to store all items with \(K\) holding areas?”. Therefore, we can use binary search to find the minimum value of \(K\).

Feasibility Check for a Specific \(K\) (Greedy Approach)

Within the binary search, we simulate the process for a specific \(K\) to determine whether all items can be stored.

Since the holding areas function as stacks (Last-In-First-Out), items that should be stored later (with larger numbers) must be placed at the bottom of the stack. Conversely, it is optimal to stack items such that their numbers increase from top to bottom in any single stack.

Consider placing item \(a\) on a stack. \(a\) will be stacked on top of the item \(t\) currently at the top of the stack. Since \(a\) must be stored before \(t\) (\(a < t\)), \(t\) must be greater than \(a\). Therefore, it is most efficient and greedily optimal to place \(a\) on the stack whose top item is “the smallest among all top items that are greater than or equal to \(a\)”.

If there is no stack whose top item is greater than or equal to \(a\), we place it in an empty stack (where the top item is considered to be \(-1\)). If there are no empty stacks either, then it is impossible with this \(K\).

Algorithm

1. Binary Search: Binary search for \(K\) in the range \(0 \le K \le N\).
2. Decision Function check(K):
   • Maintain a balanced binary search tree (such as std::set in C++) to manage the top item number of each stack. Use -1 to represent empty stacks.
   • Process each item \(a\) in order.
   • If \(a\) matches the next item number \(c\) to be stored, store it directly on the shelf and increment \(c\).
   • If it does not match, find a stack to place \(a\). Search for the smallest element greater than or equal to \(a\) in the set (using lower_bound). If found, place \(a\) on that stack. If not found, look for an empty stack. If there are no empty stacks either, return false.
   • After placing an item on a holding area or storing it directly, check if there is any stack whose top item matches \(c\). If so, pop it from the stack, store it on the shelf, and increment \(c\). Repeat this process as long as possible.
   • Finally, return true if \(c = N + 1\), and false otherwise.

Complexity

• Time Complexity: \(O(N \log^2 N)\)
  • The binary search takes \(O(\log N)\) steps.
  • In each decision step, we process \(N\) items. For each item, the operations on the set take \(O(\log K)\) time, resulting in \(O(N \log N)\) per check.
• Space Complexity: \(O(N)\)
  • The total size of the stacks and the set is proportional to \(N\).

Implementation Points

• Store pairs of {top_item_number, stack_index} in the set. This allows us to easily search for “the smallest item number greater than or equal to \(a\)” using lower_bound.

• To distinguish empty stacks, use -1 as the initial top value or when a stack becomes empty. Since item numbers are positive integers greater than or equal to \(1\), this will not cause any collisions.

• Although the problem description mentions Python code, the actual code provided is in C++. By utilizing C++’s std::set and lower_bound, the greedy selection of stacks can be performed efficiently.

  Source Code

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

bool check(int K, const vector<int>& A, int N) {
    if (K == 0) {
        int c = 1;
        for (int i = 0; i < N; i++) {
            if (A[i] == c) {
                c++;
            } else {
                return false;
            }
        }
        return c == N + 1;
    }

    vector<vector<int>> stacks(K);
    set<pair<int, int>> tops;
    for (int i = 0; i < K; i++) {
        tops.insert({-1, i});
    }

    int c = 1;
    for (int i = 0; i < N; i++) {
        int a = A[i];
        if (a == c) {
            c++;
        } else {
            auto it = tops.lower_bound({a, 0});
            if (it == tops.end()) {
                it = tops.begin();
                if (it->first != -1) return false;
            }
            int idx = it->second;
            tops.erase(it);
            stacks[idx].push_back(a);
            tops.insert({a, idx});
        }

        while (true) {
            auto it = tops.lower_bound({c, 0});
            if (it != tops.end() && it->first == c) {
                int idx = it->second;
                tops.erase(it);
                stacks[idx].pop_back();
                if (!stacks[idx].empty()) {
                    tops.insert({stacks[idx].back(), idx});
                } else {
                    tops.insert({-1, idx});
                }
                c++;
            } else {
                break;
            }
        }
    }
    return c == N + 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int low = 0, high = N;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (check(mid, A, N)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    cout << low << endl;
    return 0;
}

This editorial was generated by or-glm5.2-high.