Hello Codeforces,

In this blog, I want to discuss a technique I devised while solving the problem ABC392F Insert. Although I couldn't solve it during the contest due to time constraints, I later implemented a solution with the help of ChatGPT and it received AC. (I do feel the test cases are weak and a solution like this might not pass on tougher tests.) The editorial mentioned PBDS as a faster alternative.

Anyhow, I'm curious if you have seen this idea before, please share the relevant links and acknowledge the original source. Your feedback and insights are very welcome!

Problem Statement

Given n integers, insert them at their respective positions in the array built so far.

For i = 1, 2, …, n, perform the following operation in order: - Insert the number i into the array A so that it becomes the P[i]-th element from the beginning.
In other words, replace A with the concatenation of: 1. The first P[i] — 1 elements of A 2. The number i 3. The remaining elements of A starting from the P[i]-th element

Constraints: - 1 ≤ n ≤ 5×10^5 - 1 ≤ P[i] ≤ i - All input values are integers.

Approach: √n Decomposition

The main idea is to maintain the evolving array A as a list of blocks (vectors) where each block has roughly O(√n) elements. This allows for efficient arbitrary insertions:

• Insertion:
  For each number, determine the block and the exact position within that block by subtracting block sizes until the position is found. This takes O(√n) time per insertion.

• Balancing:
  After each insertion, check if a block's size reaches 2 × √n. If so, split the block into two to maintain the block sizes around O(√n), ensuring subsequent insertions remain efficient.

• Overall Complexity:
  With n insertions each taking O(√n), the total time complexity is O(n√n).

Code

Submission link, AC

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> arr;
    const int blk = max(1, (int)sqrt(n));
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        x--;  // Convert to 0-indexed

        int b = 0;
        if (i == x) {
            if (arr.empty()) {
                arr.push_back({ i + 1 });
            } else {
                b = arr.size() - 1;
                arr[b].push_back(x + 1);
            }
        } else {
            while (x > arr[b].size()) {
                x -= arr[b].size();
                b++;
            }
            arr[b].insert(arr[b].begin() + x, i + 1);
        }

        if (arr[b].size() == 2 * blk) {
            vector<int> t(arr[b].begin() + blk, arr[b].end());
            arr[b].resize(blk);
            arr.insert(arr.begin() + b + 1, t);
        }
    }
    for (auto& block : arr)
        for (int num : block)
            cout << num << " ";
    cout << "\n";
}