January 2020 USACO Bronze Problem 2

Problems and Contests
#1

Hi,

I need help with this problem: http://usaco.org/index.php?page=viewproblem2&cpid=988.

Thanks.

:grinning: :slight_smile:

#2

Hey Jesse, welcome to the USACO Forum!

What specifically do you need help with for this problem? Did you read through the editorial, and if so, was there a section that you didn’t understand?

#3

Thanks for the reply. I just want to know which approach would be best for the problem (greedy, brute force, or etc.).

#4

Ah. Try brute force, though I suppose it can be thought of as greedy as well.

Bigger Hint

Can you check if you can form a valid permutation with a_1 = x for some given value x?

#5

Also, I don’t really understand the problem statement. Does each element in the array b have to be less than each element in the array a?

#6

b_i = a_i + a_{i+1} for each 1 \le i < n, and the numbers a_1 \dots a_n need to form a permutation of the numbers 1 \dots n. For example, in the sample input, b_1 = 4 = a_1 + a_2 = 3 + 1.

So no – each element in the array b doesn’t have to be less than each element in the array a…

1 Like