← All solutions

Shortest judge solution: 2926 bytes. Shortest team solution (during contest): 2843 bytes.

This was a pretty hard problem, not because its algorithmically deep but just because it’s a bit messy. The main idea is to try all possible assignments of variables to banks, with the following optimizations.

1. We can always assume that bank 0 is full, because referencing variables allocated to bank 0 is always free.
2. Once bank-0 is allocated, consider the sub-program obtained by removing all the references to bank-0 variables. For each pair of remaining variables i and j, let C_ij be the number of times a reference to variable i is followed by a reference to variable j when executing the program (which can be counted pretty easily). Then given a bank assignment to the remaining variables, the total number of BSR instructions that need to be executed is simply the sum over C_ij for all i, j that are allocated to different banks. This gives a way to very quickly evaluate the quality of a bank assignment, without going through the entire program.
3. Banks 1 and up are symmetric, so one should remove this symmetry by e.g. only generating assignments where the smallest variable in bank 1 is smaller than the smallest one in bank 2 which is smaller than the smallest one in bank 3, and so on.
4. If some bank only contains r variables, than all other banks should contain at least s − r + 1 variables, because otherwise two banks could be merged which always decreases the cost of the bank allocation.

With optimizations 1, 3, and 4 and at most 13 variables, it turns out that there are in the worst case around 3 million bank assignments to try. With optimization 2, each such bank assignment can be quickly evaluated.