Contest Python: USACO Bronze › Unit 4 — Sets, Tuples & Sorting

Exercises: Unit 4 — Sets, Tuples & Sorting

Each problem is a program that reads the whole input from stdin and prints the exact output (real contest style — no solve() wrapper): import sys; data = sys.stdin.read(), parse it, then print. Write each program in a .py file and run it with piped input, e.g. python my_solution.py < case.txt.

Exercise 1: Distinct Badge Count

The first line is N. The second line contains N badge colors. Print the number of distinct colors. Use a set so repeated colors count only once. In the sample, the last color is a new distinct color and must be counted.

Constraints. 1 <= N <= 100000. Each color is one word. A repeated scan for every color will not finish in time.

Sample Input

7
red blue red green blue yellow purple

Sample Output

How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use a set so repeated colors count only once.

For parents and teachers: report a problem

Exercise 2: Students in Both Clubs

The first line contains N M. The second line contains the N distinct names in the robotics club. The third line contains the M distinct names in the art club. Print how many students are in both clubs. Build the intersection with membership checks and .add(). In the sample, the final art-club name creates the third match.

Constraints. 1 <= N, M <= 100000. Each name is one word, and names do not repeat within one club. Comparing every robotics name with every art name will not finish in time.

Sample Input

4 4
Ava Ben Cy Dia
Zoe Ava Cy Dia

Sample Output

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Build the intersection with membership checks and .add().

For parents and teachers: report a problem

Exercise 3: Only on the First Roster

The first line contains N M. The second line contains N distinct names on the first roster. The third line contains M distinct names on the second roster. Print how many names appear on the first roster but not the second. Use set difference. In the sample, the final name on the first roster is part of the answer.

Constraints. 1 <= N, M <= 100000. Each name is one word, and names do not repeat within one roster. Comparing every name with every other name will not finish in time.

Sample Input

5 4
Ava Ben Cy Dia Ivy
Ben Cy Zoe Dia

Sample Output

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use set difference.

For parents and teachers: report a problem

Exercise 4: First Repeated Ticket

The first line is N. The second line contains N ticket codes in arrival order. Print the first code whose arrival repeats a code seen earlier, or NONE if no code repeats. Use set membership while scanning from left to right. In the sample, the first repeat occurs at the last position.

Constraints. 1 <= N <= 100000. Each ticket code is one word. Rescanning all earlier tickets for each arrival will not finish in time.

Sample Input

7
Q2 W5 E8 R1 T4 Y7 W5

Sample Output

W5

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use set membership while scanning from left to right.

For parents and teachers: report a problem

Exercise 5: Final Leaderboard

The first line is N. The next N lines each contain a one-word name and an integer score. Print all contestants, one per line as name score, sorted by score from highest to lowest and then by name alphabetically when scores tie. Store each contestant as a tuple and call sorted with a named key function that returns (-score, name). The sample's lowest-ranked contestant is both the final input record and the final record after sorting, so do not drop it.

Constraints. 1 <= N <= 100000. Names are distinct one-word strings, and 0 <= score <= 1000000. Repeatedly searching for the next contestant will not finish in time.

Sample Input

5
Mia 90
Zoe 100
Ava 100
Noah 80
Liam 70

Sample Output

Ava 100
Zoe 100
Mia 90
Noah 80
Liam 70

How this is checked: Checked by running your program on 2 test inputs (1 sample, 1 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Store each contestant as a tuple and call sorted with a named key function that returns (-score, name).

For parents and teachers: report a problem

Exercise 6: Last Player in the Top K

The first line contains N K. The next N lines each contain a distinct one-word name and an integer score. Rank players by score from highest to lowest and then by name alphabetically when scores tie. Print the name score record at rank K, where the best player has rank 1. Use tuples and sorted with a named compound key function. In the sample, the final input player changes the top K, and the answer is the last record in the retained top K after sorting.

Constraints. 1 <= K <= N <= 100000. 0 <= score <= 1000000. Repeatedly searching for the next-highest score will not finish in time.

Sample Input

6 4
Ana 95
Bo 88
Cy 91
Di 88
Eli 70
Fay 90

Sample Output

Bo 88

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use tuples and sorted with a named compound key function.

For parents and teachers: report a problem

Exercise 7: Unique Allowed Codes

The first line contains B N. The second line contains B distinct banned codes. The third line contains N submitted codes and may contain repeats. First collect the distinct submitted codes, then remove every banned code with .discard(). Print the number of distinct allowed codes that remain. In the sample, the last submitted code is a new allowed code.

Constraints. 1 <= B, N <= 100000. Each code is one word. Repeatedly rescanning the submissions or banned list will not finish in time.

Sample Input

3 8
red gray black
red blue green blue gray yellow green purple

Sample Output

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

First collect the distinct submitted codes, then remove every banned code with .discard().

For parents and teachers: report a problem

Exercise 8: Partner Groups

Challenge

The first line is N. The next N lines each contain a grade number and a one-word team color. Two students can form a pair only when both their grade and team color match. Each student can belong to at most one pair. Use a (grade, color) tuple as one dictionary key and print the total number of pairs. In the sample, the final student completes the last pair.

Constraints. 1 <= N <= 100000. 6 <= grade <= 8. Counting each group again after every student will not finish in time.

Sample Input

7
7 red
8 blue
7 red
8 green
8 blue
7 gold
7 gold

Sample Output

How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use a (grade, color) tuple as one dictionary key

For parents and teachers: report a problem

Exercise 9: Allowed Finalists

Challenge

The first line contains B N K. The second line contains B distinct banned names. The next N lines each contain a one-word name and an integer score, and a name may appear more than once. Ignore every record with a banned name. For each other name, keep only that contestant's highest score. Rank the remaining distinct contestants by score from highest to lowest and then by name alphabetically when scores tie. Print the first K names, one per line. Use set membership, tuple records, and sorted with a named compound key function. In the sample, the final record changes the finalists, and the Kth finalist is the last retained record after sorting.

Constraints. 1 <= B <= 100000. 1 <= K <= N <= 100000. After banned names and repeats are handled, at least K distinct allowed contestants remain. 0 <= score <= 1000000. Repeatedly rescanning records to find each finalist will not finish in time.

Sample Input

2 8 3
Kai Uma
Ava 50
Ben 80
Kai 100
Ava 90
Cora 85
Ben 70
Dax 40
Dax 88

Sample Output

Ava
Dax
Cora

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use set membership, tuple records, and sorted with a named compound key function.

For parents and teachers: report a problem

Back to Unit 4 — Sets, Tuples & Sorting