Subtask 1

Due to the small ~N~ of this subtask, it is possible to do a brutal complete search. We can try whether to insert a "separator" between each consecutive numbers. Among all those possible "separator" positions, we only consider those with more than or equal to ~A~ and less than or equal to ~B~ groups, and find the minimum OR-SUM. The complexity for this solution is ~\mathcal O(N 2^N)~.

The solutions for the next subtasks require an understanding of Dynamic Programming.

For simplicity, let ~Y = \max\{Y_i\}~.

Subtask 2

We would like to create a dynamic programming table with three parameters, ~curpos~, ~curOR~, and ~curpartition~.

~dp[curpos][curOR][curpartition]~ will be ~true~ if and only if there exists a partition of the first ~curpos~ elements with ~curpartition~ groups and the OR-sum is ~curOR~. It can be computed by this recurrence:

$$\displaystyle dp[curpos][curOR][curpartition] = \bigvee_{i=curpos}^N dp[i+1][curOR \mid sum[curpos, i]][curpartition+1]$$

where ~sum[x, y]~ is the sum of the ages of sculpture ~x~ to ~y~ inclusive.

After computing the dp table, we are finding the minimum number ~X~ such that there exists ~P~, ~A \le P \le B~ where ~dp[N][X][P]~ is true. We can loop for all possible values for ~X~. ~curOR~ can be as worse as ~\mathcal O(YN)~. Therefore, the complexity for this solution is ~\mathcal O(NY NNN + NY N) = \mathcal O(N^4 Y_i)~.

Subtask 3

~A = 1~ means we can try to use as few groups as possible for any fixed ~curOR~ and ~curpos~. We make a minor modification to our solution from subtask 2. We remove the third parameter, left with only ~curpos~ and ~curOR~. For this subtask, ~dp[curpos][curOR]~ will return the fewest number of groups to make the partition of the first ~curpos~ elements with the OR-sum is ~curOR~. It can be computed by:

$$\displaystyle dp[curpos][curOR] = 1+\min_{i=curpos}^N dp[i+1][curOR \mid sum[curpos, i]]$$

After computing the dp table, we are finding the minimum number ~X~ such that ~dp[N][X] \le B~. The complexity for this solution is ~\mathcal O(NY NN+NY) = \mathcal O(N^3 Y)~.

Subtask 4

We are looking for the minimum OR-SUM. We will construct the answer bit-by-bit, from the most significant bit.

It is always optimal if greedily fix the most significant bit of the OR-SUM to be zero, regardless of the other bits. If it is possible, then the most significant bit should be zero; if it is not, it will be one. Then, we consider the next significant bit, and do the same, keeping the current "bit prefix" not changed.

In other words, we iterate ~k~ (current bit position) from ~\log(YN)~ to ~0~. For each ~k~, we try whether it is possible to set the ~k^\text{th}~ bit of the OR-SUM to be zero (ignoring the rest of least significant bits). The check can use the dynamic programming method explained in subtask 2, but we drop the ~curOR~ parameter. Each group sum now must not change the value of the current bit prefix. The complexity for this solution is ~\mathcal O(\log(YN) NNN) = \mathcal O(N^3 \log(YN))~.

Subtask 5

We can solve this subtask by combining the idea from subtask 4 and subtask 3. From subtask 3, we can drop the ~curpartition~ parameter by computing the minimum number of partition in the DP table instead. From subtask 4, we can drop the ~curOR~ parameter. By combining both ideas, we can have a DP table where the parameter is only ~curpos~. The complexity for this solution is ~\mathcal O(\log(YN) NN) = \mathcal O(N^2 \log(YN))~.