Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: yzhao123
Subtask 1
This subtask was meant for contestants to try and solve 
~1 \le N \le 8~ by hand.
Subtask 2
There are numerous ways to solve this problem. The intended solution will be described here. Each index 
~i~ has ~i~ subarrays ending there, and we will make those subarrays all nonnegative or all negative. It is always possible to partition the integers 
~1,2,...,n~ into two sets with a difference in sum of at most 
~1~. Let ~i~ represent ~i~ nonnegative sum subarrays ending at index ~i~, and 
~-i~ represent ~i~ negative sum subarrays ending at index ~i~. For even 
~N~, we use the pattern 
~1, -2, -3, 4~ with signs repeating
~\mod4~ which has a difference of at most ~1~ at each even index. For odd ~N~, we use the pattern 
~1, 2, -3, -4~ with signs repeating~\mod4~ which has a difference of at most ~1~ at each odd index. The implementation to create this array is left as an exercise to a reader.
Comments