Understanding a Problem and Its Constraints

16 min · Intermediate

A fast solver spends the first minutes reading, not typing. What comes in, what must go out, and how big can the input get? The answers decide which solution is fast enough.

Split the statement into input, output and rule

Problem statement is the written task: what you receive (input), what you must produce (output) and the rule that links them. Read it twice before coding.

A statement hides three things: what you receive, what you must print, and the rule between them. Write each in one line before you write code.

Python

1# Statement: count the orders larger than the average order.2# Input: a list of order amounts. Output: one whole number.3def count_above_average(amounts):4    average = sum(amounts) / len(amounts)5    return sum(1 for amount in amounts if amount > average)6
7
8print(count_above_average([120, 80, 300, 100]))

Six boxes in order: read closely, work examples, list edge cases, brute force, make it faster, test and submit. Brute force and make it faster are highlighted. A note says that if step 5 breaks, step 4 is your answer key.

Example 1 · One sentence, two readings

Python

amounts = [100, 100, 100]average = sum(amounts) / len(amounts)print(sum(1 for a in amounts if a > average))print(sum(1 for a in amounts if a >= average))

Output

0
3

What this code does

"Larger than the average" and "at least the average" give different answers when orders tie.
The sample in the statement tells you which one is meant. Check it before you code.

The input is a list of numbers, the output is one count, and the rule is "bigger than the average". The comments are the plan.

Constraints set the speed you need

Constraints are the limits a problem promises about its input, such as how many items there can be and how large the values are. They tell you how fast your solution must be.

Limits such as n up to 100,000 tell you how many steps are allowed. Python runs roughly ten million simple steps a second, so a double loop over 100,000 items is far too slow.

Python

steps_per_second = 10_000_000for n in [1_000, 100_000]:    pairs = n * n    print(n, pairs, pairs / steps_per_second)

Example 2 · Turn a limit into a method

Python

1def suggest(n):2    if n <= 20:3        return "try every subset"4    if n <= 3_000:5        return "a double loop is fine"6    if n <= 1_000_000:7        return "one pass, or sort first"8    return "a formula or binary search"9
10
11for n in [15, 2_500, 200_000, 10**9]:12    print(n, suggest(n))

Output

15 try every subset
2500 a double loop is fine
200000 one pass, or sort first
1000000000 a formula or binary search

What this code does

The thresholds are rules of thumb for Python, based on about ten million steps a second.
Find n in the constraints first, then pick the method that fits.

A double loop over 1,000 items takes about a tenth of a second. Over 100,000 items it takes about a thousand seconds, so the limit decides the method.

Python integers do not overflow

Many judges warn about 32-bit overflow. A Python int grows as needed, so the warning does not apply. Large values only make the arithmetic a little slower.

Python

big = 10**18print(big * big)print(sum([big] * 5))

Example 3 · No overflow, still exact

Python

big = 2**200print(len(str(big)))print(big % 1_000_007)

Output

61
446616

What this code does

2**200 has 61 digits and Python keeps every one.
Problems that ask for "the answer modulo 1,000,007" are about keeping numbers small in other languages. In Python you can reduce at the end.

Example 4 · Whole units, not decimals

Python

print(0.1 + 0.2 == 0.3)print(10 + 20 == 30)print(round(0.1 + 0.2, 2) == 0.3)

Output

False
True
True

What this code does

Floats store binary approximations, so money in decimals can fail an equality check.
When the statement gives whole units (paise or cents), keep ints. Otherwise round before comparing.

Both results are exact. You still check the value range, because it tells you whether a number is a whole amount or needs decimals.

Restate the problem with a tiny example

Say the task in your own words and test it on a sample with three or four items. If your answer differs from the sample, you read the problem wrongly.

Python

1# Restated: for each customer, the largest single order.2orders = [("Asha", 250), ("Ravi", 90), ("Asha", 400)]3largest = {}4for name, amount in orders:5    largest[name] = max(largest.get(name, 0), amount)6print(largest)

The sample has two customers and three orders. The dictionary has two keys, so the reading matches the sample.

Next step

Check your understanding

10 quick questions

1# Statement: count the orders larger than the average order.2# Input: a list of order amounts. Output: one whole number.3def count_above_average(amounts):4 average = sum(amounts) / len(amounts)5 return sum(1 for amount in amounts if amount > average)6 7 8print(count_above_average([120, 80, 300, 100]))

Constraints set the speed you need

Constraints are the limits a problem promises about its input, such as how many items there can be and how large the values are. They tell you how fast your solution must be.

Limits such as n up to 100,000 tell you how many steps are allowed. Python runs roughly ten million simple steps a second, so a double loop over 100,000 items is far too slow.

1def suggest(n):2 if n <= 20:3 return "try every subset"4 if n <= 3_000:5 return "a double loop is fine"6 if n <= 1_000_000:7 return "one pass, or sort first"8 return "a formula or binary search"9 10 11for n in [15, 2_500, 200_000, 10**9]:12 print(n, suggest(n))

1# Restated: for each customer, the largest single order.2orders = [("Asha", 250), ("Ravi", 90), ("Asha", 400)]3largest = {}4for name, amount in orders:5 largest[name] = max(largest.get(name, 0), amount)6print(largest)