3
$\begingroup$

I participated in an algorithms contest recently, and couldn't find an answer to this problem. The contest is over now, and am looking to see if someone might know how to solve this.

Question: "You are given an array A with n elements and a positive integer K.

As long as the array A has at least K elements, you have to select some K consecutive elements, remove them, and in their place insert their bitwise OR. Once the array's length is less than K, your final score is calculated as the sum of the elements. Your goal is to minimise this sum.

2 ≤ K ≤ N ≤ 400,000

0 ≤ ai ≤ 1,000,000,000" - https://nzprogcontest.org.nz/ProblemSets/NZPC_2024_Contest.pdf (Problem P from the link)

A brute force or exhaustive search/breadth first search on all possible choices is too slow. As N is very large, N^2 is not allowed.

Expected time complexity: The lecturer has informed me N log N is the expected solution.

Example: If A = [1, 4, 5, 3, 5, 3], and K = 3.

After repeating the OR operation multiple times, the final sum is 8 (which is the smallest sum possible)

enter image description here

$\endgroup$

1 Answer 1

2
$\begingroup$

It can be solved in $O(NKB\lg N)$ time with a dynamic programming algorithm, where $B$ is the number of bits in each array element. (For example, in your contest, $B \le 30$.)

Problem statement

We can reformulate the problem as follows:

Partition the array $A[1..N]$ into $K$ consecutive subarrays, such that the length of each subarray is a multiple of $K-1$ plus one; we will compute the bitwise OR of all elements in each subarray, then sum those $K$ values, and the goal is to minimize the sum.

Naive dynamic programming algorithm

Let $S[i,j]$ denote the minimum possible sum if you partition $A[1..i]$ into $j$ consecutive subarrays. Then you can compute a recurrence relation for $S[\cdot,\cdot]$, i.e.,

$$S[i,j] = \min \{S[i',j-1] + (A[i'+1]\oplus \cdots \oplus A[i]) \mid i' < i, i'-i \equiv 1 \pmod{K-1}\}.$$

Filling in this array in the naive way takes $O(N^2 \lg N)$ time. In particular, we can compute $A[i'+1]\oplus \cdots \oplus A[i]$ in $O(\lg N)$ time by precomputing a balanced binary tree of the $N$ elements of the array $A[1..N]$, with each leaf corresponding to an array element and each node of the tree is augmented with the bitwise OR of all array elements corresponding to the leaves under that node. Then computing $S[i,j]$ involves computing the min over $N/(K-1)=O(N/K)$ values, and each value can be computed in $\lg N$ time, so it takes $O((N/K) \lg N)$ time to compute each $S[i,j]$, and there are $NK$ entries in $S$, so the total running time of this naive algorithm is $O(N^2 \lg N)$.

Faster algorithm

We can optimize the above algorithm, by introducing a clever way to compute $S[i,j]$ in $O(B\lg N)$ time. Then the total running time will be $O(NKB\lg N)$, as claimed above.

To help us derive this optimization, let's look at the following sequence of values:

$$A[i], A[i-1] \oplus A[i], A[i-2] \oplus A[i-1] \oplus A[i], \dots, A[1] \oplus \cdots \oplus A[i].$$

Even though the sequence might be very long (up to $N$ entries), I claim it only contains at most $B$ distinct values -- so there are a lot of repeats. Also, it is a monotonically increasing sequence. In particular, each element of this sequence is either the same as the preceding value; or the same as the preceding value but with some additional bit positions set. Once a bit position becomes set, it stays set for all subsequent values in this sequence. So the sequence has the form

$$v_1,\dots,v_1,v_2,\dots,v_2,\dots,v_m,\dots,v_m$$

for some $m\le B$. We will find the indices of each entry in this sequence that is different (larger than) its preceding entry. This can be done with binary search. We do $m \le B$ binary searches. Each binary search requires at most $\lg N$ iterations, and computing each value in the sequence takes $O(\lg N)$ time (using the binary tree trick above), so the total running time to find all of these indices is $O(B (\lg N)^2)$. By making the binary search traverse the binary tree, you can reduce the running time to $O(B \lg N)$.

Now, we are considering all values of $S[i',j-1] + (A[i'+1]\oplus \cdots \oplus A[i])$ for all $i'$. It is easy to see that $S[i',j-1]$ is an increasing function of $i'$. We have shown above that $(A[i'+1]\oplus \cdots \oplus A[i])$ is a decreasing function of $i'$ with at most $B$ different places where it changes value. It follows that the minimum possible value of $S[i',j-1] + (A[i'+1]\oplus \cdots \oplus A[i])$ must occur at one of these changepoints (since $S[i',j-1]$ is an increasing function of $i'$, we want to consider the smallest $i'$ out of an entire stretch where $(A[i'+1]\oplus \cdots \oplus A[i])$ has the same value). We indicates above that we can compute the changepoints in $O(B \lg N)$ time, and we also obtain the value of $A[i'+1]\oplus \cdots \oplus A[i]$ at each changepoint for free. Therefore, it suffices to evaluate $S[i',j-1] + (A[i'+1]\oplus \cdots \oplus A[i])$ at each of these $\le B$ changepoints.

All in all, for a given value of $i,j$, it takes $O(B \lg N)$ time to find all the changepoints, compute the values at the changepoints, and compute the minimum. So for each $i,j$ we can compute $S[i,j]$ in $O(B \lg N)$ time. There are $O(NK)$ entries $S[i,j]$ to compute. Therefore, the total running time is $O(NKB \lg N)$, as claimed above.

$\endgroup$
9
  • $\begingroup$ Wow, thanks DW, I think that's entirely correct. I was looking it up as well, I believe a sparse table can also be used for O(1) range queries but, I've only coded up the naive DP solution at the moment. I also noticed that, with each OR operation, we're only removing K - 1 elements at a time, so we know the exact amount of elements left at the end. The amount of elements left in the final array is (N % (K - 1)) + 1, so I believe a top-down dp, only needs to know the result for (N % (K - 1)) + 1 groupings of numbers. $\endgroup$ Commented Aug 21 at 12:13
  • $\begingroup$ I believe, that was the main thing I was having issue with understanding, if we're only left with 5 numbers in the final array, how do we know we have 5 groupings. But it makes sense to me now, 3 numbers may have been part of grouped OR operations, and 2 of the final numbers may have never been OR'ed against any other. But those 2 individual numbers which remained untouched were just part of their own single element group. $\endgroup$ Commented Aug 21 at 12:18
  • 2
    $\begingroup$ Can you expand more on why the reformulation is equivalent to the original problem? What does each partition in the reformulation represent in the original problem? Say in the array 1,1,2,2,3,3 with K=3, what does the partition [1,1], [2,2], [3,3] represent? $\endgroup$
    – justhalf
    Commented Aug 21 at 13:16
  • $\begingroup$ @justhalf I believe that may have been a minor mistake in DW's overall reformulation. As [1, 1] would not be a valid partition, and for the example you've given, it's not possible to split those 6 numbers into 3 groups. (it need's at least K=3 numbers in it). Just for the example you've given, after calculating all the OR's, the final array/answer should only have 2 elements in it. Which actually means there are only 2 consecutive subarrays. (And therefore, in a 2D DP, the answer should be in DP[5][2], for all 5 elements and 2 bitwise OR groupings/subarrays). $\endgroup$ Commented Aug 21 at 13:33
  • 2
    $\begingroup$ So it should be partitions into a number of subarrays the same as the number of elements in the final array, each representing the final elements? That works. There'll be 1 + (N-1 mod K-1) subarrays, I suppose, right. $\endgroup$
    – justhalf
    Commented Aug 21 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.