Solution code

Greedy

There was a simple greedy approach to this problem. Go through all balls in ascending order. For each ball, try to move it up as much as possible by repeatedly swapping it with another ball with a larger index. At each step, we have up to two possible swaps. Among the two choices, it is better to pick the ball with the highest value, so that it moves down the pyramid.

Beam search

The greedy solution can be improved by beam search.

I used the following evaluation value:

\[\sum_{i=1}^{495} \sqrt{i} \cdot \text{(row of ball i)} + 1000.0 * \text{(number of placed balls)}\]

My implementation of beam search is described here: euler-tour-beam-search. It uses an Euler tour of the search tree to avoid copying states. On this problem, it is probably between 2x and 5x faster than state-copying implementations.

Using this implementation technique, I could set the beam width to 6000. (But it was a bit better to run three independent searches with a beam width of 2000).