Блог пользователя maomao90

Автор maomao90, история, 6 месяцев назад, По-английски

Introduction

I recently came across this problem which required an interesting trick to compute $$$a_i \otimes a_{i + 1} \otimes \ldots \otimes a_{i + w - 1}$$$ for all $$$1 \le i \le n - w + 1$$$ in $$$O(n)$$$ time and space. I found the trick very interesting, so I decided to write a short blog about it.

Problem

Given an array $$$a$$$ of size $$$n$$$ and an integer $$$w$$$. You are required to compute the value of $$$a_i \otimes a_{i + 1} \otimes \ldots \otimes a_{i + w - 1}$$$ for all $$$1 \le i \le n - w + 1$$$ in $$$O(n)$$$ time and space. $$$\otimes$$$ is a binary operation that is associative ($$$(x \otimes y) \otimes z = x \otimes (y \otimes x)$$$).

Solution

Split array $$$a$$$ into blocks of size $$$w$$$. In each block, we calculate applying the operator on each prefix and on each suffix. Then, any range of width $$$w$$$ can be formed by combining the suffix of one block with the prefix of another block.

The implementation is very easy as well. Let $$$p_i = a_{\left\lfloor\frac{i - 1}{w}\right\rfloor\cdot w + 1} \otimes \ldots \otimes a_i$$$ and $$$s_i = a_i \otimes \ldots \otimes a_{\left\lceil\frac{i}{w}\right\rceil\cdot w}$$$ for all $$$1 \le i \le n$$$. Then, $$$a_i \otimes a_{i + 1} \otimes \ldots \otimes a_{i + w - 1} = s_i \otimes p_{i + w - 1}$$$.

Extension

If we try to generalize this solution to work for queries of arbitrary width, we will realize that it becomes a disjoint sparse table. In disjoint sparse table, the queries can have arbitrary width, so we need to split into blocks of width $$$2^k$$$ for all $$$1 \le k \le \log_2 n$$$. For our application, since we only have queries of a fixed width, we only need one layer, and hence we can obtain a solution in linear time and space.

  • Проголосовать: нравится
  • +178
  • Проголосовать: не нравится

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Nice one! Now solve Triangle ignore the 1.5s timelimit, solve for 1s

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 6   Проголосовать: нравится +18 Проголосовать: не нравится

    Ok time to add something meaningful to the conversation.

    Although the trick detailed can be easily dismissed as unrolled queue-like undoing, the problem linked poses the same question but for 2D spaces. And so I would like to detail this scaling:

    The trick here, which can be applied in the 2D case, is to assign some reference points for which we will calculate some information which will be necessary and sufficient for completing an entire query. For triangles, given an interiour reference point, we can divide the triangle by drawing lines parallel to the axis through the given reference point, and as such we divide our query to require only information for a: trapeze in NW/SE quadrants, simple cornered triangle in NE, and rectangle in SW, all computable in linear time wrt the dimensions required for a query, which is of the order of $$$k^2$$$ (sufficiency?)

    Furthermore, to assure the necessity? of the construction, we can calculate only for gridpoints which have both their coordinates divisible by $$$\frac{k}{2}$$$; as such, any query has a reference point within it.

    The complexity is, therefore, clearly linear.

»
6 месяцев назад, # |
Rev. 3   Проголосовать: нравится -23 Проголосовать: не нравится

Uhhh, if your answers are denoted by $$$b_i$$$, then $$$b_{i+1} = b_i \otimes a_i \otimes a_{i+w}$$$, end of topic...

You should think about presenting a better showcase example. I reread the first paragraph a few times cause I was not expecting red to write a blog on a problem even a grey should be able to solve. It's not particularly educative that way and you will get "overcomplicated nonsense" rather than "clever technique" reactions even though your trick generalize to nontrivial problems

Btw this trick is in some sense a disguised divide and conquer (which would even be linear if we do not compute info about segments longer than w)

EDIT: Uhh, I was under a strong impression that you are considering XOR only, but it seems your intention was to denote an arbitrary commutative and associative binary operator with it. First thing — you do not need commutativity at all. Second thing — sparse table? I don't see any resemblance to a sparse table here. But to segment tree — surely. Or you can go with already mentioned D&C

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    dont you assume invertibility (and specifically, the operator being its own inverse)? i dont believe thats one of the axioms

    your example doesnt solve if the operator was bitwise and for instance

»
6 месяцев назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

You don't need comutativity. The way you describe the query, what $$$s_i$$$ and $$$p_i$$$ mean makes comutativity not be required.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do you use it to solve the original problem?

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +49 Проголосовать: не нравится

    Using bitset. :)

    Build a boolean table $$$B$$$ of size $$$n\times n$$$ where $$$B_{ik}=1$$$ if and only if $$$p_i < p_{i+k}$$$. Then the number of suitable indices $$$j$$$ for a fixed $$$i$$$ is the number of ones in the bitwise $$$\texttt{AND}$$$ of the rows $$$B_i, B_{i+1}, \ldots , B_{i+m-1}$$$. You can find it for all $$$i$$$ using the approach in this blog.

»
6 месяцев назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

In fact, this can be pushed a bit further, to obtain a structure of size O(n) that computes any sum in O(α(n)) time. See https://arxiv.org/abs/2406.06321.

»
6 месяцев назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Well-known in Krasnoyarsk

»
6 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Another way of thinking about it is by trying to simulate a queue with 2 stacks. Then you maintain prefix / suffix aggregated values starting from the bottom of each stack so that queries can be answered with a single merge of the two top values.

It's also quite cool that this can be done in worst case $$$O(1)$$$ per insertion / window movement, by doing the "slow stack movement" in advance. A paper that roughly describes the idea and some additonal things can be seen here.

»
6 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

In Argentina we call this "Hugo DP", I wrote a blog about it once

»
6 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

bro trying really hard to get back to top 1 contributor