How to solve USACO Bronze 2020 Jan Photoshoot in O(N)?

The problem is here: USACO

I coded and solved the problem with the O(N^2) solution (the one where you try out all possible a0).

However, the official solution has a bonus which asks you to come up with an O(N) solution.

I think I got the answer to the case where there is an even number of sums.
If the sums are b1, b2, …, bn - 1, where n is odd, I subtract the sum of b2 + b4 + … + bn - 1 from the total (which is n * (n + 1)), which gives me a0. Then, I can calculate the rest of the permutation.

But I can’t think of the O(N) solution to the case with the odd number of sums. Can anyone help? Thanks in advance.

1 Like

There are at most two values of a_1 such that \min(a_1,a_2,\dots,a_N)=1. You can find them in O(N) and test them in O(N).

1 Like

Interesting! Sorry to bother you again, but how did you get to this solution?
I don’t quite understand why it works yet (e.g. why are there at most two values?).
Thanks!

@Benq
I solved it in O(N) using your solution! Thanks so much!
However, I’m still confused about why there are at most two values of a1. Can you help?
Thanks!

How did you solve it in O(N) without proving that there are at most two solutions?

I understand now! Thanks Benq!