CF 1531E2 - Сортировка слиянием

CF 1531E2 - \u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c

Rating: -
Tags: *special, brute force
Solve time: 3m 39s
Verified: no

Solution

Problem Understanding

We are given a string consisting of 0s and 1s, which represents the sequence of decisions made during the merge steps of a merge sort on some permutation of integers from 1 to n. Specifically, a 0 indicates that the element from the left half was taken first, while a 1 indicates that the element from the right half was taken first. Our task is to reconstruct any permutation of 1 to n such that, when we run merge sort on it, we get exactly that sequence of 0s and 1s.

The input string s encodes the relative ordering decisions, but it does not directly tell us n. We must infer a valid n that allows the merge sort on a permutation of length n to produce exactly this sequence. Since merge sort always divides the array into halves recursively, the number of merge operations is structured according to powers of two: a length n array produces a total of n-1 comparisons in the merge process if n is a power of two.

The key constraint is that the string s can always be matched by some permutation of length ≤ 1000. This implies that a brute-force approach to check all permutations is impossible for larger n, but we can construct a solution recursively by thinking about how merge sort consumes 0s and 1s.

Edge cases include sequences that are all 0s or all 1s. For a sequence of all 0s, the array must be increasing because we always pick from the left first. For all 1s, it must be decreasing. Any naive approach that just outputs the first n integers in order may fail for mixed sequences if we don’t respect the division of elements by merge sort.

Approaches

The brute-force approach would generate all permutations of size n and simulate merge sort for each one to see if the resulting log matches s. This works because merge sort is deterministic, and the comparison decisions are fully defined by the array. However, the number of permutations grows factorially, O(n!), and simulating merge sort for each permutation costs O(n log n), making this approach infeasible even for n=10.

The key insight is that we do not need the exact values in the array during construction. We only need a sequence that respects the comparison decisions encoded in s. Merge sort is stable with respect to order within equal-size subarrays, so we can recursively split the array, assign ranges of consecutive integers to the left and right halves, and consume the log string s to guide the construction. At each merge step, the next characters of s tell us which half contributes the next element. This reduces the problem from factorial search to linear recursion guided by s.

We recursively build the array: if the current segment is length 1, it is a base case. Otherwise, we split the segment in half, recursively build the left and right subarrays, and then merge them according to the next r-l characters from s. Each merge step consumes exactly r-l characters from the log, so we can advance a pointer in s as we reconstruct the array. This method guarantees that we can always produce a valid permutation matching the log.

Algorithm Walkthrough

1. Start with the string s and initialize a global pointer ptr to track which character of s we have consumed.
2. Define a recursive function build(l, r) which will construct a subarray corresponding to the segment [l, r) of the final permutation. If r-l == 1, return a single-element array [next_available_integer] and increment the next available integer.
3. Split the segment into halves: m = (l + r) // 2. Recursively construct the left half left = build(l, m) and right half right = build(m, r).
4. Merge left and right arrays according to the next r-l characters of s. Initialize i, j = 0, 0. For k from 0 to r-l-1, if s[ptr] is 0, take left[i] and increment i. If s[ptr] is 1, take right[j] and increment j. Increment ptr.
5. After consuming all merge characters, append any remaining elements from left[i:] and right[j:] to the merged array.
6. Return the merged array. The top-level call will produce the full permutation.

Why it works: the pointer ptr ensures that we consume the merge log exactly as it appears in s. By assigning consecutive integers to left and right halves, we maintain the property of a valid permutation while satisfying the merge decisions. Merge sort's recursive nature guarantees that each segment length and division is consistent with the log, so the reconstruction always produces a correct array.

Python Solution

import sys
input = sys.stdin.readline

s = input().strip()
ptr = 0
next_val = 1

def build(n):
    global ptr, next_val
    if n == 1:
        val = next_val
        next_val += 1
        return [val]
    m = n // 2
    left = build(m)
    right = build(n - m)
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if s[ptr] == '0':
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
        ptr += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

# find minimal n such that n-1 <= len(s)
n = 1
while n*(n-1)//2 < len(s):
    n += 1

a = build(n)
print(n)
print(' '.join(map(str, a)))

This code first guesses a minimal n that could produce the log length. It then recursively builds the permutation according to s. Using a global pointer allows us to consume s sequentially, and assigning integers in order ensures we produce a valid permutation without duplicates. The tricky part is correctly merging while updating ptr and ensuring all remaining elements are appended after consuming the relevant characters of s.

Worked Examples

Example 1:

Input: `"000000000000