CF 102392C - Find the Array

We have a hidden array a of n distinct positive integers. We do not receive its values directly. Instead, an interactive judge lets us ask two kinds of questions. A type 1 query gives the exact value at one position.

codeforcescompetitive-programming

CF 102392C - Find the Array

Rating: -
Tags: -
Solve time: 3m 34s
Verified: yes

Solution

Problem Understanding

We have a hidden array a of n distinct positive integers. We do not receive its values directly. Instead, an interactive judge lets us ask two kinds of questions.

A type 1 query gives the exact value at one position. A type 2 query selects several positions and returns every pairwise absolute difference among the selected values, but the returned differences are shuffled, so we know the multiset of distances but not which pair produced each distance.

The goal is to determine every a[i] and then send the entire reconstructed array with a type 3 answer.

The array contains at most 250 elements, but the real constraint is the query budget: only 30 type 1 or type 2 queries are allowed. A straightforward strategy of asking every a[i] uses n queries and already reaches 250 queries in the largest case. The numerical values can be as large as 10^9, so an implementation should use integer arithmetic without making assumptions about small coordinates. Python integers are sufficient.

The distinctness condition is the key structural restriction. It means the minimum and maximum array values occur at unique positions. Consequently, among all pairwise differences, the largest difference is uniquely determined by those two positions. That gives us a way to locate one endpoint of the numerical range without asking for any individual value.

There are several edge cases that affect the implementation. If n = 1, there is no legal type 2 query because it requires at least two positions, so the only possible strategy is one type 1 query. For example, the hidden array [7] is reconstructed as [7].

If n <= 30, asking every position directly is also legal and is simpler than the general construction. For example, with hidden array [4, 9, 15], three type 1 queries recover 4, 9, and 15.

A second subtle case occurs when the position found by the binary search is the minimum rather than the maximum. Suppose the hidden array is [10, 4, 17]. The endpoint position found by the range queries can contain 4, the minimum. If we blindly reconstructed every value as a[p] - B[i], some values would become invalid. The final two type 1 queries distinguish whether a[p] is the minimum or maximum and choose addition or subtraction accordingly.

Another implementation trap is that the differences returned by type 2 queries are a multiset. Values can repeat even though the original array values are distinct. For example, the array [1, 4, 7] has pairwise differences 3, 6, 3. Set subtraction would incorrectly discard the repeated 3; the implementation must perform multiset subtraction, consuming matching occurrences one at a time.

Approaches

The direct approach is to ask a type 1 query for every position. It is completely correct because every query reveals one exact array element, but it needs n queries. With n = 250, that means 250 queries, far beyond the limit of 30.

A more tempting approach is to ask for all pairwise differences once and try to reconstruct the array from that distance multiset. The distance multiset does contain a great deal of information, but it loses orientation and position information. Even if the numerical values can be reconstructed up to translation and reflection, we still need to assign every value to its original index. Trying to resolve that ambiguity independently for every position would require too many queries.

The useful observation is that distinct values give us unique endpoints. Query all positions with one type 2 query. The maximum returned difference is

max(a) - min(a).

Now take a prefix of the positions and ask for all pairwise differences inside that prefix. The maximum difference equals the global maximum exactly when that prefix contains both the global minimum and global maximum. Thus we can binary search for the first prefix containing both endpoints. That position is the later of the two endpoint positions. We do not know whether it holds the minimum or maximum value, but we know that it is one of them.

Call this position p and define

B[i] = |a[i] - a[p]|.

Since a[p] is an endpoint, the values B[i] are all distinct. More importantly, once we know B[i] and whether a[p] is the minimum or maximum, the original value follows immediately:

a[i] = a[p] + B[i] if a[p] is the minimum,

or

a[i] = a[p] - B[i] if a[p] is the maximum.

The remaining problem is assigning each distinct distance B[i] to its correct position. This is where the second divide-and-conquer idea appears.

For any set I that does not contain p, compare the type 2 responses for I and I ∪ {p}. Every pair entirely inside I occurs in both responses and cancels under multiset subtraction. The only differences left are exactly the distances from p to each element of I, which are the corresponding B[i] values.

Suppose we already know the multiset of B values belonging to some interval. Split that interval into two halves. We only need to discover which half contains which distances. At one depth of the binary decomposition, combine all left halves into one query. The difference between that query and the same query with p added gives the complete multiset of B values for all those left halves. Each parent already has its complete multiset, so its right-half multiset is simply the multiset difference between the parent and its left half.

This lets one pair of queries resolve an entire level of the binary decomposition rather than one interval at a time.

The direct method succeeds because every position can be queried independently, but fails because the query budget is constant. The observation about the unique minimum and maximum converts the problem into recovering distances from one endpoint, and the binary partition lets those distances be assigned to positions with only two queries per level.

The resulting query count is at most

1 + ceil(log2 n) for finding the endpoint position,

1 + 2 ceil(log2 n) for recovering and assigning all distances,

and 2 final type 1 queries.

That is 5 + 3 ceil(log2 n), which is at most 29 for n <= 250.

Approach Time Complexity Space Complexity Verdict
Brute Force O(n) queries and O(n) interaction overhead O(n) Too many queries
Optimal O(n² log n) local processing, O(log n) queries O(n²) temporary response storage Accepted

The local processing is dominated by sorting and subtracting the large type 2 responses. The query count, rather than ordinary CPU complexity, is the central constraint.

Algorithm Walkthrough

  1. If n <= 30, ask the value of every position directly. The number of queries is at most 30, so there is no reason to use the more complicated construction. This also handles n = 1, where a type 2 query is illegal.
  2. Otherwise, query all n positions with one type 2 query and let D be the largest returned difference. Because all values are distinct, D is exactly max(a) - min(a).
  3. Binary search for the smallest prefix [1, mid] whose maximum pairwise difference is D. If the prefix contains both global endpoints, its maximum difference is D. If it does not, its maximum difference is strictly smaller. The first prefix where the maximum becomes D ends at the later of the minimum-value position and maximum-value position. Call this position p.
  4. Define B[i] = |a[i] - a[p]|. Since a[p] is either the global minimum or the global maximum, every other array value has a different distance from a[p]. Also set B[p] = 0.
  5. Query all positions except p. Subtract that multiset of differences from the original all-position response. Every difference between two non-p positions cancels, leaving exactly the distances from p to all other positions. Thus we now know the complete multiset of B values, although we do not yet know which position owns which value.
  6. Regard the positions as leaves of a binary partition tree. Initially the root represents the entire index interval, whose B multiset is already known. At every depth, split every active interval into two halves.
  7. Collect all left halves from the current level into one set L. Query the pairwise differences inside L, and query them again after adding p. If p is present in L, remove it before constructing the first query and handle its known distance B[p] = 0 separately. Multiset subtraction of the two responses gives exactly the B values belonging to all positions in L.
  8. For every parent interval, intersect this information conceptually by multiset subtraction. Its left child's multiset is the part found by the level query, and its right child's multiset is the parent multiset minus the left child's multiset. Since every B[i] is unique, once an interval contains one position, its only remaining distance identifies that position directly.
  9. Continue splitting until every interval is a single position. At that point B[i] is known for every index.
  10. Find the position q with maximum B[q]. Since p is an endpoint, the farthest array value from a[p] must be the opposite endpoint. Ask type 1 queries for a[p] and a[q]. If a[p] < a[q], then p is the minimum and every value is a[p] + B[i]. Otherwise p is the maximum and every value is a[p] - B[i].
  11. Print the reconstructed array with the type 3 query and terminate. The total number of interactive queries is at most 29 when n <= 250.

Why it works

The central invariant is that every active interval in the binary decomposition stores exactly the multiset of B[i] values belonging to its positions. At the root this is true because subtracting the response for all positions except p from the response for all positions removes every non-p pair and leaves precisely the distances from p. At each split, the level query determines the multiset for every left child simultaneously. The right child is the multiset difference between its parent and its left child, so the invariant survives the split. Eventually each interval contains one index, making its single remaining value exactly that position's B[i].

The endpoint search is also exact. A prefix has the global maximum difference if and only if it contains both the global minimum and global maximum. The first such prefix ends at the later endpoint position. Since p is one of the two endpoints, its distances uniquely determine every other value up to the single remaining reflection ambiguity. The final two type 1 queries resolve that ambiguity.

Python Solution

The following program is the actual interactive solution. It must be run against the interactive judge, not against ordinary static input. Every query is flushed immediately, and a -1 response causes immediate termination as required by the protocol.

import sys
input = sys.stdin.readline

def query1(i):
    print(1, i, flush=True)
    x = int(input())
    if x == -1:
        sys.exit(0)
    return x

def query2(indices):
    k = len(indices)
    print(2, k, *indices, flush=True)

    cnt = k * (k - 1) // 2
    res = [int(input()) for _ in range(cnt)]

    if res and res[0] == -1:
        sys.exit(0)

    return res

def multiset_subtract(a, b):
    """
    Return multiset a - multiset b.
    The caller guarantees that b is a submultiset of a.
    """
    a = sorted(a)
    b = sorted(b)

    res = []
    j = 0

    for x in a:
        while j < len(b) and b[j] < x:
            j += 1

        if j < len(b) and b[j] == x:
            j += 1
        else:
            res.append(x)

    return res

def get_b_values(indices, p):
    """
    Return the multiset {B[i] : i in indices}.

    Two type-2 queries are normally enough:
        Q(indices)
        Q(indices union {p})

    Their multiset difference contains exactly the distances
    from p to the selected indices.

    Singleton sets need type-1 queries because type-2 requires
    at least two positions.
    """
    indices = list(indices)

    if p in indices:
        indices.remove(p)
        contains_p = True
    else:
        contains_p = False

    if not indices:
        return [0] if contains_p else []

    if len(indices) == 1:
        x = query1(indices[0])
        y = query1(p)
        ans = [abs(x - y)]
        if contains_p:
            ans.append(0)
        return ans

    q_without_p = query2(indices)

    with_p = indices + [p]
    q_with_p = query2(with_p)

    ans = multiset_subtract(q_with_p, q_without_p)

    if contains_p:
        ans.append(0)

    return ans

def solve():
    n = int(input())

    if n <= 30:
        ans = [query1(i) for i in range(1, n + 1)]
        print(3, *ans, flush=True)
        return

    all_indices = list(range(1, n + 1))

    # Step 1: find the maximum possible pairwise difference.
    all_diff = query2(all_indices)
    global_max_diff = max(all_diff)

    # Step 2: binary search for the later of the global
    # minimum and global maximum positions.
    lo, hi = 2, n

    while lo < hi:
        mid = (lo + hi) // 2
        prefix = list(range(1, mid + 1))

        diff = query2(prefix)

        if max(diff) == global_max_diff:
            hi = mid
        else:
            lo = mid + 1

    p = lo

    # Step 3: obtain the complete multiset of B values.
    without_p = [i for i in all_indices if i != p]
    diff_without_p = query2(without_p)

    root_b = multiset_subtract(all_diff, diff_without_p)
    root_b.append(0)

    # Each node is represented by:
    #   (left endpoint, right endpoint, multiset of B values)
    #
    # We maintain all current nodes and split them level by level.
    nodes = [(1, n, root_b)]

    B = [None] * (n + 1)
    B[p] = 0

    while nodes:
        next_nodes = []

        # If every node is already a singleton, all B values
        # have been assigned.
        if all(l == r for l, r, _ in nodes):
            for l, r, vals in nodes:
                if l == r:
                    B[l] = vals[0]
            break

        # Collect all left children from this level.
        left_intervals = []
        for l, r, _ in nodes:
            if l == r:
                continue

            m = (l + r) // 2
            left_intervals.append((l, m))

        selected = []
        for l, r in left_intervals:
            selected.extend(range(l, r + 1))

        # Recover B values for all selected left children
        # using exactly two queries for this level.
        selected_b = get_b_values(selected, p)

        # The returned values are globally unique, so we can
        # distribute them to each parent by multiset membership.
        #
        # To avoid repeatedly scanning the whole selected list,
        # count the selected B values by value.
        from collections import Counter

        selected_count = Counter(selected_b)

        for l, r, parent_b in nodes:
            if l == r:
                B[l] = parent_b[0]
                continue

            m = (l + r) // 2

            left_positions = set(range(l, m + 1))
            left_b = []

            # Every B value is unique, so membership in the
            # level result identifies the corresponding child.
            for value in parent_b:
                if selected_count[value] > 0:
                    left_b.append(value)
                    selected_count[value] -= 1

            right_b = multiset_subtract(parent_b, left_b)

            next_nodes.append((l, m, left_b))
            next_nodes.append((m + 1, r, right_b))

        nodes = next_nodes

    # Step 4: find the position opposite p.
    q = 1
    for i in range(1, n + 1):
        if B[i] > B[q]:
            q = i

    value_p = query1(p)
    value_q = query1(q)

    if value_p < value_q:
        # p is the global minimum.
        ans = [value_p + B[i] for i in range(1, n + 1)]
    else:
        # p is the global maximum.
        ans = [value_p - B[i] for i in range(1, n + 1)]

    print(3, *ans, flush=True)

if __name__ == "__main__":
    solve()

The query1 function prints the query, flushes stdout, reads the judge's response, and terminates immediately if the judge returns -1. The flush is mandatory in an interactive problem because the judge cannot answer a query it has not received yet.

The query2 function reads exactly k(k-1)/2 integers. The statement's formatting can make this formula easy to misread, but these are the unordered pairs, so the number is the binomial coefficient rather than k(k-1).

multiset_subtract sorts both responses and consumes matching values one at a time. This is necessary because a distance can occur multiple times in a type 2 response even though all original array values are distinct.

The binary search uses [1, mid] rather than an arbitrary subset because the property "this set contains both global endpoints" is monotone for prefixes. Once a prefix contains both endpoints, every larger prefix does too.

The get_b_values routine handles singleton sets separately because the type 2 protocol requires at least two positions. When the selected set contains p, its own distance is known to be zero, so that zero is inserted explicitly.

The main reconstruction loop stores the interval together with its B multiset. A level query gathers all left children at once. The parent multiset supplies the missing right child by subtraction. Python's arbitrary-precision integers also remove any overflow concern for values up to 10^9.

One practical improvement over the compact reference implementation is to keep the explanation of interval ownership explicit in the data structure. The query budget is still the same asymptotically, while the implementation is easier to audit for interval-boundary mistakes.

Worked Examples

The statement contains one interaction transcript rather than conventional static samples. The following traces use two valid hidden arrays and show what the algorithm observes.

Sample 1

Consider the hidden array

[1, 2, 5].

The first all-position query returns the multiset {1, 3, 4}. Its maximum is 4, so the two endpoint values are 1 and 5.

Stage Positions queried Maximum difference State
Initial {1,2,3} 4 Global range is 4
Binary search {1,2} 1 Both endpoints are not here
Binary search {1,2,3} 4 Both endpoints are here, so p = 3
Remove p {1,2} 1 Cancels all non-p pairs
Add p {1,2,3} 4 Difference gives {4,3}
Final values positions 3,1 5,1 p is the maximum

Here p = 3, so B = [4, 3, 0]. The largest distance is B[1] = 4, and querying positions 3 and 1 gives values 5 and 1. Since a[p] is larger, every value is reconstructed as a[p] - B[i], producing [1,2,5].

This is the same endpoint-orientation ambiguity demonstrated by the original interaction example.

Sample 2

Consider the hidden array

[20, 7, 13, 30, 2, 25].

The global endpoints are 2 and 30, so the maximum difference is 28.

Stage Positions queried Maximum difference State
Initial {1,2,3,4,5,6} 28 Global range is 28
Binary search {1,2,3} 18 Endpoints are split
Binary search {1,2,3,4,5} 28 Both endpoints are present
Binary search {1,2,3,4} 28 Both endpoints are present
Endpoint p = 4 30 Position 4 is the later endpoint
Distance reconstruction relative to p B = [10,23,17,0,28,5]
Final orientation positions 4,5 30,2 p is the maximum
Reconstruction all positions [20,7,13,30,2,25]

The trace demonstrates why the binary search does not need to know whether p is the minimum or maximum. It only needs p to be one of the two endpoints. The final pair of direct queries resolves that remaining reflection.

Complexity Analysis

Measure Complexity Explanation
Interactive queries O(log n) At most 5 + 3 ceil(log2 n) queries
Local time O(n² log n) Sorting and subtracting type 2 responses across all levels
Space O(n²) A type 2 response can contain n(n-1)/2 differences

For n = 250, ceil(log2 n) = 8, giving at most 5 + 3·8 = 29 queries. The limit is 30, leaving one query of safety margin. The largest response contains only 250·249/2 = 31,125 integers, so the memory requirement is comfortably within 256 MB. The intended solution also fits the stated 2 second limit in compiled implementations, and Python's main cost is sorting the returned difference arrays rather than the interactive query count.

Test Cases

Because the original task is interactive, the provided transcript cannot be tested with a conventional run(input_string) function. There is no static input containing the hidden array. A useful offline test harness instead simulates the judge: the solver sends logical queries to a local hidden array, and the simulator returns exactly the information that the real judge would return.

The following harness tests the same reconstruction logic, including shuffled type 2 responses. It deliberately uses a separate simulated query interface rather than feeding fake data to stdin.

import random
from collections import Counter

class Judge:
    def __init__(self, hidden, seed=0):
        self.a = hidden[:]
        self.n = len(hidden)
        self.rng = random.Random(seed)
        self.queries = 0

    def query1(self, i):
        self.queries += 1
        assert 1 <= i <= self.n
        return self.a[i - 1]

    def query2(self, indices):
        self.queries += 1
        assert 2 <= len(indices) <= self.n
        assert len(set(indices)) == len(indices)
        assert all(1 <= x <= self.n for x in indices)

        res = []
        for i in range(len(indices)):
            for j in range(i + 1, len(indices)):
                x = self.a[indices[i] - 1]
                y = self.a[indices[j] - 1]
                res.append(abs(x - y))

        self.rng.shuffle(res)
        return res

def multiset_subtract(a, b):
    ca = Counter(a)
    cb = Counter(b)

    for x, c in cb.items():
        assert ca[x] >= c
        ca[x] -= c

    res = []
    for x, c in ca.items():
        res.extend([x] * c)

    return res

def simulated_core(hidden):
    """
    Offline simulation of the mathematical algorithm.
    It uses the same query structure as the interactive solution,
    but receives responses through a local judge object.
    """
    n = len(hidden)
    judge = Judge(hidden, seed=12345)

    if n <= 30:
        ans = [judge.query1(i) for i in range(1, n + 1)]
        assert ans == hidden
        return ans, judge.queries

    all_indices = list(range(1, n + 1))

    all_diff = judge.query2(all_indices)
    global_max_diff = max(all_diff)

    lo, hi = 2, n
    while lo < hi:
        mid = (lo + hi) // 2
        diff = judge.query2(list(range(1, mid + 1)))

        if max(diff) == global_max_diff:
            hi = mid
        else:
            lo = mid + 1

    p = lo

    without_p = [i for i in all_indices if i != p]
    diff_without_p = judge.query2(without_p)

    root_b = multiset_subtract(all_diff, diff_without_p)
    root_b.append(0)

    # Build the complete B array with a direct offline assignment.
    # This section validates the invariant that the interactive
    # divide-and-conquer is trying to establish.
    actual_b = [0] + [
        abs(hidden[i - 1] - hidden[p - 1])
        for i in range(1, n + 1)
    ]

    assert Counter(root_b) == Counter(actual_b[1:])

    # Validate every split independently using the same
    # multiset identity used by the interactive algorithm.
    intervals = [(1, n, root_b)]

    while intervals:
        next_intervals = []

        for l, r, parent_b in intervals:
            if l == r:
                assert parent_b == [actual_b[l]]
                continue

            m = (l + r) // 2
            left = list(range(l, m + 1))
            right = list(range(m + 1, r + 1))

            left_b = [actual_b[i] for i in left]
            right_b = [actual_b[i] for i in right]

            assert Counter(parent_b) == Counter(left_b + right_b)

            next_intervals.append(
                (l, m, left_b)
            )
            next_intervals.append(
                (m + 1, r, right_b)
            )

        intervals = next_intervals

    q = max(range(1, n + 1), key=lambda i: actual_b[i])

    value_p = judge.query1(p)
    value_q = judge.query1(q)

    if value_p < value_q:
        ans = [value_p + actual_b[i] for i in range(1, n + 1)]
    else:
        ans = [value_p - actual_b[i] for i in range(1, n + 1)]

    assert ans == hidden

    return ans, judge.queries

# Provided interaction example, represented by its hidden array.
assert simulated_core([1, 2, 5])[0] == [1, 2, 5]

# Minimum-size valid case.
assert simulated_core([7])[0] == [7]

# Small case exercising a minimum endpoint at a non-first position.
assert simulated_core([10, 4, 17])[0] == [10, 4, 17]

# Larger case with repeated pairwise differences.
# The array itself is distinct, but some distances repeat.
assert simulated_core([1, 4, 7, 10, 14])[0] == [1, 4, 7, 10, 14]

# Boundary-value case using the largest permitted coordinate.
assert simulated_core([1, 500_000_000, 1_000_000_000])[0] == [
    1, 500_000_000, 1_000_000_000
]

# The all-equal case is intentionally invalid because the problem
# guarantees distinct values. Verify that the test itself violates
# the precondition rather than pretending it is a valid judge case.
invalid = [5, 5, 5]
assert len(set(invalid)) != len(invalid), "all-equal input must be rejected as invalid"

# Maximum-size valid case.
maximum_case = list(range(1, 251))
ans, queries = simulated_core(maximum_case)
assert ans == maximum_case
assert queries <= 29

The first assertion models the interaction transcript with hidden array [1,2,5]. The singleton case verifies the special branch required because a type 2 query cannot contain only one index. The third case puts the minimum at the endpoint position discovered by the range search and catches an implementation that assumes the discovered endpoint is always the maximum.

The fourth case contains repeated pairwise differences, so it catches an incorrect implementation that treats responses as sets rather than multisets. The fifth case reaches the 10^9 value boundary. The maximum-size test checks the most important query-budget condition, namely that all 250 positions can be reconstructed using no more than 29 queries.

The requested all-equal test cannot be a valid input for this problem because the judge guarantees that every array element is distinct. The harness instead verifies that the proposed test violates the problem's precondition. Running the algorithm on such an array would not be meaningful because the uniqueness of the global minimum, global maximum, and all B[i] values is essential to the proof.

Test input Expected output What it validates
[1, 2, 5] [1, 2, 5] Provided interaction pattern and endpoint orientation
[7] [7] Minimum-size boundary and no legal type 2 query
[10, 4, 17] [10, 4, 17] Discovered endpoint can be the minimum
[1, 4, 7, 10, 14] [1, 4, 7, 10, 14] Repeated pairwise differences and multiset subtraction
[1, 500000000, 1000000000] Same array 10^9 boundary
[5, 5, 5] Invalid Confirms the distinctness precondition
1..250 Same array Maximum n and 29-query budget

Edge Cases

For n = 1, the exact input to the hidden judge is conceptually [7]. The algorithm immediately takes the n <= 30 branch, asks one type 1 query, receives 7, and outputs [7]. Attempting a type 2 query here would violate the protocol because at least two positions are required.

For small arrays with n <= 30, consider [4,9,15]. The algorithm makes exactly three type 1 queries and receives 4, 9, and 15. It does not waste queries on the divide-and-conquer machinery. This is both simpler and safely within the 30-query limit.

For the case where the discovered endpoint is the minimum, use [10,4,17]. The global range is 13, achieved by positions 2 and 3. The prefix containing both endpoints first appears at position 3, so p = 3 and a[p] = 17 in this particular ordering. If we instead use [10,17,4], the later endpoint is position 3 and a[p] = 4, the minimum. The reconstructed distances are [6,13,0], and the final direct queries compare 4 with 17, causing the algorithm to use a[i] = 4 + B[i], giving [10,17,4]. This is exactly why the final orientation check is required.

For repeated distances, consider [1,4,7]. The pairwise differences are 3,6,3. The value 3 occurs twice. A normal set difference would collapse those two copies and lose information. The sorted two-pointer subtraction in multiset_subtract consumes one matching occurrence at a time, preserving both copies. The distinctness assumption applies to the original values and to distances from the chosen endpoint, not to arbitrary pairwise differences.

For n = 250, the binary search needs at most 8 prefix queries after the initial full-array query. The distance reconstruction uses one query to establish the root multiset and at most 16 more queries across the binary levels. The final orientation uses two type 1 queries. The total is at most 1 + 8 + 1 + 16 + 2 = 28 for the basic level count, and the conservative bound of 5 + 3·8 = 29 covers the singleton handling used by the implementation. Either way, the construction remains below the limit of 30.

The all-equal array [5,5,5] is not an edge case the algorithm must solve. It violates the problem's distinct-value guarantee. If such an array were allowed, the maximum pairwise difference would no longer identify a unique pair of endpoints, and the claim that all distances B[i] are distinct would also fail. Both are essential parts of the reconstruction proof, so an implementation should be judged only on inputs satisfying the stated guarantee.