# Internet Problem Solving Contest

## Solution to Problem B – Bounding box

### Easy subproblem

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:

• Create a 3D grid of small cubes inside the box, starting at (0, 0, 0). Store the coordinates of all small cubes inside a set data structure.
• Create a 3D grid of big cubes inside the box, starting at (0, 0, 0). Pick as many cubes as needed and place all copies of the big ball inside those cubes. Remove all small cubes inside the used big cubes from the set data structure.
• Place all small balls into the remaining small cubes in the set data structure.

### Hard subproblem

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:

• To avoid the quite strict overlap check in the grader, it is best to enlarge the balls by a few percent.
• Previous bullet applies applies also to solutions using a physics engine. They tend to keep some collision overlaps.
• The initial positions of balls affect the result, sometims even by over 10%. If the current stable state does not fit into the box, we just need to reeated the experiment with new randomized positions of balls. Only a small number of such trials should suffice.

### But what if I hate physics engines

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.

1. distribute balls randomly in the box
2. repeat until solution is ok or maximum steps reached
• there will be no velocity of the balls. Everything is instant-time teleport ;-)
• “solve” collisions with the box. If a ball is too close to the box, just move it to the correct distance + random epsilon.
• “solve” collisions of balls. If two balls are too close to each other, change their positions such that their midpoint is fixed but their distance is now r1 + r2 + random epsilon.
• Note that random epsilons are quite important – as in a naive implementation the collision check is likely to be in the deterministic order, small random variations allow the algorithm to escape some nasty cycling which could happen if the result after processing of collisions is the same as before.
1. if we did not find a valid solution, repeat with step 1.

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.