Mastering AtCoder ABC462 Solutions with Python Examples

The AtCoder Beginner Contest 462 (ABC462) challenged participants with five algorithmic problems spanning string manipulation, graph theory, coordinate geometry, combinatorics, and dynamic optimization. Below, we dissect each problem’s solution approach and provide clean Python implementations that focus on clarity and efficiency.

Problem A: Extracting Digits from Strings

The first challenge required extracting all numeric digits from a mixed alphanumeric string while preserving their original order. The straightforward solution involves iterating through each character and checking whether it represents a digit.

Solution Approach:

• Convert the input string into a list for easy traversal.
• For each character, verify if it belongs to the set of digits '0' through '9'.
• Accumulate valid digits in a separate list and join them for the final output.

S = list(input())
digits = []
for char in S:
    if char.isdigit():
        digits.append(char)
print(''.join(digits))

This implementation uses Python’s built-in str.isdigit() method for clean and efficient digit detection. The time complexity remains linear, O(n), where n is the length of the input string.

Problem B: Mapping Gift Exchanges Between Participants

Participants in a gift exchange network needed to be mapped according to who received gifts from whom. The goal was to output, for each person, the list of people who sent them gifts.

Solution Approach:

• Use a dictionary to store each person’s incoming gift senders.
• Parse the input to extract sender-receiver pairs.
• For each pair (sender, receiver), record the sender in the receiver’s list.
• Finally, format the output to show the count of senders followed by their identifiers.

N = int(input())
recipients = {i: [] for i in range(1, N + 1)}

for _ in range(N):
    data = list(map(int, input().split()))
    sender = data[0]
    for receiver in data[1:]:
        recipients[receiver].append(sender)

for i in range(1, N + 1):
    senders = recipients[i]
    print(f"{len(senders)} {' '.join(map(str, senders))}")

This approach efficiently tracks relationships using dictionary lookups, ensuring O(N) time complexity for both processing and output generation.

Problem C: Counting Points Outside All Rectangles

Given N points on a 2D plane with unique x and y coordinates, determine how many points lie outside every possible rectangle defined by the bottom-left corner (0,0) and a point (X_i, Y_i).

Solution Approach:

• Sort points by their x-coordinates to process them in increasing order.
• Maintain the minimum y-coordinate encountered so far.
• A point (X_i, Y_i) lies outside all rectangles if its y-coordinate is less than the minimum y encountered in points processed before it.

N = int(input())
points = [list(map(int, input().split())) for _ in range(N)]
points.sort()

count = 0
min_y = float('inf')

for x, y in points:
    if y < min_y:
        count += 1
    min_y = min(min_y, y)

print(count)

The sorting step dominates the time complexity at O(N log N), while the subsequent scan is linear, O(N).

Problem D: Counting Valid Combinations of Two Suspects

In a murder investigation, N suspects were present in a building during specific time intervals. We needed to find the number of ways to choose two suspects who were both inside the building during a single continuous crime window of duration D.

Solution Approach:

• For each suspect, determine the time intervals in which they could be considered as potential suspects.
• Use a difference array to mark intervals where suspects are present.
• Compute the prefix sum to count how many suspects are present at each moment.
• For each moment, count combinations using the formula n choose 2 = n(n-1)/2.

def combinations(n):
    return n * (n - 1) // 2 if n >= 2 else 0

N, D = map(int, input().split())
suspects = [list(map(int, input().split())) for _ in range(N)]

max_time = 10**6 + 2
time_diff = [0] * max_time

for start, end in suspects:
    if end - start >= D:
        continue
    time_diff[start] += 1
    time_diff[end - D + 1] -= 1

suspect_count = [0] * max_time
current = 0
result = 0

for i in range(max_time):
    current += time_diff[i]
    suspect_count[i] = current
    result += combinations(current)

print(result)

The algorithm runs in O(N + T) time, where T is the maximum time value, making it suitable for large inputs.

Problem E: Minimizing Movement Cost with Time-Dependent Pricing

A token starts at (0,0) and must reach (X,Y) using directional moves. The cost of each move depends on whether the move is odd or even in sequence. The challenge was to compute the minimum total cost across all possible paths.

Key Insight:

• Moves along the diagonal axis (increasing both x and y) use only one cost type per direction.
• Alternate paths can be replaced by diagonal moves if they reduce total cost.

Solution Approach:

• Normalize coordinates to positive values using absolute values.
• Calculate base cost to reach the minimum of X and Y.
• Compute the remaining distance and determine how many moves fall under each cost type.
• Optimize by replacing expensive moves in blocks when cheaper alternatives exist.

T = int(input())

for _ in range(T):
    A, B, X, Y = map(int, input().split())
    X, Y = abs(X), abs(Y)

    cost = 2 * min(X, Y) * min(A, B)
    remaining = max(X, Y) - min(X, Y)

    if X < Y:
        a_moves = remaining // 2
        b_moves = a_moves if remaining % 2 == 0 else a_moves + 1
    else:
        b_moves = remaining // 2
        a_moves = b_moves if remaining % 2 == 0 else b_moves + 1

    if A > B and 3 * B < A:
        b_moves += 3 * a_moves
        a_moves = 0
    elif A < B and 3 * A < B:
        a_moves += 3 * b_moves
        b_moves = 0

    cost += a_moves * A + b_moves * B
    print(cost)

This solution efficiently handles up to 200,000 test cases with O(1) per-case complexity after normalization.

As programming contests continue to evolve, revisiting classic problems like those in ABC462 helps sharpen problem-solving skills and deepen understanding of algorithmic patterns. These solutions not only solve the contest challenges but also serve as templates for similar problems in future competitions.