Do you have the standings of Day 2?

+

DP on substrings

Let's look at the difference between adjacent elements.

Assume that $$$b_i = a_{i+1}-a_i$$$, and now our task will be to remove equal neighbors, and put the doubled value instead.

Now let's do some dynamic programming here, $$$dp_{l, r}$$$ — which determines whether we can remove a subarray $$$b_{l \dots r}$$$.

The observation is that, for the fixed $$$l$$$, there at most $$$log_2(n)$$$ such $$$r$$$. Hence, for each $$$l$$$, we can just maintain a set that stores those rightborders. Try to come up with transitions by yourself.

After calculating these $$$dp$$$ values, the problem can be solved with another dynamic programming. $$$d_i$$$ — minimal length of after performing operations on prefix $$$b_{1 \dots i}$$$. Answer to the problem will be $$$d_n$$$.

Do you have the other tasks too?