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.

Author: samliu12

Given that each $a_i$ ~a_i~ is unique, we realize that the answer is always $1$ ~1~, $2$ ~2~, or $3$ ~3~.

If $N = 2$ ~N = 2~, the answer is $1$ ~1~ if the total number of cookies among all bowls is odd and $2$ ~2~ if the total is even.

For all $N \ge 3$ ~N \ge 3~, the answer is $3$ ~3~ if we can find three bowls $a_i$ ~a_i~, $a_j$ ~a_j~, and $a_k$ ~a_k~ that form an arithmetic sequence, and $2$ ~2~ otherwise.

Subtask 1

We loop possible values of $i$ ~i~, $j$ ~j~, and $k$ ~k~, and check if the elements form an arithmetic sequence.

Time Complexity: $\mathcal{O}(N^3)$ ~\mathcal{O}(N^3)~

Subtask 2

To optimize, we add all $a_i$ ~a_i~ into a set and loop possible values of $i$ ~i~ and $j$ ~j~, checking if $\frac{a_i + a_j}{2}$ ~\frac{a_i + a_j}{2}~ is contained.

Time Complexity: $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~

Comments

0

zenomyth commented on Oct. 12, 2023, 5:54 p.m. ← edit 2 →

Don't know if $\mathcal{O}(N^2)$ ~\mathcal{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 $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~ solution is to sort the array. Then loop through $[2, N - 1]$ ~[2, N - 1]~ to find the solution to the equation of $a[j] + a[k] = 2 * a[i]$ ~a[j] + a[k] = 2 * a[i]~, $j < i < k$ ~j < i < k~.

8

suguruchhaya commented on May 13, 2021, 9:40 p.m. ← edited →

Kind of an explicit intuitive proof about why for $N \ge 3$ ~N \ge 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$ ~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$ ~N = 2~. Unlike $\ge 3$ ~\ge 3~, for $N = 2$ ~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.