2
$\begingroup$

I was thinking on the following problem:
Given an array A. The value of an interval from i to the index j is defined as follows:

Take the maximum value from that interval, and add it to the OR value of all the numbers from this interval(which equals a[i] OR a[i+1] OR ... OR a[j]).

Now lets suppose, our arrays length is N. Now we need to determine the value of the interval with the highest value, which has a length k where k = 1,2,3...N(so we need to answer for every possible k, and therefore we need approximately O(log N) or O(log^2 N) time to answer for a given k value). The dataset is large enough(N<=100000), so I can't use an algorithm with complexity O(N^2), with which I was able to come up.

My only idea was an N x log N big two dimension array, where I can store datas, with which I can determine OR in O(log N) time, but I'm out of ideas. Please, help me.

Thank you in advance!

$\endgroup$
  • $\begingroup$ Can we assume the values are non-negative? $\endgroup$ – dtldarek May 28 '15 at 20:31
  • $\begingroup$ Yes, the values are non-negative. $\endgroup$ – porcupine May 28 '15 at 20:32
0
$\begingroup$

Denote an interval with $(i, j)$, meaning it is the interval from $a[i]$ to $a[j]$. Denote by $OR(i, j)$ the value $a[i]$ or $a[i+1] \ldots a[j]$. For each $k$, we want to find $i$ that maximizes (or minimize) $OR(i, i+k-1)$.

For each $i$, consider the set $\{OR(i, j) | j \le i\}$ (that is, all the possible different values of intervals starting at position $i$). Let the maximum value of any of the elements be $M$. Then, the set will contain at most $O(\log M)$ distinct values (to see this, suppose $OR(i, j) \not = OR(i, j+1)$. Then, one of the bits from $OR(i, j)$ that was zero must be one in $OR(i, j+1)$. But there are at most $\log M$ bits, so this can only happen $O(\log M)$ times.

Thus, for each $i$, calculate all the possible distinct values of $OR(i, j)$ (can be done quickly in $O(\log n)$ for each $i$). Computing the maximum/minimum for each $k$ is now trivial.

EDIT: Expanded Answer. Here's the algorithm

1) For each $0 \le i \le \log M$, create a data structure $D_i$ from which you can compute the following: given an index $j$, find the first index $f \le j$ such that the $i$-th bit of the number at index $f$ is 1.

2) For each $0 \le i \le N$ and for all possible indices $j$, query $D_j$ at position $i$ to find the first index $f_j$ whose $j$-th bit is 1 (using $D_j$). Note that $f_j$ may be equal $i$ for some $j$.

3) Sort all the $f_j$ values, and make them unique. For every prefix of this sequence, compute their OR = $p$. Let $a_k$ be our potential answer for a given $k$. Suppose $f_z$ is the largest of index of all the $f_j$ values that makes up $p$. Add $p$ to the potential answers for $a_{f_j - f_0}$.

4) For each $k$, the maximum value is either one of the values of $a_k$, or is equal to the maximum value for less $k$.

This is $O(N \log^2 N)$. If you rather have pseudocode

for i in range(N):
  zs = set()
  for j in range(log M):
    zs.add(first index k >= i whose j-th bit is one).
  orvalue = 0
  for v in sorted(zs):
    orvalue |= number[v]
    maybe_answer[v - i].push(orvalue)

best = 0
for k in range(N+1):
  best = max(best, max(maybe_answer[k]))
  print 'answer for k=' + k + ' is ' + best
$\endgroup$
  • $\begingroup$ Where you talk about the set of OR(i,j), you mean i≤j right? $\endgroup$ – porcupine May 29 '15 at 15:32
  • $\begingroup$ It seems like the question was to maximize the sum max(a(j),a(j+1),...a(j+k)) + OR(a(j),a(j+1),...,a(j+k)) over j for each choice of k. This seems to only address the OR part. $\endgroup$ – user2566092 May 29 '15 at 21:13
  • $\begingroup$ @user2566092 yes, it's true... do you have any suggestions, how to solve this problem, or extend this approach? $\endgroup$ – porcupine May 30 '15 at 9:32
  • $\begingroup$ @porcupine No unfortunately. I don't even fully understand Irvan's answer given here for just "OR" and how its running time can be made faster than O(N^2). Currently I'm coming up with my own approach for that which increases memory use by a logarithmic factor (which I think Irvan's solution does too). I'll post that if I get it, but I still have no idea how to include the addition of the max over the interval. $\endgroup$ – user2566092 May 30 '15 at 18:57
  • $\begingroup$ @user2566092 What my answer basically suggest is to find all $N \log N$ possible different values of $OR(i, j)$. Deducing the maximum for each $k$ can be done in amortized $N \log N$ time. I'll expand on the answer later. $\endgroup$ – Irvan Jun 1 '15 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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