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

Problems and Contests
#1

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
#2

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
#3

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!

#4

@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!

#5

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

#6

I understand now! Thanks Benq!

#7

Hi! Really sorry to bother, but I couldn’t for the life of me figure out how to implement the solution when there is an odd number of bs in O(n) even after viewing BenQ’s hint, which I don’t fully comprehend as well. Do you mind explaining your solution or your way of thinking?

#8

lets call the given array b and the answer array a
adjacent differences in b corresponds to the differences of values 2 away from each other
aka b[i+1] - b[i] = a[i+2]-a[i]
therefore we can split a into even and odd terms and represent each element in terms of the first and second terms

array a has to include 1 so we can assume the minimum even term is 1 and construct the array that way (we would know the first term and using b[0], obtain the second term and then construct). we can do the same for the odd terms. then we just check which array is valid and print the lexicographically smallest of the two

my solution code ^

#9

@MatthewC3297 Time complexity of your solution is NlogN, because you used sort function.

#10

yes because sorting a 2 element vector will turn the time complexity into nlogn (this is sarcasm, use ur brain)

#11

ok,that’s clear

#13

@MatthewC3297 Your solution isn’t true, I checked it then found bug, for example, I enter the input as
6
8 7 8 10 5
Your output: 7 1 6 2 8 -3
Correct output: 3 5 2 6 4 1

#14

@MatthewC3297 I found out problem. The problem in code is at 44th and 53rd lines. Please change the condition i < n-1 to i < n or i <= n-1 in loop, because your pref vector consist of n elements. I hope that it will fix your problem. Thanks in advance.