Help Understanding Moorio Kart (Feb 2019 Plat)

#1

I’m currently working on Moorio Kart. Looking at the official solution, I understand everything except where it says

Such an algorithm would run in O(YS) where S is equal to the sum of the number of distinct path lengths in each tree (when we group together lengths ≥Y ). S is maximized to be Nsqrt(Y) when we have trees of size sqrt(Y).

Why is the sum of the number of distinct paths minimized when trees are of size sqrt(Y)?

#2

Total number of distinct paths is roughly \sum \min(c_i^2, Y) where \sum c_i=N. And

\sum \min(c_i^2, Y)\le (\max_i \frac{\min(c_i^2, Y)}{c_i})\cdot \sum c_i.

The ratio \max_i \frac{\min(c_i^2, Y)}{c_i} is maximized with c_i=\sqrt Y.

1 Like
#3

Gotcha, thanks for the clarification!