Solution

It is possible to arrive at any points between the range from the highest to the lowest coordinate, because distributional operations from the middle and from the edge are equivalent from the final state and does not affect the result. At the same time, as no parrots will be at the same position, there must be apples more than the number of parrots.

Therefore, it is a greedy algorithm that is one of estimated approaches to solving this problem. The solution is a $\max$ of $k$, where $\sum_{i=0}^{k}i$ is the lower bound of the maximum difference of the elements, and $N$, representing the number of parrots. This can be accomplished in $O(N)$ runtime complexity and $O(1)$ auxiliary spacing.

Side story

I really like 2 Eggs and 100 Floors Problem, so I tried my best making a similar problem, but it ended up weighing too light on the analysis part, compared to the original. Which is why I made the maximum constraint of $N$ way less than it can be so that it's less likely to be instantly seen through that the greedy approach is valid, lol.

Advertisement

As one of newbie competitive programming enjoyers, I am looking for members and officers willing to participate in an RSO for competitive programming club at UARK!

I need at least 6 people to make it work...Please let me know if you are interested via Discord DM! (last upated on September 12th, 2025)

Sample code

Please report any mistakes or concerns to the following address

trueryobATproton.me