Learn to Code by Solving Problems: A Python Programming Primer Homepage for the book Learn to Code by Solving Problems: A Python Programming Primer

Solving USACO Photoshoot, the Conclusion

Hello everyone!

We’re back with part 2 of solving the USACO Photoshoot problem.

Please read the previous post first before continuing :)

At the end of that previous post, I talked about that there’s a super fast $O(n)$ solution to this problem.

It kind of surprised me that there was a way to do this in $O(n)$ time, TBH. After all, don’t we have to try all possible values for $A(1)$? And for each one, don’t we have to build out the whole $A$ list (or at least some of it) and test it?

If you need a refresher on this big O stuff, or you’ve never fully understood it (no judgment! :) ), then Learn to Code by Solving Problems has a whole chapter (Chapter 10) on this. It shows you:

Sometimes you can speed up an algorithm by replacing one data structure with another (like we did in Chapter 8 when replacing a list by a set). Other times you can use a binary search instead of a linear search (as we did in Chapter 9). Still other times you can introduce a Python dictionary into your solution or sort the input prior to processing it (as we did in Chapter 10). And sometimes, you just gotta come up with something that’s specific to the current problem you’re solving. That’s what we’re about to do here.

An Observation

We’re going to make a lot of progress today by looking at differences between consecutive values in the $B$ list.

To start, here’s a question: what do we get if we do $B[2] - B[1]$? That’s just taking the second value of $B$ and subtracting the first value. Remember that $B[i] = A[i] + A[i+1]$. So $B[2] - B[1] = A[2] + A[3] - (A[1] + A[2])$… and after simplifying that, we get $B[2] - B[1] = A[3] - A[1]$.

Now, we don’t know what $A[1]$ is. (If we knew, then we’d be done because we could just fill out the rest of $A$ using $B$, as we did in the previous post when we were complete-searching over all possible $A[1]$ values.)

But what we do know now is the difference between $A[1]$ and $A[3]$. Call this Fact 1. This Fact 1 might seem useless—really, who cares what the difference is between these two values? Well, just wait :)

So we know what $B[2] - B[1]$ gives us. What about $B[4] - B[3]$? (I’m just moving forward by two in $B$.)

Using the same pattern, we find that $B[4] - B[3] = A[5] - A[3]$. Call this Fact 2.

From Fact 1, we know the difference between $A[1]$ and $A[3]$. From Fact 2, we know the difference between $A[3]$ and $A[5]$. We can put these together and then we’d know the difference between $A[1]$ and $A[5]$.

We can keep going and get as many of these facts as we want. For any odd index $j$, we can figure out the difference between $A[1]$ and $A[j]$ or, in other words, how much bigger $A[j]$ is than $A[1]$.

We’re going to go through an example in a sec, but here’s the key thing: whichever of these value differences is smallest (relative to the same reference value, $A[1]$) must be the smallest value among all of these values. And we know that the smallest value of all must be $1$ (remember that we’re looking for an $A$ list that’s a permutation of the numbers from $1$ to $N$). So, if we can figure out which value in $A$ is $1$, then we also know what $A[1]$ is, because we know the difference between $A[1]$ and that value!

Oooook, I think we’re ready for an example bigtime.

An Example

Let’s use the same example from last time, this sample input:

6
9 5 7 9 5

Using the above observation, here’s what we learn about the values of $A$:

And that’s it. We have learned that among the values at indices $1$, $3$, and $5$, the one at index $3$ is smallest. If the value at index $3$ is the smallest one in $A$, then it has to have a value of $1$. And since the difference between $A[1]$ and $A[3]$ is $-4$, then $A[1]$ must be $1-(-4) = 5$.

From the previous post, we know that once we’ve figured out $A[1]$, then we can reconstruct the rest of $A$ using $B$. So we’ll be able to find that $A$ is $[5, 4, 1, 6, 3, 2]$, as needed.

Now, at this point, you might be thinking like this:

And the answer to that question is: yes.

It’s not good enough to only look at $A[1]$, $A[3]$, and $A[5]$. Those are only the odd indices. We also need to look at the even indices $A[2]$, $A[4]$, and $A[6]$, and figure out the smallest value among those three as well… because that might be the $1$!

Let’s see what the even indices give us, then. We can use the same algorithm as above, but this time we’re going to start with $B[3] - B[2]$. That will tell us the difference between $A[2]$ and $A[4]$. Then we can do $B[5] - B[4]$ to get the difference between $A[4]$ and $A[6]$, and so on.

Applying this to our running example, we learn this stuff:

So, if any of the values at even indices is the $1$, it’s got to be the value at index 6. That’s enough for us to get $A[2]$, and then we can use $A[2]$ to figure out $A[1]$. Then we can fill out $A[3]$ to the end of $A$ using $B$ as usual.

Key Point

This whole thing boils down to just two major steps:

That gives us two possible $A$ lists. There can’t be anymore! The first one is when $1$ is at an odd index. The second is when $1$ is at an even index. The $1$ can’t be anywhere else :)

The Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

# Convention in this program:
# In a list, index 0 is ignored (set to 0 placeholder value).
# The A and B lists in the problem description start
# at A[1] and B[1], so I wanted our lists to start at 1 as well.


# This is the same function as last time
def is_valid_permutation(lst):
    """
    lst is a list of integers.
    The integers are at lst[1], lst[2], ..., lst[n].

    Return True if lst is a permutation of the integers from 1 to n, False otherwise.
    """
    already_used = set()
    for i in range(1, len(lst)):
        # Already used? Out of bounds? Both bad!
        if lst[i] in already_used or lst[i] < 1 or lst[i] >= len(lst):
            return False
        already_used.add(lst[i])
    return True


# This program uses files; see Chapter 7 for review
input_file = open('photo.in')
output_file = open('photo.out', 'w')

n = int(input_file.readline())
b_lst = input_file.readline().split()
for i in range(len(b_lst)):
    b_lst[i] = int(b_lst[i])
b_lst = [0] + b_lst  # Per convention, put placeholder at index 0

# **Option 1** (the odd indices)

current_diff = 0  # Cumulative difference from index 1 to index i
smallest_diff = 0  # Smallest cumulative difference
for i in range(3, len(b_lst) + 1, 2):
    diff = b_lst[i - 1] - b_lst[i - 2]
    current_diff = current_diff + diff
    if current_diff < smallest_diff:
        smallest_diff = current_diff

start_val = 1 - smallest_diff
option1 = [0, start_val]
for i in range(2, len(b_lst) + 1):  # Generate rest of A list
    next_value = b_lst[i - 1] - option1[i - 1]
    option1.append(next_value)

# **Option 2** (the even indices)

current_diff = 0
smallest_diff = 0
for i in range(4, len(b_lst) + 1, 2):
    diff = b_lst[i - 1] - b_lst[i - 2]
    current_diff = current_diff + diff
    if current_diff < smallest_diff:
        smallest_diff = current_diff

second_val = 1 - smallest_diff  # This is A[2]
start_val = b_lst[1] - second_val  # Find A[1]
option2 = [0, start_val, second_val]
for i in range(3, len(b_lst) + 1):  # Generate rest of A list
    next_value = b_lst[i - 1] - option2[i - 1]
    option2.append(next_value)

# We want the smallest valid permutation...
if option1 < option2 and is_valid_permutation(option1):
    answer = option1
else:
    answer = option2

output_lst = []
for val in answer[1:]:
    output_lst.append(str(val))

output_file.write(' '.join(output_lst) + '\n')

input_file.close()
output_file.close()

A Final Observation

We know that there are at most two $A$ options for us to check (option1 and option2 in the code). Sometimes, like in our running example, they’re both valid permutations–in which case we choose the minimum one. But for some inputs, only one of them may be valid. (For example, try both options for this $B$ list: $[6, 4, 7, 6, 8]$.) We are guaranteed from the problem description that there’s at least one valid $A$, though :)

More Practice

Definitely a challenge coming up with problem-specific optimizations like that! That’s why, in the book, I focus on broad patterns that can help you solve many different problems (rather than ad hoc solutions that differ per problem). That’s the biggest bang for your buck. Still, it’s great practice to really dive into a problem looking for specific, targeted efficiency improvements.

What did you think of this problem? Want to see more like this?

Don’t forget to check the extra exercises for more practice with the material from the book.

Happy problem-solving!

Written on February 16th, 2025 by Daniel Zingaro
Feel free to share!

You may also enjoy: