Problem 1: Pairs from Sorted Arrays with Distance Constraints

We have two strictly non-decreasing integer arrays arrX and arrY, plus a non-negative integer maxGap. Our task is to generate a list of ordered pairs (x_i, y_j) adhering to these rules:

1. x_i ≤ y_j always holds
2. If y_j - x_i ≤ maxGap, select the first such valid y_j for x_i
3. If no valid y_j satisfies rule 2, pick the smallest y_j that still meets rule 1

Sample Input/Output

Input line: arrX={1,3,5},arrY={2,4,6},maxGap=1 Output: (1,2)(3,4)(5,6)

Implementation Approach

Instead of nested O(n*m) loops, we can optimize with a two-pointer technique since both arrays are sorted. This reduces time complexity to O(n + m). We track a pointer y_ptr starting at 0 for arrY, iterate over each element x in arrX, move y_ptr to find the first valid candidate y, then determine if we need to adjust for rule 3.

import re

def parse_input(line):
    arr_x_part = re.search(r'arrX=\{([0-9,]+)\}', line).group(1)
    arr_y_part = re.search(r'arrY=\{([0-9,]+)\}', line).group(1)
    gap_part = re.search(r'maxGap=([0-9]+)', line).group(1)
    return (
        list(map(int, arr_x_part.split(','))),
        list(map(int, arr_y_part.split(','))),
        int(gap_part)
    )

x_list, y_list, gap = parse_input(input().strip())
result_pairs = []
y_pos = 0
len_y = len(y_list)

for current_x in x_list:
    # Move y_pos to first y >= current_x
    while y_pos < len_y and y_list[y_pos] < current_x:
        y_pos += 1
    if y_pos >= len_y:
        continue  # No valid y for this x
    # Check if we have a candidate within gap
    candidate = y_list[y_pos]
    if candidate - current_x <= gap:
        result_pairs.append((current_x, candidate))
    else:
        result_pairs.append((current_x, candidate))
    # Keep y_pos for next x, no need to reset

print(''.join([f'({a},{b})' for a, b in result_pairs]))

---

Problem 2: Tokenization and Reverse Concatenation with Special Delimietr Rules

We process a single input string to split into tokens, then print them in reverse order separated by single spaces. Tokenization rule are:

1. Only alphanumeric characters and valid hyphens remain in tokens
2. A hyphen - is valid only if surrounded by alphanumerics on both sides
3. Any other chraacter, invalid hyphen, or consecutive hyphens act as delimiters

Sample Input/Output

Input line: I am an 20-years out--standing @ * -stu- dent Output: dent stu standing out 20-years an am I

Implementation Approach

We can build tokens character by character, maintaining a buffer and checking validity for each - encountered. After processing all characters, we trim any trailing invalid hyphens from the buffer and add it as a token if non-empty. Finally, reverse the token list and join.

def is_alnum(char):
    return char.isalnum()

buffer = []
tokens = []

for char in input().strip():
    if is_alnum(char):
        buffer.append(char)
    elif char == '-':
        # Check if buffer is not empty and last char is alnum (valid so far)
        if buffer and is_alnum(buffer[-1]):
            buffer.append(char)
        else:
            # Invalid hyphen, flush buffer if needed
            if buffer:
                # Remove trailing invalid hyphens first
                while buffer and not is_alnum(buffer[-1]):
                    buffer.pop()
                if buffer:
                    tokens.append(''.join(buffer))
                buffer = []
    else:
        # Other delimiter, flush buffer
        if buffer:
            while buffer and not is_alnum(buffer[-1]):
                buffer.pop()
            if buffer:
                tokens.append(''.join(buffer))
            buffer = []

# Flush remaining buffer
if buffer:
    while buffer and not is_alnum(buffer[-1]):
        buffer.pop()
    if buffer:
        tokens.append(''.join(buffer))

print(' '.join(reversed(tokens)))

---

Problem 3: Flight Booking Update System

We maintain flight seat reservations, processing initial bookings followed by a list of rebookings. Rebookings overwrite previous seat assignments for the same passenger, and each new rebooking takes precedence over prior ones. The output lists all current bookings sorted lexicographically by seat key (flight,seat).

Sample Input/Output

Input:

3
CZ7132,A1,ZHANGSAN
CZ7132,A2,ZHAOSI
CZ7156,A2,WANGWU
2
CZ7132,A1,CZ7156,A2
CZ7156,A2,CZ7156,A3

Output:

CZ7132,A2,ZHAOSI
CZ7156,A2,ZHANGSAN
CZ7156,A3,WANGWU

Implementation Approach

We use two dictionaries: one mapping passenger names directly to their current seat keys, and another to track occupied seat keys to avoid conflicts (though rebookings explicitly overwrite, this helps catch edge cases if needed). Since we process rebookings in order, later entries automatically replace earlier ones for the same passenger. Finally, we sort the seat keys lexicographically and print each entry.

# Read initial bookings
initial_count = int(input())
passenger_to_seat = {}
seat_to_passenger = {}

for _ in range(initial_count):
    flight, seat, name = input().strip().split(',', 2)
    seat_key = f"{flight},{seat}"
    passenger_to_seat[name] = seat_key
    seat_to_passenger[seat_key] = name

# Read and process rebookings
rebook_count = int(input())

for _ in range(rebook_count):
    old_flight, old_seat, new_flight, new_seat = input().strip().split(',')
    old_seat_key = f"{old_flight},{old_seat}"
    new_seat_key = f"{new_flight},{new_seat}"
    # Get passenger name from old seat
    current_name = seat_to_passenger[old_seat_key]
    # Remove old seat occupancy
    del seat_to_passenger[old_seat_key]
    # Remove any passenger already in new seat (if exists, since rebook overwrites)
    if new_seat_key in seat_to_passenger:
        del passenger_to_seat[seat_to_passenger[new_seat_key]]
    # Update both dictionaries
    passenger_to_seat[current_name] = new_seat_key
    seat_to_passenger[new_seat_key] = current_name

# Sort seat keys lex and print
for seat in sorted(seat_to_passenger.keys()):
    print(f"{seat},{seat_to_passenger[seat]}")