Lists and maps

frequent

Many problems require you to store data and use it later. A list stores items in order, while a map stores values under a key such as a name or id. Python calls them list and dict; in C++, you'll usually use vector and map or unordered_map.

The choice depends on how you use the data:

Collect, then scan — store everything in a list and loop through it to find the answer (Silent Auction).
Store, then look up — store each value under a key and retrieve it when you need it (Group Work).

J2 Walkthrough: Silent Auction2021 · J2 · Original problem · DMOJ

A charity is having a silent auction where people place bids on a prize without knowing anyone else’s bid. Each bid includes a person’s name and the amount of their bid. After the silent auction is over, the winner is the person who has placed the highest bid. If there is a tie, the person whose bid was placed first wins. Your job is to determine the winner of the silent auction.

The first line of input contains a positive integer $N$ , where $1 \leq N \leq 100$ , representing the number of bids collected at the silent auction. Each of the next $N$ pairs of lines contains a person’s name on one line, and the amount of their bid, in dollars, on the next line. Each bid is a positive integer less than $2000$ . The order of the input is the order in which bids were placed.

Output the name of the person who has won the silent auction.

3
Ahmed
300
Suzanne
500
Ivona
450

Output for Sample Input 1

Suzanne

Explanation of Output for Sample Input 1

The highest bid placed was 500 and it was placed by Suzanne. Suzanne wins the silent auction.

2
Ijeoma
20
Goor
20

Output for Sample Input 2

Ijeoma

Explanation of Output for Sample Input 2

The highest bid placed was 20 and it was placed by both Ijeoma and Goor. Since Ijeoma’s bid was placed first, Ijeoma wins the silent auction.

Solution

Each bid is a pair — a name and an amount — and the winner is the highest amount, with ties going to the bid placed first. The input is exactly that sequence of pairs in placement order, so we read all of them into lists and scan afterwards: names holds the bidders and bids the amounts, with matching positions.

We track the index of the best bid rather than the bid itself, so the name comes along for free. The comparison is strict — a bid replaces the current best only if it is strictly higher — so on a tie, the earlier bid keeps the win. Sample 2 is exactly this case: Ijeoma and Goor both bid 20, and Ijeoma stays the winner.

Running the estimate: at most 100 bids, one comparison per bid in the scan — nowhere near any limit.

Since each bid is only compared once, we could skip the lists and track the best bid while reading. Collecting first and scanning afterwards is the pattern worth practicing, though — most problems need their input more than once, and separating "read the data" from "answer the question" keeps a solution easy to fix.

Implementation

n = int(input())

names = []
bids = []
for _ in range(n):
    names.append(input())
    bids.append(int(input()))

best = 0
for i in range(1, n):
    if bids[i] > bids[best]:
        best = i

print(names[best])

J4 Walkthrough: Group Work2022 · J4 · Original problem · DMOJ

A class has been divided into groups of three. This division into groups might violate two types of constraints: some students must work together in the same group, and some students must work in separate groups.

Your job is to determine how many of the constraints are violated.

The first line will contain an integer $X$ with $X \geq 0$ . The next $X$ lines will each consist of two different names, separated by a single space. These two students must be in the same group.

The next line will contain an integer $Y$ with $Y \geq 0$ . The next $Y$ lines will each consist of two different names, separated by a single space. These two students must not be in the same group.

Among these $X+Y$ lines representing constraints, each possible pair of students appears at most once.

The next line will contain an integer $G$ with $G \geq 1$ . The last $G$ lines will each consist of three different names, separated by single spaces. These three students have been placed in the same group.

Each name will consist of between 1 and 10 uppercase letters. No two students will have the same name and each name appearing in a constraint will appear in exactly one of the $G$ groups.

The following table shows how the available 15 marks are distributed at the Junior level.

Marks Awarded	Number of Groups	Number of Constraints
4 marks	$G \leq 50$	$X \leq 50$ and $Y = 0$
10 marks	$G \leq 50$	$X \leq 50$ and $Y \leq 50$
1 mark	$G \leq 100\,000$	$X \leq 100\,000$ and $Y \leq 100\,000$

The following table shows how the available 15 marks are distributed at the Senior level.

Marks Awarded	Number of Groups	Number of Constraints
3 marks	$G \leq 50$	$X \leq 50$ and $Y = 0$
5 marks	$G \leq 50$	$X \leq 50$ and $Y \leq 50$
7 marks	$G \leq 100\,000$	$X \leq 100\,000$ and $Y \leq 100\,000$

Output an integer between $0$ and $X+Y$ which is the number of constraints that are violated.

1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE

Output for Sample Input 1

Explanation of Output for Sample Input 1

There is only one constraint and it is not violated: ELODIE and CHI are in the same group.

3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L

Output for Sample Input 2

Explanation of Output for Sample Input 2

The first constraint is that A and B must be in the same group. This is violated.

The second constraint is that G and L must be in the same group. This is violated.

The third constraint is that J and K must be in the same group. This is not violated.

The fourth constraint is that D and F must not be in the same group. This is violated.

The fifth constraint is that D and G must not be in the same group. This is not violated.

Of the five constraints, three are violated.

Solution

The constraints arrive before the groups do, so we read the X same-group constraints and Y separate-group constraints into two lists of pairs before seeing any groups. Then we read the G groups and record each student's group number in a map keyed by name — all three names on group line i map to i.

With the map built, every constraint is two lookups and one comparison. A same-group constraint is violated when the two students are not in the same group; a separate-group constraint is violated when they are.

Running the estimate: the full-size subtask allows G, X, and Y up to 100 000. Building the map is 300 000 assignments, and checking the constraints is 200 000 pairs of constant-time lookups — a few million operations in total, well within limits. Without the map, checking a constraint means scanning the groups to find each student: up to 100 000 constraints times 100 000 groups, tens of billions of operations across the whole run. That scan-inside-a-loop is exactly what the map removes, and it is what the last subtask is testing.

Two guarantees in the statement keep the code short. Every constrained student appears in exactly one group, so no lookup can fail. And X or Y may be zero — the empty lists simply check nothing.

Implementation

x = int(input())
same = []
for _ in range(x):
    a, b = input().split()
    same.append((a, b))

y = int(input())
diff = []
for _ in range(y):
    a, b = input().split()
    diff.append((a, b))

group = {}
g = int(input())
for i in range(g):
    a, b, c = input().split()
    group[a] = i
    group[b] = i
    group[c] = i

violations = 0
for a, b in same:
    if group[a] != group[b]:
        violations += 1
for a, b in diff:
    if group[a] == group[b]:
        violations += 1

print(violations)

Summary

The choice between a list and a map usually comes down to how you access the data. If you need to scan everything, a list is fine. If you need to jump to a specific item by name or id, the map pays for itself immediately — as Group Work shows, replacing a scan-inside-a-loop with a single lookup is often the difference between passing the last subtask and timing out.

Both structures appear in almost every module from here on.

Lists and mapsCopy Anchor Link

J2 Walkthrough: Silent Auction2021 · J2 · Original problem · DMOJ

Problem Description

Input Specification

Output Specification

Sample Input 1

Output for Sample Input 1Copy Anchor Link

Explanation of Output for Sample Input 1Copy Anchor Link

Sample Input 2

Output for Sample Input 2Copy Anchor Link

Explanation of Output for Sample Input 2Copy Anchor Link

SolutionCopy Anchor Link

ImplementationCopy Anchor Link

J4 Walkthrough: Group Work2022 · J4 · Original problem · DMOJ

Problem Description

Input Specification

Output Specification

Sample Input 1

Output for Sample Input 1Copy Anchor Link

Explanation of Output for Sample Input 1Copy Anchor Link

Sample Input 2

Output for Sample Input 2Copy Anchor Link

Explanation of Output for Sample Input 2Copy Anchor Link

SolutionCopy Anchor Link

ImplementationCopy Anchor Link

SummaryCopy Anchor Link

On this page

Lists and maps

Output for Sample Input 1

Explanation of Output for Sample Input 1

Output for Sample Input 2

Explanation of Output for Sample Input 2

Solution

Implementation

Output for Sample Input 1

Explanation of Output for Sample Input 1

Output for Sample Input 2

Explanation of Output for Sample Input 2

Solution

Implementation

Summary