Subtask 1
Due to the small
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
and less than or equal to
groups, and find the minimum OR-SUM. The complexity for this solution is
.
The solutions for the next subtasks require an understanding of Dynamic Programming.
For simplicity, let
.
Subtask 2
We would like to create a dynamic programming table with three parameters,
,
, and
.
will be
if and only if there exists a partition of the first
elements with
groups and the OR-sum is
. 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]](//static.dmoj.ca/mathoid/317131ed6e7c0f6902daaf6c32ad3dae212a4cde/svg)
where
is the sum of the ages of sculpture
to
inclusive.
After computing the dp table, we are finding the minimum number
such that there exists
,
where
is true. We can loop for all possible values for
.
can be as worse as
. Therefore, the complexity for this solution is
.
Subtask 3
means we can try to use as few groups as possible for any fixed
and
. We make a minor modification to our solution from subtask 2. We remove the third parameter, left with only
and
. For this subtask,
will return the fewest number of groups to make the partition of the first
elements with the OR-sum is
. It can be computed by:
![\displaystyle dp[curpos][curOR] = 1+\min_{i=curpos}^N dp[i+1][curOR \mid sum[curpos, i]]](//static.dmoj.ca/mathoid/d8598fb7f758425947c217f704a529b0b99d0a2d/svg)
After computing the dp table, we are finding the minimum number
such that
. The complexity for this solution is
.
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
(current bit position) from
to
. For each
, we try whether it is possible to set the
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
parameter. Each group sum now must not change the value of the current bit prefix. The complexity for this solution is
.
Subtask 5
We can solve this subtask by combining the idea from subtask 4 and subtask 3. From subtask 3, we can drop the
parameter by computing the minimum number of partition in the DP table instead. From subtask 4, we can drop the
parameter. By combining both ideas, we can have a DP table where the parameter is only
. The complexity for this solution is
.
Comments