One loop for each choice
When a candidate is made of a few separate choices, a complete search has one loop for each choice. Two loops list every pair, and three loops list every triple. Each added loop multiplies the number of candidates, so the first thing to settle about a brute-force program is which choices need a loop. Here is a problem with three choices.
An envelope holds bills. Each bill is worth 10000, 5000 or 1000 yen, and together they are worth yen. Find how many bills of each kind the envelope could hold.
The input is one line with and . Print three counts, of 10000-yen, 5000-yen and 1000-yen bills, that make exactly bills worth yen; any valid answer is accepted. If no counts work, print -1 -1 -1.
Constraints
- is a multiple of 1000
Sample 1 · Input
9 45000
Output
4 0 5
Sample 2 · Input
20 196000
Output
-1 -1 -1
Sample 3 · Input
1000 1234000
Output
14 27 959
Sample 4 · Input
2000 20000000
Output
2000 0 0
In the first sample, 9 bills are worth 45000 yen. Four 10000-yen bills and five 1000-yen bills are one answer, since . Nine 5000-yen bills are another, and the judge accepts either.
A candidate is a triple of counts : bills of 10000 yen, of 5000 and of 1000. The direct search runs three nested loops, each from 0 to , and checks two conditions for every triple: the counts add up to , and the values add up to . For the largest input, , the loops visit
Even at simple operations a second that is about 80 seconds, and AtCoder gives this problem 2 seconds.
Compute the last count from the other two
Nearly all of those triples fail the first condition, and the program does not have to visit them to know it. Once and are chosen, exactly one value of makes bills in total:
So the third loop is not needed. We loop over and , compute , and check only the total value. The inner loop can stop early as well. A count cannot be negative, so runs from 0 to and no further.
The pairs the two loops visit
For the first sample, where , the two loops visit the pairs in this triangle:
Every valid triple is still found, because its and are a pair in the triangle and its is the value we compute. The triangle has pairs with , then pairs with , and so on down to a single pair, which makes in all. For that is
about 4,000 times fewer than the triples, and a small fraction of a second of work.
Otoshidama with two loops
The function returns the first triple that has the right value, or three -1s when the loops end without finding one.
def otoshidama(n, y):
for a in range(n + 1):
for b in range(n - a + 1):
c = n - a - b
if 10000 * a + 5000 * b + 1000 * c == y:
return a, b, c
return -1, -1, -1
n, y = map(int, input().split())
print(*otoshidama(n, y))On the first sample the program prints 0 9 0, where the card shows 4 0 5. The loops reach , before , , and the problem accepts any valid answer.
The third loop could be dropped because the statement fixes once and are known. Any choice that the statement determines from the others can be computed in the same way, with no loop of its own.
Loop over the possible answers
In Otoshidama the candidates were counts of bills. In the next problem the candidates that the statement suggests are triples of positions in a string. There are far too many of them, and the search loops over the possible answers instead.
You get a string of digits. Erase all but three of its digits and read the three that remain, in their order in , as a 3-digit PIN; the PIN may start with 0. Count how many different PINs can be made this way.
The input is on the first line and on the second. Print the count.
Constraints
- is a string of digits
Sample 1 · Input
4 0224
Output
3
Sample 2 · Input
6 123123
Output
17
Sample 3 · Input
19 3141592653589793238
Output
329
In the first sample is 0224, so exactly one digit is erased. Erasing the first digit leaves 224, erasing either 2 leaves 024, and erasing the 4 leaves 022. Two of the four results are the same PIN, so the answer is 3.
The direct search follows the statement: it chooses the three positions to keep, reads the PIN they spell, and counts the different PINs it has seen. Three nested loops over positions make that choice, and for they run
which is more than twelve hours of work even at operations a second.
But the answer counts PINs, and only 1,000 PINs exist, from 000 to 999. So we turn the search around. The candidates are the 1,000 PINs, and the check asks whether a PIN can be made from , that is, whether its three digits occur in in that order. One pass over is enough for that check, as the next section shows, so the whole search takes at most
That is 150,000 times less work than the search over positions.
Check one PIN in one pass
To check a PIN, we look for its first digit from the start of and take the earliest place where it occurs. We look for the second digit after that place, and for the third digit after the second:
123123, the digits of PIN 213 are found at indices 1, 3 and 5. PIN 321 finds its 3 at index 2 and its 2 at index 4, and no 1 comes after index 4.Taking the earliest place each time is safe. Suppose a PIN can be made with some later occurrence of its first digit. Its other two digits then come after that occurrence, so they also come after the earliest one, and the earliest one works as well. The same argument applies to the second digit.
Count the PINs that can be made
In the program, can_make is the check, and the three loops in count_pins list the candidates, one loop for each digit of the PIN.
s.find(digit, start) returns the first position at or after start where digit occurs, or -1 when there is none.
def can_make(s, pin):
pos = -1
for digit in pin:
pos = s.find(digit, pos + 1)
if pos == -1:
return False
return True
def count_pins(s):
digits = "0123456789"
count = 0
for a in digits:
for b in digits:
for c in digits:
if can_make(s, a + b + c):
count += 1
return count
n = int(input())
s = input()
print(count_pins(s))Try PINs on the samples
For the second sample, 123123, the program prints 17. The demo runs the check on that string and opens on PIN 213. Type another PIN, such as 321, or step through them in order. The count of PINs that can be made is shown under the controls, and buttons load the other two samples.
Time and memory of the two programs
- Otoshidama
time, memory - About pairs of counts, each checked with a few multiplications. Nothing is stored.
- Lucky PIN
time, memory - At most steps. The 1,000 is the same for every input, so Big O leaves it out as a constant factor. The memory is the string itself.
Common brute force mistakes
Letting the inner loop of Otoshidama run to .
- Where it breaks
- For and , the pair , gives and , so the program prints
1 1 -1instead of-1 -1 -1. - The fix
- Stop the inner loop at , so that is never negative.
Looking for every digit of the PIN from the start of .
- Where it breaks
- On
0224every PIN made of the digits 0, 2 and 4 then passes, including420, and the program prints 27 instead of 3. - The fix
- Look for each digit after the place where the previous one was found.
Recall In Otoshidama, why is it safe to loop over only a and b, and could we loop over b and c instead?
Every valid triple has , so its is , and the loops over and reach it. Any two of the counts work the same way: looping over and and computing visits the same number of pairs.
