Standard input and output
Every problem in this course is checked by a judge, a program that runs our solution on tests we do not get to see and compares what it prints with the expected output. So before any algorithm, a solution has to read the input in the layout the statement describes, print the answer in the layout the statement asks for, loop over exactly the right positions, and keep its numbers in a type that is large enough. This lesson is about those parts of a program.
We will use one small task for most of the lesson. A sensor took readings, and we want to count the readings that are at least a threshold . The first line of the input holds and , and the second line holds the readings:
5 64 8 2 8 6The readings that are at least 6 are the two 8s and the final 6, so the program should print:
3On Codeforces, AtCoder, CSES and newer USACO problems, the input arrives on standard input, which is what input() reads, and the answer goes to standard output, which is where print writes. The whole program is:
n, t = map(int, input().split())
readings = list(map(int, input().split()))
count = 0
for value in readings:
if value >= t:
count += 1
print(count)On the input above, the program prints 3.
input() returns the next line of the input as a string, here "5 6". .split() cuts that string at its spaces into the pieces "5" and "6", and map(int, ...) turns each piece into an integer, so the first line of the program sets n to 5 and t to 6. The second line reads the readings the same way and keeps them in a list. input() reads one line at a time, so the program calls it once for each line the statement describes. The loop never uses n, because the list knows its own length, but n still has to be read: it shares a line with t.
The comparison is >= because the statement says “at least”, which includes a reading equal to the threshold. With > the program would miss the final 6 and print 2.
Check the loop by hand
Before submitting a program, we run it by hand on the sample. Here are the five readings, with the three that are at least 6 highlighted:
The table follows the loop through them, one row for each iteration, with the value of count at the end of it.
| Position | Reading | At least 6? | count afterwards |
|---|---|---|---|
| 0 | 4 | no | 0 |
| 1 | 8 | yes | 1 |
| 2 | 2 | no | 1 |
| 3 | 8 | yes | 2 |
| 4 | 6 | yes | 3 |
After every row, count is the number of readings so far that are at least 6. A statement like that, true at the same point of every iteration, is called a loop invariant, and three checks prove the loop correct. It is true before the first iteration, when no reading has been looked at and count is 0. If it is true when an iteration starts, it is still true when the iteration ends, because the iteration adds 1 exactly when its reading is at least 6. So it is true after every iteration, including the last, when “the readings so far” are all of them and count is the answer.
Worked example
Step through the count
The trace runs the same loop one reading at a time. Its buttons load three more inputs: one with two readings equal to the threshold, one with no readings at all, where the loop does not run and the count stays 0, and one where no reading reaches the threshold.
Start before the first reading. No readings have been counted.
- count
- 0
Change the example input
Current result: 3
Print exactly what the statement asks for
The judge compares our output with the expected output as text. If the program prints Answer: 3 where 3 is expected, the judge marks it wrong although the number is right, and the same goes for a line of debugging output that was left in.
When the answer is a list of values, the statement says how to lay them out, for example on one line with a space between them, or one on each line. Suppose the task asked for the qualifying readings themselves, on one line. For our input the expected output would be 8 8 6:
n, t = map(int, input().split())
readings = list(map(int, input().split()))
kept = [value for value in readings if value >= t]
print(*kept)On the input above, the program prints 8 8 6.
print(*kept) prints the values of the list with one space between them and then ends the line. print(kept) would print [8, 8, 6], brackets and commas included, and the judge would mark that wrong. For one value per line, print each value in a loop.
Verdicts
After a submission the judge reports a verdict, such as the four below. AtCoder shortens them to AC, WA, RE and TLE.
| Verdict | What happened | A usual cause in a first program |
|---|---|---|
| Accepted | Every test printed the expected output within the time and memory limits. | None. |
| Wrong answer | The program finished, and on some test its output differs from the expected output. | An extra label or debugging line, > where the statement says “at least”, or a case the sample does not show, such as the smallest input the statement allows. |
| Runtime error | The program crashed. | An index past the end of a list, or reading a number where the input has none. |
| Time limit exceeded | The program was still running when the time limit passed. | A loop that never ends, or a method that needs too many steps for the limits. The Time complexity lesson is about the second. |
Judges that call a function or use files
Not every judge uses standard input and output. These are the judges this course takes problems from:
| Judge | Input | Output |
|---|---|---|
| CSES, Codeforces, AtCoder | standard input | standard output |
| USACO, December 2020 onwards | standard input | standard output |
| USACO, before December 2020 | the file the statement names, such as mixmilk.in | the matching .out file |
| LeetCode | the arguments of a function we write | the function's return value |
On LeetCode there is nothing to read and nothing to print. The statement gives the name and the parameters of a function. The judge calls that function with the input already turned into numbers and lists, and checks the value it returns. Here is a LeetCode problem whose loop is close to our counting loop:
You get a list nums. Return a list of the same length whose value at position is the sum of nums[0] through nums[i].
Constraints
Sample 1 · Input
nums = [1,2,3,4]
Output
[1,3,6,10]
Sample 2 · Input
nums = [3,1,2,10,1]
Output
[3,4,6,16,17]
For the first sample, the input and the list to return are:
The answers are 1, then , then , then . Each answer is the previous answer plus the next value, so the loop keeps the sum so far in total. Its invariant is that after each iteration total is the sum of the values read so far, which is the value to record:
def running_sum(nums):
total = 0
out = []
for x in nums:
total += x
out.append(total)
return out
print(*running_sum([1, 2, 3, 4]))Output: 1 3 6 10.
The function returns the list and prints nothing, and LeetCode checks the returned value. The print line under the function is ours: it calls the function on the first sample so that the listing can be run here, and it is not part of a submission. On LeetCode itself the function is a method of a class named Solution. The editor supplies the class and the method's first line, which names it runningSum and gives it the parameter self before nums. Our Python listings name functions the Python way, running_sum, and leave out the class, so keep the editor's first line when you submit and put the body under it.
USACO problems from before December 2020 use files. The statement names an input file and an output file, such as mixmilk.in and mixmilk.out for USACO Mixing Milk, and the program must read the first and write the second. The simplest way is to point standard input and standard output at the two files at the start of the program, and to write everything after that as usual:
sys.stdin = open("mixmilk.in")
sys.stdout = open("mixmilk.out", "w")Loop bounds
Many loops run over the positions of a list, and a bound that is off by one is an easy bug to write in them. A list of length has positions 0 to . range(n) produces exactly those numbers, because it starts at 0 and stops before . In general range(a, b) starts at and stops before , so its loop runs times. A third argument is the step: range(0, n, 2) counts up in twos, and range(n - 1, -1, -1) counts down from and stops before , so its last value is 0. The table lists several forms, with the values each one gives when .
| Loop | Values of i for n = 5 | Iterations | Used for |
|---|---|---|---|
range(n) | 0, 1, 2, 3, 4 | every position | |
range(1, n + 1) | 1, 2, 3, 4, 5 | the numbers 1 to | |
range(n - 1) | 0, 1, 2, 3 | each position with the one after it, a[i] and a[i + 1] | |
range(n - 1, -1, -1) | 4, 3, 2, 1, 0 | every position, last to first | |
range(0, n, 2) | 0, 2, 4 | half of , rounded up | every second position |
Statements that count from 1
Many statements number things from 1 and include both ends, as in “the readings in positions 2 through 5”. Lists number from 0, so position of the statement is index :
Positions through are therefore the indices from up to, but not including, . That loop runs times: positions 2 through 5 are readings.
Large numbers and large inputs
A statement also gives limits for its input. Let's say ours are
Limits like these decide whether a method is fast enough, once you count the steps it takes. Two simpler decisions come before that one: whether the numbers fit in the type that holds them, and how to read that much input.
Choose a type large enough
The count is at most , which is small. Now suppose the task asked for the sum of the qualifying readings. In the worst case all readings qualify and each of them is :
Python integers have no fixed size. They grow to whatever the value needs, so this sum is computed exactly and nothing has to be declared. The size of a number still matters once it meets a float, and the usual place is division: / always produces a float, and a float keeps only about 16 significant digits. The listing adds three readings of and then divides , a 19-digit number, by 3 in both ways:
readings = [10**9, 10**9, 10**9]
total = 0
for value in readings:
total += value
print(total)
print(10**18 // 3)
print(int(10**18 / 3))Prints 3000000000, then 333333333333333333 and 333333333333333312.
// divides integers exactly and gives 333333333333333333. / goes through a float, and turning its result back into an integer gives 333333333333333312, which is off by 21. When the answer is an integer, divide with //.
Read a large input quickly
Two hundred thousand readings on one line are no trouble for our program, which calls input() only twice. The slow case is a large input spread over many lines, because every call to input() does more than read a line: it also checks whether the input comes from a keyboard and flushes the output. On our laptop, reading numbers, one per line, and adding them up took 0.65 seconds with one call to input() per line. Reading the whole input at once and splitting it took 0.07 seconds. Here is the counting program written that way:
data = sys.stdin.read().split()
n, t = int(data[0]), int(data[1])
count = 0
for i in range(2, 2 + n):
if int(data[i]) >= t:
count += 1
print(count)On the input above, the program prints 3.
sys.stdin.read() returns the whole input as one string, and .split() cuts it at every space and line break. For our sample, data is ["5", "6", "4", "8", "2", "8", "6"]: the pieces in order, with the line layout gone. The readings are the pieces from index 2 on, which is the loop range(2, 2 + n). The pieces are still strings, so each one is converted with int where it is used.
A smaller change is to write input = sys.stdin.readline at the top of a program and leave the rest alone. That version took 0.12 seconds on the same test. sys.stdin.readline only reads the line, and it keeps the line break at its end. int and .split() ignore the line break, but text keeps it: on the line abc the call returns "abc\n", four characters long, so once input has been replaced, a line of text is read with input().rstrip().
Read a grid and visit every cell
Many problems give a grid: the number of rows and the number of columns on the first line, and then lines of characters each. In this one # is a wall and . is an empty cell, and the task is to count the walls:
3 4.#.#....#...This grid has three walls, so the expected output is 3.
h, w = map(int, input().split())
grid = [input() for _ in range(h)]
walls = 0
for r in range(h):
for c in range(w):
if grid[r][c] == '#':
walls += 1
print(walls)On the input above, the program prints 3.
Each row is read as one string, so grid is a list of strings, and grid[r][c] is the character in row and column , both counted from 0. A grid of numbers is read the same way with each line split into integers: grid = [list(map(int, input().split())) for _ in range(h)].
The outer loop takes the rows in order, and for each row the inner loop runs through every column before the outer loop moves on. The inner body therefore runs once for each pair of a row and a column, times in all. The two loops have different bounds. With h used for both, the fourth column would never be visited, and on this grid the program would print 2.
Reach cells with an index formula
A loop does not have to visit every cell. When the cells we need follow a pattern, their positions can be computed from the loop variable.
You get a square grid mat of side . Return the sum of the values on its two diagonals: the primary diagonal from the top-left corner to the bottom-right, and the secondary diagonal from the top-right corner to the bottom-left. A cell on both diagonals counts once.
Constraints
Sample 1 · Input
mat = [[1,2,3],[4,5,6],[7,8,9]]
Output
25
Sample 2 · Input
mat = [[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1]]
Output
8
In the first sample the primary diagonal holds 1, 5 and 9, and the secondary diagonal holds 3, 5 and 7. The centre 5 lies on both and counts once, so the answer is .
Two loops over all cells, with a test for each cell, would work. But every row holds one cell of each diagonal, and we can say where they are. In row , the primary diagonal is at column . The secondary diagonal is at the last column, , in row 0, and it moves one column to the left with each row, so in row it is at column . One loop over the rows reaches both.
def diagonal_sum(mat):
n = len(mat)
total = 0
for i in range(n):
total += mat[i][i] + mat[i][n - 1 - i]
if n % 2 == 1:
total -= mat[n // 2][n // 2]
return total
print(diagonal_sum([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))Output: 25, the first sample.
When is odd, the two formulas name the same cell in the middle row, mat[n // 2][n // 2], and the loop has added it twice, so the function subtracts it once. On the first sample the loop adds up 30, and . When is even the diagonals share no cell, and the second sample gives 8 with nothing subtracted.
Iterations of each loop
- One loop over a list
iterations - The counting loop looks at each reading once: 200,000 iterations at our limit.
- Two loops over a grid
iterations - 12 for the grid above, and for a grid of 1,000 rows and 1,000 columns.
- One loop with an index formula
iterations - The diagonal sum reads two cells per row: 100 iterations for the largest grid allowed, 100 by 100, where two loops over every cell would take 10,000.
Common input and loop mistakes
In Python, converting a whole line of several numbers with
int.- Where it breaks
int(input())on the line5 6raisesValueError, which the judge reports as a runtime error.- The fix
- Split the line first:
n, t = map(int, input().split()).
In Python, reading
a[i - 1]wheniis 0.- Where it breaks
- On
[4, 8, 2]it readsa[-1], which is the last value, 2. A negative index is not an error in Python, so the loop compares the first value with the last one and carries on. - The fix
- Start the loop at index 1 when its body reads
a[i - 1].
In C++, bounding a loop by
v.size() - 1.- Where it breaks
- The type of
v.size()has no negative values, so on an empty vectorv.size() - 1is 18,446,744,073,709,551,615 and the loop runs far past the end. - The fix
- Store the length in an
int nfirst, or write the condition asi + 1 < n.
Recall A statement numbers the readings from 1 and asks for the sum of readings 3 through 7. Which loop visits them in a list that starts at index 0, and how many readings is that?
Readings 3 through 7 are indices 2 through 6, which is range(2, 7). It runs times, the same as .
One more grid problem
A problem to try with the loop bounds of this lesson:
Judge problems
- Rotate Image(opens the judge in a new tab) ↗
Turn a square grid a quarter turn clockwise without building a second grid. Two loops you can already write do it: swap
m[r][c]withm[c][r]for every pair with , then reverse each row. The inner loop of the swap starts atr + 1. Started at 0, it would swap every pair twice, which undoes the swaps.