CCC 2021 · JUNIOR J4 · LISTS

Arranging Books

Minimum swaps to group L, M, S. The answer is a counting problem in disguise — you never need to perform the swaps.

❓ The question first

❓ THE QUESTION

Problem — Arranging Books

A shelf holds books of three sizes: L (large), M (medium), S (small). Valentina wants all the L books first, then all the M books, then all the S books. One swap exchanges any two books. What is the fewest number of swaps needed?

Input

One line: a string of L, M, S characters — the shelf from left to right.

LLSLM
Output

One integer: the minimum number of swaps.

2

🎬 The solution, step by step

The idea — count zones, never simulate:
  1. Count how many L, M, S exist. That fixes the three zones of the finished shelf.
  2. Count the misplaced books in each zone (an S sitting in the L-zone, etc.).
  3. Direct pairs (two books belonging in each other's zones) fix 2 books per swap → cost 1 each. What's left always forms 3-cycles → cost 2 each.
Animation — walk the official sample

💻 The code

s = input().strip()

count = {ch: s.count(ch) for ch in "LMS"}

zone = {}                        # where each zone starts/ends
start = 0
for ch in "LMS":
    zone[ch] = (start, start + count[ch])
    start += count[ch]

mis = {z: {c: 0 for c in "LMS"} for z in "LMS"}
for z in "LMS":                  # count wrong books per zone
    a, b = zone[z]
    for ch in s[a:b]:
        mis[z][ch] += 1

direct = (min(mis['L']['M'], mis['M']['L'])
        + min(mis['L']['S'], mis['S']['L'])
        + min(mis['M']['S'], mis['S']['M']))

misplaced = sum(mis[z][c] for z in "LMS" for c in "LMS" if z != c)
cycles = (misplaced - 2 * direct) // 3

print(direct + 2 * cycles)       # direct pairs: 1 each; 3-cycles: 2 each

⭐ Key points & traps

Trap — actually swapping: simulating swaps (bubble sort style) counts YOUR swaps, not the minimum. The contest asks for the fewest possible, which is a counting question: zones → misplaced → pairs and cycles.
Why a 3-cycle costs exactly 2: swap any two of the three — one lands correctly, the other two now form a direct pair — swap them. 2 total, and 1 is impossible because a single swap can put at most 2 books right, and in a cycle no single swap puts ANY book in its own zone… check Step 4's shelf if that feels surprising.
Edge cases: a shelf may contain no M's at all (two zones only) — the counting still works, the M-zone is just empty. Sample 1 (LMMMS) has zero misplaced books → 0.

✋ Your turn — predict first, then check

Shelf SML — minimum swaps?

Zones are one book each. S sits in the L-zone and L sits in the S-zone: a direct pair → 1 swap. Answer: 1.