TILT - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CHALLENGE

EXPLANATION

This problem had the lowest number of successful submissions ever for a challenge problem, which I found quite surprising. I did not mean for the problem to be so difficult.

The author’s solution works as follows:

The main solver function takes 2 parameters. The first parameter is the number of moves to look ahead, and the second parameter is a value that will change how the heuristic is calculated. From any state, consider all possible sequences of moves of length equal to the “look ahead” parameter. Rank these sequences based on the change in score, the heuristic, and whether any balls fell into holes. Execute the first move of the best sequence (or if there’s a tie, choose randomly).

The heuristic is calculated as follows:

If there are no inverter balls left, add m for every remaining positive ball, and subtract m for every negative ball, where m is a parameter that varies from run to run. Otherwise, add m for every remaining positive ball and negative ball. Then, subtract cieling((remaining balls)/holes).

Since the algorithm may not always yield a solution, it is executed repeatedly with different parameters and random number seeds until a solution is found.

A better solution is to use a Beam Search. See ACRush’s winning solution for an implementation.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Will be updated soon.