http://clesolea.com/1EY8
Tags: observations, invariant theory (see more about this here)
I struggled with this but got it in the last couple minutes of the contest. First, I wrote down the requirements, which were that the sum had to be even and the greatest element is less than or equal to the rest of the sum (think about if it was n=2, 2 4). I couldn't go any further with this though so I tried some incorrect greedy things and gave up and did C. My mistake was looking too far into it (for a B problem) and doing some cases I created incorrectly (I thought n=4, 2 2 2 4 was impossible). I realized the answer when I correctly did the case I just mentioned (the n=4 one).
The answer is just to make sure the sum is divisible by 2 and the greatest element is less or equal to the rest of the sum of the array. You can just assume that this always works after doing some samples, or you can try proving it by performing some operations and seeing if the requirement of the greatest element not being greater than the sum of the rest still holds (idea from here).
No comments:
Post a Comment