A ball of diameter 1 meter has volume π/6 m3, which is about 0.5236 m3. A cube with a 1-meter long side has volume 1 m3, less than twice more than the ball. We notice that in the easy inputs there is plenty of room inside the box, sometimes three times as much as the total volume of the balls. What if we could use treat every ball as smallest cube surrounding it and pack the cubes instead?
We also notice that there are always 2 balls with radii in ratios of 2 : 1 and 3 : 1, so we can exchange a group of 2 × 2 × 2 small cubes or 3 × 3 × 3 small cubes for a big cube. We check the dimensions of the box and realize a simple greedy approach will work: we pack all big cubes first and then fill the rest of the space with small ones.
One of the easiest way to implement this greedy approach is the following:
We can start by observing that the limits on the box size are much stricter than in the easy subproblem. Moreover, the ratios between the cubes sizes are smaller here. As such, we really need to perform a “ball-packing”. Fortunately, you already know how from the experience how to efficiently pack balls of roughly the same sizes – when was the last time you saw a bucket full of apples or strawberries? Could you do much better than the state to which the fruits arrived by themselves with the help of gravity? This suggest a “straightforward” approach – just throw all of the balls into the box and let them settle down. The real technicality is the implementation of this process. There is an easy and a hard way. An easy way is to download some physics engine, add balls, gravity and let it play. The hard way is to code a physics-like dynamics with a collision algorithm yourself. Fortunately, collisions of balls are detected very easily and the more challenging part of the task is to keep balls from “squishing” or just being accelerated to extreme speeds (https://what-if.xkcd.com/1/) which can happen if the simulation starts diverging.
Finally, here are few notes you might find useful:
Well, if you don’t want to use real physics engine and you are fed up with coding your own (though, you should be glad that you can safely ignore rotation and angular momentum of balls), there is an easier way – let’s call it no-physics engine. The idea is very simple.
This simple “no-physics” engine algorithm is enough to solve both easy and hard subtasks, avoids long simulation times (because everything is instantly teleported) and is quite elegant on its own.