4
$\begingroup$

Sorry for the lack of clarity in the question description.

I have an array composed of length $N$ composed of $K$ linear subarrays. We define a linear subarray as a contiguous subarray of the array $[l,r]$ where $A[i]-A[i-1] = C$, a constant, for all $l<i<=r$. (Note: $C$ may be different for different subarrays; the elements of the array are integers.) Please note that the linear subarrays are not disjoint (there is one element intersection between any pair of adjacent linear subarrays). For example, [1,3,5,4,3,2] has two linear subarrays: [1,3,5] and [5,4,3,2]. [1,3,5,1,2,3] would have three: [1,3,5], [5,1], [1,2,3].

I wish to find multiple queries for the maximal value that is less than a queried value $V$, in $o(K)$ and $o(N)$ time per query, with $o(K^2)$ and $o(N)$ preprocessing. (Assume that the array has already been stored in terms of the K linear subarrays, perhaps in terms of the constant C and length of each subarray, with the subarrays ordered. Therefore, you are given the array with the starting and ending points of all the linear subarrays, as well as the linear constant C, as described before. So, one does not need to derive the linear subarrays in the first place.) Otherwise, a proof (formal or not) that it is not possible to do so would be appreciated.

Of course, a balanced binary search tree (BBST) or simply sorting achieves the purpose, but it requires $O(NlogN)$ preprocessing, which is too much. Checking the largest valid value within each subarray takes $O(K)$ per query, which is again too much. Would it be possible for something to combine both of these, perhaps?

Randomised algorithms are okay as long as they always achieve the correct answer and work fast enough in the average case, though deterministic algorithms are preferred.

Thanks for any and all responses. I was wondering if there was any research in the question, maybe? It does not seem like too obscure a topic, but unfortunately my searching has not been competent enough.

EDIT: A method that seems useful.

Here was my line of thinking after I asked the question; I wonder if this would help somehow. It uses the idea of modulo as well. Initialise V=0, and allow each linear subarray to be stored as L,R; where L is the minimal value of the subarray and R is the maximal value. When we are given a query for V, we somehow disinclude elements where L>V and R<V (perhaps by using multiple dimensions?) A supplementary data structure stores the minimal theoretical difference of the element in the array, which is something like L - V mod c[i]. So essentially, we now need to be able to run a range add on this data structure, but if the value of any element becomes <0 or >=c[i] it needs to be reset (eg. if an element becomes equal to -1 with c[i]=5 it would be reset to 4; if an element becoming equal to 6 with the same c[i] would be reset to 1); and also run range minimum queries.

If such a data structure can be made, the problem is solved. The trouble is the modulo, as range add and range minimum query can be easily done with a segment tree and lazy propagation; as well as the disinclusion of certain elements.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Basically, it seems you have $K$ arithmetic sequences, of the form $a_i,a_i+c_i,a_i+2c_i,a_i+3c_i,\dots,a_i+u_ic_i$, and given $V$ you want to find the larget element of any a.s. that's less than $V$. For a given a.s., if $u_i$ is sufficiently large, this value is $a_i + \lfloor (V-a_i)/c_i \rfloor c_i$, and its distance from $V$ is $a_i - V \bmod c_i$, so essentially our goal is: given the $a_i,c_i,u_i$ to find the $i$ that minimizes $a_i - V \bmod c_i$. I don't see how to do that in $o(K)$ time, even with preprocessing. $\endgroup$
    – D.W. ♦
    Commented Jan 3, 2020 at 17:24
  • $\begingroup$ @D.W. Sorry for the confusion. What I mean is that I am fine with O(logN) or really any logarithm for each query, but O(K) is too slow. The mention of O(K^2/logK) for K queries is essentially the goal, and something like O(logN) would satisfy this as long as N is not absurdly large, which it is not in my case. And the difference is not that important, but I was hoping for something that runs somewhat substantially faster than O(K^2/logK). The elements are integers. I have now added that; I forgot to add that the previous time. $\endgroup$
    – shgr1092
    Commented Jan 3, 2020 at 17:54
  • $\begingroup$ @D.W. I don't really want to "shave off" a O(logK) factor, but I wanted something that runs substantially faster. That comment was because something like O(Klog^4K) could be essentially as slow as O(K^2), so I wanted something that is practically faster. $\endgroup$
    – shgr1092
    Commented Jan 3, 2020 at 18:02
  • $\begingroup$ @D.W. It occurs to me that the way I initially phrased the question was misleading, causing the question to be harder than it otherwise would be. Would it be possible for you to read the revised question? $\endgroup$
    – shgr1092
    Commented Jan 7, 2020 at 2:56
  • $\begingroup$ You have "hidden" some of what you are looking for in "the bounty text" instead of editing it into your question: A solution in $o(K)$ per query, with $o(K^2)$ preprocessing, or a proof that such a solution cannot exist (given $k<N$, $o(N)$ looks redundant). $\endgroup$
    – greybeard
    Commented Jan 11, 2020 at 5:57

1 Answer 1

Reset to default
3
+50
$\begingroup$

It is not possible to guarantee to find the maximal value that is less than a queried value $V$ in $o(K)$ time with preprocessing in $o(N)$ time.

This can be seen easily in the following extreme case. Let $A$ be any array of $N$ integers, which is composed of the following $K=N-1$ linear subarrays.

  • the subarray $A[0], A[1]$ with $C=A[1]-A[0]$.
  • the subarray $A[1], A[2]$ with $C=A[2]-A[1]$.
  • $\cdots$
  • the subarray $A[N-2], A[N-1]$ with $C=A[N-1]-A[N-2]$.

With $o(N)$ time preprocessing and $o(K)=o(N)$ time processing, an algorithm will not be able to even read some number in $A$ when $N$ is large enough. (In fact, most of the numbers in $A$.) So, for some queried value $q$, the algorithm will fail to recognize that $q+1$ appears in $A$.

(The explanation above could be made more rigorous, for example, using the formal method of adversary and a well-defined model of computation.)

It looks like the more interesting question to ask should be whether there is an algorithm with $o(N\log N)$ preprocessing and $o(K)$ per query. Or whether there is algorithm with $o(N)$ preprocessing and $o(K)$ per query given $K=o(N)$. That sounds like another question, anyway.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Missed the rev. 16 edit from not bounded above by N to dominated by N. $\endgroup$
    – greybeard
    Commented Jan 12, 2020 at 16:37
  • $\begingroup$ @greybeard Your comment could not be understood. What is missed by whom, exactly? $\endgroup$
    – John L.
    Commented Jan 12, 2020 at 17:55
  • $\begingroup$ I missed shgr1092's 15th edit. $\endgroup$
    – greybeard
    Commented Jan 12, 2020 at 17:58
  • 1
    $\begingroup$ @JohnL. Ah... What I was meant to be asking for was "Or whether there is algorithm with 𝑜(𝑁) preprocessing and 𝑜(𝐾) per query given 𝐾=𝑜(𝑁)." (I think the nuance of this was lost in my last edit.) Still, I'll give the bounty, since you answered the question the way it is currently asked. Apologies to everyone for the lack of clarity all-around, I'll try to do better in the future. $\endgroup$
    – shgr1092
    Commented Jan 13, 2020 at 5:03

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.