Last year when I was in Team Terharu :’), we did some Codeforces Gym contests for our training. One of the interesting problem is Problem E of the ACM ICPC Central Europe Region Contest 2014.
The problemset of that CERC 2014 can be accessed here.
Given a sequence of $N (1 \le N \le 1000)$ integers in the form of power of twos. The sum of the integers does not exceed $2^{13}$. Each time we can put a number to the left or right of the group of integers we currently have (initially empty). Our task is to merge the given integers (in the same order as the input) to be only an integer. While there are two adjacent numbers having same values, they will merge into an integer which value is the twice of their values. We should check whether there is a configuration leaving only one block.
Because at first we thought that this problem was very hard, we said the title as “Can’t Start Playing” :’(
One of the idea to solve this problem is by using dynamic programming + bitmask.
Initially, we should check whether the sum of all of the numbers is in the form of power of two. If not, then we can be sure that there is no way to make them become a power of two.
Then we begin the dynamic programming routine. The state is in the form (index, mask), where index is the current index of number we are processing, and mask is the bitmask of the group of numbers we have from middle to left (or from middle to right is also OK). In further explanation I will use the “from middle to left” version.
At a time, the configuration of the group of numbers will be strictly increasing sequence followed by strictly decreasing sequence. Because we only need to store a configuration of one side and there will not be any duplicate adjacent value, we can store the configuration on the bitmask :’)
Then how do we know the configuration of the other side (i.e. the right side)? We make a prefix sum before our DP routine, then if we are processing DP (i, right), to know the left part, we only need to make a binary representation of the sum[i] - mask. This kind of technique is also called as state reduction technique. It is very useful because we can reduce the memory usage for the DP.
The code of the Accepted solution can be accessed here «Source Code» –broken link, will be fixed later.