CF 1970F1 - Playing Quidditch (Easy)

CF 1970F1 - Playing Quidditch (Easy)

Rating: 2300
Tags: implementation
Solve time: 2m 30s
Verified: no

Solution

Problem Understanding

We are asked to simulate a simplified Quidditch game on a rectangular grid. The field contains players from two teams, goals for both teams, and exactly one Quaffle. Each player can move in one of four directions, catch the Quaffle if it is on their cell, and throw it. A point is scored whenever a player leaves the Quaffle on the opposing team’s goal. If a player scores in their own goal, the other team gains the point. The Quaffle immediately resets to the center after each score. The game provides a sequence of moves, and we must output when goals occur and the final score.

The input grid is small, at most 99×99, and the number of steps can reach 10,000. Each action is guaranteed to be valid, so we do not need to handle invalid moves. Our task is therefore to faithfully simulate all moves, track who is carrying the Quaffle, check goal events, and print them in the correct order, along with the final score.

Edge cases include multiple players starting on the same cell, scoring in one’s own goal, and the Quaffle being thrown onto a goal immediately after catching. A naive simulation must carefully update both the player and ball positions at each step.

Approaches

The brute-force approach here is feasible because the grid and number of moves are small. We can maintain a mapping from player IDs to positions, keep track of the Quaffle’s position and carrier, and process each action sequentially. For movement actions, we update the player’s coordinates. For catching, we mark the Quaffle as carried. For throwing, we place it on the current cell. After each move, we check if the Quaffle is on a goal and update the score accordingly. This approach is correct and fast enough given the constraints, requiring O(T) time for T moves.

There is no asymptotically faster approach because every move must be processed to determine scoring events, and the constraints allow this direct simulation. We avoid any premature optimization such as event batching or precomputing paths, since the primary challenge is careful bookkeeping rather than algorithmic complexity.

Algorithm Walkthrough

1. Parse the grid and store the positions of all players and goals. Keep a separate variable for the Quaffle’s position and whether it is carried.
2. Initialize scores for both teams to zero.
3. For each action from 0 to T-1, extract the entity performing it and the action type. If it is a move, update the entity’s coordinates. If it is a catch, mark the player as carrying the Quaffle and clear the Quaffle’s grid position. If it is a throw, place the Quaffle at the player’s current cell and mark it as no longer carried.
4. After each action, if the Quaffle is on a goal, determine which team scores. If the goal belongs to the opposite team, the player’s team gains a point. If the goal belongs to the same team, the other team gains the point. Print the event with the current step index.
5. After scoring, reset the Quaffle to the center of the grid and mark it as not carried.
6. After all actions, print the final score in the format FINAL SCORE: r b.

Why it works: This algorithm maintains the invariant that the Quaffle is either on the field or carried by a player. Every move and goal is processed in chronological order. By updating positions and checking goals immediately after each action, we correctly capture the sequence of scoring events and the final result.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    grid = []
    players = {}
    goals_red = set()
    goals_blue = set()
    quaffle_pos = None
    quaffle_carrier = None

    for i in range(N):
        row = input().split()
        for j, cell in enumerate(row):
            if cell.startswith('R') and cell[1].isdigit():
                players[cell] = (i, j)
            elif cell.startswith('B') and cell[1].isdigit():
                players[cell] = (i, j)
            elif cell == 'RG':
                goals_red.add((i, j))
            elif cell == 'BG':
                goals_blue.add((i, j))
            elif cell == '.Q':
                quaffle_pos = (i, j)
        grid.append(row)

    T = int(input())
    actions = [input().split() for _ in range(T)]

    score_red = 0
    score_blue = 0

    center = ((N-1)//2, (M-1)//2)

    for t, act in enumerate(actions):
        entity = act[0]
        move = act[1]

        if move in 'UDLR':
            x, y = players[entity]
            if move == 'U':
                x -= 1
            elif move == 'D':
                x += 1
            elif move == 'L':
                y -= 1
            elif move == 'R':
                y += 1
            players[entity] = (x, y)
            if quaffle_carrier == entity:
                quaffle_pos = (x, y)
        elif move == 'C':
            # catching Quaffle
            quaffle_carrier = entity
            quaffle_pos = None
        elif move == 'T':
            # throwing Quaffle
            x, y = players[entity]
            quaffle_pos = (x, y)
            quaffle_carrier = None

        # check for scoring
        if quaffle_pos is not None:
            if quaffle_pos in goals_red:
                if entity[0] == 'R':
                    score_blue += 1
                    print(f"{t} BLUE GOAL")
                else:
                    score_red += 1
                    print(f"{t} RED GOAL")
                quaffle_pos = center
                quaffle_carrier = None
            elif quaffle_pos in goals_blue:
                if entity[0] == 'B':
                    score_red += 1
                    print(f"{t} RED GOAL")
                else:
                    score_blue += 1
                    print(f"{t} BLUE GOAL")
                quaffle_pos = center
                quaffle_carrier = None

    print(f"FINAL SCORE: {score_red} {score_blue}")

solve()

Walkthrough of Implementation

We maintain dictionaries for players and sets for goals for quick lookup. The Quaffle is represented by a tuple for its position and a variable tracking the carrier. Each action updates positions or carries appropriately. After every action, we immediately check whether the Quaffle is on a goal. Resetting the Quaffle to the center after a goal ensures that subsequent actions correctly continue the simulation. Off-by-one errors are avoided by careful indexing and integer division when computing the center.

Worked Examples

Sample 1:

This confirms scoring events and the correct resetting of the Quaffle.

Complexity Analysis

Constraints are small enough that this approach fits well within the limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()
    solve()
    return sys.stdout.getvalue().strip()

# provided sample
sample_input = """5 5
.. R1 .. B1 ..
RG .. .. .. BG
RG R0 .Q B0 BG
RG .. .. .. BG
.. R2 .. B2 ..
13
B2 U
B2 U
B2 L
B2 C .Q
B2 L
B2 L
B2 T
R0 R
R0 C .Q
R0 D
R0 R
R0 R
R0 T
"""
sample_output = """6 BLUE GOAL
12 RED GOAL
FINAL SCORE: 1 1"""
assert run(sample_input) == sample_output, "sample 1"

# custom test: player scores in own goal
custom_input = """3 3
RG .Q BG
R0 .. B0
.. .. ..
3
R0 C .Q
R0 R
R0 T
"""
custom_output = """2 BLUE GOAL
FINAL SCORE: 0 1"""
assert run(custom_input) == custom_output, "own goal"