Editorial for An Animal Contest 2 P2 - Koala Party
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Given that each is unique, we realize that the answer is always , , or .
If , the answer is if the total number of cookies among all bowls is odd and if the total is even.
For all , the answer is if we can find three bowls , , and that form an arithmetic sequence, and otherwise.
Subtask 1
We loop possible values of , , and , and check if the elements form an arithmetic sequence.
Time Complexity:
Subtask 2
To optimize, we add all into a set and loop possible values of and , checking if is contained.
Time Complexity:
Comments
Don't know if O(N^2) is optimal solution. Also I don't think this issue has anything to do with greedy algorithm as suggested by the "problem type". Another O(N^2) solution is to sort the array. Then loop through [2, n - 1] to find the solution to the equation of a[j] + a[k] = 2 * a[i], j < i < k.
Kind of an explicit intuitive proof about why for n>=3, if an arithmetic sequence doesn't exist, the answer is 2. For the answer to be 2, there must be 2 bowls with the sum of their cookies being an even number. An even number can be reached either by even+even or odd+odd. In 3 or more bowls, intuitively, there must be at least one pair of bowls that have their cookies adding to an even number. For example, when n==3, possible unordered combinations are (odd, odd, odd), (odd, odd, even), (odd, even, even), and (even, even, even). In all of these combinations, there is at least 1 pair adding up to an even number (either odd+odd or even+even).
This also explains why we have to explicitly check for cases when n==2. Unlike >=3, for n==2, it isn't guaranteed that a pair in which the sum is even exists. (even, even) and (odd, odd) has satisfying pair but (odd, even) doesn't.