Editorial for DMOPC '22 Contest 5 P2 - Absolutely Even
Submitting an official solution before solving the problem yourself is a bannable offence.
This subtask was meant for contestants to try and solve by hand.
There are numerous ways to solve this problem. The intended solution will be described here. Each index has subarrays ending there, and we will make those subarrays all nonnegative or all negative. It is always possible to partition the integers into two sets with a difference in sum of at most . Let represent nonnegative sum subarrays ending at index , and represent negative sum subarrays ending at index . For even , we use the pattern with signs repeating which has a difference of at most at each even index. For odd , we use the pattern with signs repeating which has a difference of at most at each odd index. The implementation to create this array is left as an exercise to a reader.