Constraints

• block_type is either 'R' or 'B'.
• All integers are in the signed 32-bit range [-2147483648, 2147483647].
• For an RLE block, count >= 1.
• For a bit-packed block, 0 <= len(data) <= 10^4.

Examples

Solution

def solution(block_type, data):
    def min_bits_signed(x):
        if x >= 0:
            return 1 if x == 0 else x.bit_length() + 1
        return (~x).bit_length() + 1

    def pack(values, w):
        words = []
        current = 0
        used = 0
        mask = (1 << w) - 1
        for v in values:
            u = v & mask
            remaining = w
            while remaining > 0:
                space = 32 - used
                take = remaining if remaining < space else space
                part = u & ((1 << take) - 1)
                current |= part << used
                used += take
                u >>= take
                remaining -= take
                if used == 32:
                    words.append(current & 0xFFFFFFFF)
                    current = 0
                    used = 0
        if used > 0:
            words.append(current & 0xFFFFFFFF)
        return words

    if block_type == 'R':
        value, count = data
        return {'type': 'R', 'value': value, 'count': count}

    values = list(data)
    if not values:
        return {'type': 'B', 'bitWidth': 0, 'count': 0, 'words': []}

    bit_width = max(min_bits_signed(v) for v in values)
    return {'type': 'B', 'bitWidth': bit_width, 'count': len(values), 'words': pack(values, bit_width)}

Time complexity: O(n + number_of_words), which is O(n) because each value uses at most 32 bits. Space complexity: O(number_of_words).

Hints

1. A signed w-bit two's-complement integer must lie in the range [-2^(w-1), 2^(w-1)-1].
2. While packing, track the current 32-bit word and the bit offset already used inside it.

Constraints

• 0 <= len(values) <= 10^5
• 1 <= rle_min_run <= 10
• 1 <= max_bp_block <= 128
• All input values are in the signed 32-bit range [-2147483648, 2147483647].

Examples

Solution

def solution(values, rle_min_run=3, max_bp_block=128):
    from collections import deque

    def min_bits_signed(x):
        if x >= 0:
            return 1 if x == 0 else x.bit_length() + 1
        return (~x).bit_length() + 1

    def pack(vals, w):
        words = []
        current = 0
        used = 0
        mask = (1 << w) - 1
        for v in vals:
            u = v & mask
            remaining = w
            while remaining > 0:
                space = 32 - used
                take = remaining if remaining < space else space
                part = u & ((1 << take) - 1)
                current |= part << used
                used += take
                u >>= take
                remaining -= take
                if used == 32:
                    words.append(current & 0xFFFFFFFF)
                    current = 0
                    used = 0
        if used > 0:
            words.append(current & 0xFFFFFFFF)
        return words

    def make_bp(chunk):
        bit_width = max(min_bits_signed(v) for v in chunk)
        return {'type': 'B', 'bitWidth': bit_width, 'count': len(chunk), 'words': pack(chunk, bit_width)}

    blocks = []
    buffer = deque()

    def flush_full_chunks():
        while len(buffer) >= max_bp_block:
            chunk = [buffer.popleft() for _ in range(max_bp_block)]
            blocks.append(make_bp(chunk))

    def flush_all():
        while buffer:
            size = min(len(buffer), max_bp_block)
            chunk = [buffer.popleft() for _ in range(size)]
            blocks.append(make_bp(chunk))

    i = 0
    n = len(values)
    while i < n:
        j = i + 1
        while j < n and values[j] == values[i]:
            j += 1
        run_len = j - i

        if run_len >= rle_min_run:
            flush_all()
            blocks.append({'type': 'R', 'value': values[i], 'count': run_len})
        else:
            for k in range(i, j):
                buffer.append(values[k])
            flush_full_chunks()

        i = j

    flush_all()
    return blocks

Time complexity: O(n). Space complexity: O(max_bp_block + output_size).

Hints

1. Think in terms of maximal runs first. A long enough run becomes one R block; a short run is buffered into BP data.
2. Flush the buffered non-RLE values before emitting an R block, and also whenever the BP buffer reaches max_bp_block.

Constraints

• 0 <= len(blocks) <= 10^5
• Each block is valid and follows the canonical format.
• For bit-packed blocks, 1 <= bitWidth <= 32 when count > 0.
• All decoded values fit in the signed 32-bit range.

Examples

Solution

def solution(blocks):
    result = []

    for block in blocks:
        if block['type'] == 'R':
            result.extend([block['value']] * block['count'])
            continue

        w = block['bitWidth']
        count = block['count']
        words = block['words']
        if count == 0:
            continue

        mask = (1 << w) - 1
        bit_pos = 0
        for _ in range(count):
            word_index = bit_pos // 32
            offset = bit_pos % 32

            if offset + w <= 32:
                u = (words[word_index] >> offset) & mask
            else:
                low_bits = 32 - offset
                high_bits = w - low_bits
                low = (words[word_index] >> offset) & ((1 << low_bits) - 1)
                high = words[word_index + 1] & ((1 << high_bits) - 1)
                u = low | (high << low_bits)

            sign_bit = 1 << (w - 1)
            if u & sign_bit:
                value = u - (1 << w)
            else:
                value = u
            result.append(value)
            bit_pos += w

    return result

Time complexity: O(total_decoded_values). Space complexity: O(total_decoded_values).

Hints

1. The i-th packed value starts at bit position i * bitWidth inside that block's bitstream.
2. After extracting the unsigned w-bit pattern, check its highest bit to decide whether it represents a negative number.

Constraints

• 0 <= number of sequences <= 10^4
• 0 <= total number of integers across all sequences <= 2 * 10^5
• 1 <= rle_min_run <= 10
• All integers are in the signed 32-bit range [-2147483648, 2147483647].

Examples

Solution

def solution(test_sequences, rle_min_run=3):
    INT_MIN = -2147483648
    INT_MAX = 2147483647

    def analyze_sequence(seq):
        has_r = False
        has_b = False
        i = 0
        n = len(seq)
        while i < n:
            j = i + 1
            while j < n and seq[j] == seq[i]:
                j += 1
            if j - i >= rle_min_run:
                has_r = True
            else:
                has_b = True
            i = j
        return has_r, has_b

    summary = {
        'simple_bp': False,
        'long_run_rle': False,
        'alternating_switch': False,
        'has_int_min': False,
        'has_int_max': False,
        'has_negative': False,
        'empty_input': False,
        'complete': False,
    }

    for seq in test_sequences:
        if not seq:
            summary['empty_input'] = True
        if any(v == INT_MIN for v in seq):
            summary['has_int_min'] = True
        if any(v == INT_MAX for v in seq):
            summary['has_int_max'] = True
        if any(v < 0 for v in seq):
            summary['has_negative'] = True

        has_r, has_b = analyze_sequence(seq)
        if seq and not has_r:
            summary['simple_bp'] = True
        if has_r:
            summary['long_run_rle'] = True
        if has_r and has_b:
            summary['alternating_switch'] = True

    summary['complete'] = all([
        summary['simple_bp'],
        summary['long_run_rle'],
        summary['alternating_switch'],
        summary['has_int_min'],
        summary['has_int_max'],
        summary['has_negative'],
        summary['empty_input'],
    ])
    return summary

Time complexity: O(total number of integers across the whole suite). Space complexity: O(1) extra space, excluding the returned dictionary.

Hints

1. A sequence has an RLE block iff at least one maximal run is long enough.
2. alternating_switch is stronger than having some BP-only tests and some RLE-only tests; one single sequence must produce both block types.