Best Algorithm for solving USACO: Photoshoot - Python I was trying to solve this problem with Python 3.8. I couldn't find a way other than to brute-force calculate all the possible permutations then check which permutation was valid. The program works fine, but as it's O(n!) time complexity (I think) it takes extraordinarily long when the input has a length of, say, 1000.
My code:
from itertools import permutations as permute

fin = open(&quot;photo.in&quot;, &quot;r&quot;)
fout = open(&quot;photo.out&quot;, &quot;w+&quot;)

useless, line = fin.readlines()

nums = [int(i) for i in line.split(&quot; &quot;)]

def main(nums):
    foo = [i+1 for i in range(len(nums)+1)]
    bar = permute(foo)
    
    for permutation in bar:
      boo = False
      for i in range(1, len(permutation)):
          if permutation[i]+permutation[i-1] != nums[i-1]:
              boo = False
              break
          else:
            boo = True
      
      if boo:
          return permutation

final = &quot; &quot;.join([str(i) for i in main(nums)])
fout.write(final)

fin.close()
fout.close()

I'm not sure how to optimize this code. Should I create my own permutation generator function and then check along the way instead of getting the whole thing at once? Or is there an algorithm that I'm not seeing?
A short problem description:
Given a list N of length n integers, find a permutation of the numbers 1 through n+1 in which every element of the permutation plus the next one is equal to the corresponding number of N.
Edit: The generator approach did not work.
Mathematical approach
Let us assume the following notation:
$$ \mathbb{B} = \sum_{i = 1}^{n - 1} b_i = b_1 + b_2 + \cdots + b_{n-1} $$
As mentioned earlier in comments, you have set of interdependent equations as follows:
$$
\begin{align}
b_1 &amp;= a_1 + a_2 \\
b_2 &amp;= a_2 + a_3 \\
b_3 &amp;= a_3 + a_4 \\
\vdots \\
b_{n - 1} &amp;= a_{n - 1} + a_n \\
\end{align}
$$
The above is \$ n - 1 \$ sets of equations, and the last equation you can derive from those is:
$$
\begin{align}
\sum_{i = 1}^{n - 1} b_i &amp;= \sum_{i = 1}^{n} a_i + \sum_{j = 2}^{n - 1} a_j \\
\implies \mathbb{B} + (a_1 + a_n) &amp;= 2 \times \left( \sum_{i = 1}^{n} a_i 
\right) \\
\implies a_1 + a_n &amp;= 2 \times \left( \dfrac{n (n + 1)}{2} \right) - \mathbb{B} \\
&amp;= \left( n \cdot (n + 1) \right) - \mathbb{B} \tag{1}
\end{align}
$$

Now, let's see what happens if we try the summation with a slight variation:
$$
\begin{align}
\sum_{i = 1}^{n - 1} \left[ (-1)^{i + 1} \cdot b_i \right] &amp;= b_1 - b_2 + b_3 - \cdots \cdots (-1)^{n - 2} b_{n - 1} \\
&amp;= (a_1 + a_2) - (a_2 + a_3) + (a_3 + a_4) - \cdots \cdots + (-1)^n (a_{n - 1} + a_n) \\
&amp;= a_1 + (-1)^{n} a_n \tag{2}
\end{align}
$$
Now, there would be 2 cases; 1 is fairly straight to solve:
Case 1: \$ n \$ is odd
The equation 2 becomes: $$ a_1 - a_n = \sum_{i = 1}^{n - 1} \left[ (-1)^{i + 1} \cdot b_i \right] $$
giving you the direct result (adding equation to above):
$$
a_1 = \dfrac{1}{2} \left( \sum_{i = 1}^{n - 1} \left[ (-1)^{i + 1} \cdot b_i \right] + n^2 + n - \mathbb{B} \right)
$$
Case 2: \$ n \$ is even
This gives you the same result as equation 1, therefore the replacement operation from SylvainD's answer comes into play. I'll leave this for the programming specific solution.

Program/code review

Use the names of variables which are closer to words used in problem statement. This makes it easier to go through code and question at the same time.

The photo.in serves no purpose once it has been read, use a contextual open for this:
with open(&quot;photo.in&quot;, &quot;r&quot;) as file_in:
    num_cows = int(file_in.readline())
    summations = map(int, file_in.readline().split(&quot; &quot;))


Same as above, the photo.out serves no purpose until you want to write:
with open(&quot;photo.out&quot;, &quot;w+&quot;) as file_out:
    file_out.write(&quot; &quot;.join(output_string))