I am solving problems on Codeforces and have made it a point to solve at least one problem that requires me to learn something or practice something I'm not yet comfortable at everyday. For such problem(s), I will write down my analysis and post it in a blog. I will try to write as explicitly as possible and pretend I am teaching this to someone quite new to things related to the problem like myself. Hope it helps someone out there. There will definitely be some inaccuracies that I was not aware of, please let me know and I will try to correct them. Thank you for reading.

981D — Bookshelves

Problem statement summary: Given an array $$$a$$$ consisting of $$$n$$$ non-negative integers ($$$1 <= n <= 50$$$), find a way to split $$$a$$$ into $$$k$$$ contiguous subarrays such that when we take the sum of each subarray and then take the bitwise AND over those sums, we get the maximal value possible. Output that maximal value (the exact way to split is not required here).

There is already one tutorial for this problem here: https://codeforces.com/blog/entry/59713. I have read it to understand how to solve this myself.

Idea: Upon reading a problem that involves finding a solution that returns the optimal value, the first thing that comes to mind is to try every possible splittings and take the best one. There are $$$C(n - 1, k - 1)$$$ ways we need to check. With $$$1 <= k <= n <= 50$$$ this will exceed the time limit. So the next idea would be finding a DP approach.

Before considering a DP approach, we must realize that there is no optimal substructure for the bitwise AND operation. Unlike ordinary sums or OR sums, AND sums can never increase as we take bitwise AND of more values. So solving the problem for a section of the array will not provide any insight into solving a larger section. However, having realized that AND sums can never increase as we add more values, we can start to see a way to break this problem down in order to apply DP.

Let $$$res$$$ be the optimal AND sum that we are looking for. Also let's pretend we have computed all possible splittings and the AND sums of such splittings, then $$$res$$$ must be the largest among such values. Being the largest must at least equivalate to having the largest index of all highest-order 1-bits. Among all values that also have such bit, $$$res$$$ would also have the largest index of all next-highest-order 1-bits and so on. From here we have an idea: What if we can loop from the highest-order index and check whether we can turn the bit at this index of our answer (initially set to zero) to 1 by splitting the array into k segments? If yes then definitely turn it on. Then check for the next index.

Now we have a new task: Given a bitmask, check whether there exists a k-splitting that would generate a value that contains this mask as a prefix. Initially we have cur_mask set to zero. Then, looping i from 49 to 0, at each loop we make new_mask out of cur_mask with bit i flipped to 1 and check whether a value with prefix new_mask can be generated from a k-splitting. If yes then new_mask must be the prefix of the optimal value, so we replace the cur_mask with new_mask. Repeat until we have checked for all indices i and the answer is the final value of cur_mask.

The rest of the solution relies on implementation and can be read from the tutorial link above.