Three Tankards and a Lie

Platform: CACTF2026 | Category: Coding | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2026-07-27 | Status: Solved Techniques: direct_swap_simulation, permutation_inversion

Summary

Task: Simulate positional swaps and report the final location of each queried starting item. Solution: Apply every swap to an identity array, invert the resulting permutation, and answer all queries by direct lookup.

Three Tankards and a Lie — CACTF2026

Description

N tankards initially hold correspondingly numbered items. M swaps exchange the contents at two positions. For each of Q queried starting positions/items, print that item's final position. Bounds: N <= 2000, M <= 5000, Q <= 2000.

The task is to follow items through a sequence of positional swaps. Each query names an item by the position where it started and asks for that item's position after all swaps.

Analysis

Let cup[pos] denote the identity of the item currently occupying position pos. Initially every item is in its correspondingly numbered tankard, so: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 text read-only • copy allowed Copy
cup[pos] = pos

A swap (a, b) acts on the current contents of positions a and b. It is therefore modeled directly as:

 python read-only • copy allowed Copy
cup[a], cup[b] = cup[b], cup[a]

After all swaps, cup maps each final position to the item found there. The queries require the opposite direction: given an item's initial identity p, return its final position. Build the inverse permutation once:

 text read-only • copy allowed Copy
position[cup[pos]] = pos

Then each query is answered by position[p] in constant time.

This distinction eliminates the main ambiguity: a query does not ask which item ends at position p; it asks where the item that started at p ends. The title's “Lie” is flavor only—there is no corrupt swap to detect. Given the modest bounds, neither range-query machinery nor permutation-composition optimization is necessary. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

1. Create the identity permutation cup = [0, 1, ..., N].
2. Read each swap and exchange the current contents at its two positions.
3. Allocate position and invert the final cup permutation.
4. For each queried item, print its entry in position.

For the sample with five tankards and swaps (1,3), (2,4), (3,5), (4,1), querying items 3 and 5 produces positions 4 and 3, respectively.

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import sys


def solve(data: list[int]) -> str:
    it = iter(data)
    n, m, q = next(it), next(it), next(it)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    # cup[position] is the item currently at that position.
    cup = list(range(n + 1))
    for _ in range(m):
        a, b = next(it), next(it)
        cup[a], cup[b] = cup[b], cup[a]

    # Invert the final permutation: item -> final position.
    position = [0] * (n + 1)
    for pos in range(1, n + 1):
        position[cup[pos]] = pos

    return "\n".join(str(position[next(it)]) for _ in range(q))


if __name__ == "__main__":
    values = list(map(int, sys.stdin.buffer.read().split()))
    if values:
        sys.stdout.write(solve(values))

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Correctness argument

Initially, cup[pos] is exactly the item at position pos. Each update exchanges precisely the two current contents named by the input, so this invariant remains true after every swap. Consequently, after all swaps, if cup[pos] = item, that item finishes at pos. Assigning position[cup[pos]] = pos for every position constructs the inverse mapping, and position[p] is therefore the required final position of queried starting item p.

Complexity

Initializing and inverting the permutation take O(N), applying the swaps takes O(M), and answering the queries takes O(Q). Total complexity is O(N + M + Q) time and O(N) memory. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Verification

The local sample produced exactly:

 text read-only • copy allowed Copy
4
3

Submitting the Python solver to the challenge's POST /run endpoint returned challengeCompleted: true and a flag value (redacted here). The implementation and contemporaneous solve notes are preserved in the task directory as solver.py and notes.md. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍