Unit 4 — Sets, Tuples & Sorting

Slide 1 of 25

Contest problems often ask: how many DIFFERENT things are there? Is this one present? Who ranks first? Sets store distinct values with fast membership, tuples keep a record's fields together, and sorted(key=...) orders records by a field you choose. Each idea is a short executable demo with a Notice, then a full stdin solver.
- Store distinct values in a set and test membership with in.
- Remove duplicates and build the union, intersection and difference of two groups.
- Keep a record's fields together in a tuple and unpack it in a for loop.
- Sort records with a named key function, in descending order, and with ties broken by a second field.
Lesson 1 — Sets: Distinct Values, Membership & Set Operations

A set keeps only DISTINCT values. Build one from a list with a {...} literal and .add; .discard removes a value if present.

names = ["Bo", "Ava", "Bo", "Ava", "Cy", "Bo", "Dia"]
distinct = {names[0]}          # a set literal, seeded with the first name
for name in names:
    distinct.add(name)         # adding a repeat changes nothing
distinct.discard("Bo")         # .discard removes Bo if present
print(len(distinct))

Output

Seven names collapse to the distinct ones; adding a repeat does nothing, and .discard("Bo") drops Bo — leaving 3.

Membership — value in set is a fast yes/no test.

roster = {"Ava", "Bo", "Cy", "Dia", "Eli"}
for name in ["Dia", "Zoe"]:
    if name in roster:
        print(name, "is on the roster")
    else:
        print(name, "is NOT on the roster")

Output

Dia is on the roster
Zoe is NOT on the roster

in answers membership directly; Dia is present, Zoe is not.

Union — every name in EITHER set. Build it with a loop and .add (no | operator).

first = {"Ava", "Bo", "Cy"}
second = {"Cy", "Dia", "Eli"}
either = set()
for name in first:
    either.add(name)
for name in second:
    either.add(name)
print(len(either))

Output

Adding every name from both sets into either gives the 5 distinct names.

Intersection — names in BOTH sets. Add a name only if it is also in the other (no & operator).

first = {"Ava", "Bo", "Cy", "Dia"}
second = {"Eli", "Ava", "Cy", "Dia"}
both = set()
for name in first:
    if name in second:
        both.add(name)
print(len(both))

Output

Only Ava, Cy, Dia are in both — 3 names.

Difference — names in the FIRST set but not the second, written first - second. Put it together: the program reads N M, then N first-group names and M second-group names from stdin, and prints how many are ONLY in the first group.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
m = int(tokens[1])
first = set()
second = set()
for position in range(n):
    first.add(tokens[position + 2])
for position in range(m):
    second.add(tokens[position + n + 2])
only_first = first - second
print(str(len(only_first)))

Run the full solver from this unit folder:
```
python assets/l1.py < assets/l1/1.in
```
Build two sets, then first - second keeps names unique to the first group.

Complexity: O(n + m) — each name is added once; set membership is fast.
Lesson 2 — Tuples & Sorting by a Chosen Field

A tuple groups a record's fields, e.g. (name, score). Unpack it with for name, score in records.

records = [("Ava", 8), ("Bo", 11), ("Cy", 6)]
for name, score in records:
    print(name, score)
total = 0
for name, score in records:
    total = total + score
print("total", total)

Output

Ava 8
Bo 11
Cy 6
total 25

Each record is one tuple; unpacking reads its fields by name while scanning.

Sort by one field — pass sorted a NAMED key function that returns the field to order by (no lambda).

records = [("Ava", 18), ("Bo", 9), ("Cy", 14)]

def by_score(record):
    return record[1]

ordered = sorted(records, key=by_score)
print(ordered[0])

Output

('Bo', 9)

by_score returns the score, so sorted orders ascending — Bo (9) comes first.

Sort descending — return the NEGATED field so the largest comes first.

records = [("Ava", 18), ("Bo", 9), ("Cy", 24)]

def highest_first(record):
    return -record[1]

ordered = sorted(records, key=highest_first)
print(ordered[0])

Output

('Cy', 24)

Returning -score flips the order — Cy (24) is first. No reverse= needed.

Compound key — break ties with a second field by returning a TUPLE (-score, name). Put it together: the leaderboard program reads N then N name score pairs and prints the top record: highest score first, ties broken by name.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
rows = []
for position in range(n):
    rows.append((tokens[1 + position * 2], int(tokens[2 + position * 2])))

def leaderboard_key(record):
    name, score = record
    return (-score, name)

ordered = sorted(rows, key=leaderboard_key)
first_name, first_score = ordered[0]
print(first_name + " " + str(first_score))

Run the full solver from this unit folder:
```
python assets/l2.py < assets/l2/1.in
```
leaderboard_key returns (-score, name), so sorted ranks by score (desc) then name (asc); ordered[0] is the winner.

Complexity: O(n log n) — the sort dominates.
- A set keeps only distinct values; .add ignores repeats and .discard removes a value if present.
- value in group is a fast yes/no membership test.
- Union and intersection come from a loop with .add; first - second keeps values only in the first set.
- for name, score in records: unpacks each tuple into named fields.
- sorted(records, key=leaderboard_key) with a key returning (-score, name) ranks by score, then by name.
You can now count distinct values, compare groups and rank records for a contest problem.

Unit 4 — Sets, Tuples & Sorting

Lesson 1 — Sets: Distinct Values, Membership & Set Operations

Lesson 2 — Tuples & Sorting by a Chosen Field