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
is optimal solution. Also I don't think this issue has anything to do with greedy algorithm as suggested by the "problem type".
Another
solution is to sort the array. Then loop through
to find the solution to the equation of
,
.
Kind of an explicit intuitive proof about why for
, 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
, 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
. Unlike
, for
, 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.