National_Wind's blog

About counting the number of subarray
By National_Wind, history, 4 years ago, In English

Hi guys, I have this problem. In a given array a length n, how many subarray are there that satisfies: max_element — min_element of the subarray is even. Given that 1 <= n <= 1e5, 1 <= ai <= 1e9. I can't figure out a better solution than O(n^2) solution. How to solve this problem? Thanks!

  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What do you mean by consecutive subsequence? Contiguous subsequence(Subarray) or a subsequence which consists of consecutive numbers?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Contiguous subsequence. A subsequence that can be achieved by erasing a number of elements.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The task is to find the number of subarray that in each subarray, the difference between the max_element and the min_element is even.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -19 Vote: I do not like it

        It can be solved using prefix sums.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't think it's possible to solve using prefix sums, because the min and max functions aren't reversible.

          The easiest solution I have in mind right now is a divide and conquer + segment tree solution (that runs in $$$O(n*log^2(n))$$$), I can describe that in a separate comment if you want.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ah, my mistake, I badly misread the problem. Sorry for being misleading.

            → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Here is the $$$O(n*log^2(n))$$$ solution I mentioned in a previous comment.

First, apply standard D&C (divide and conquer). Now our solution is reduced to find the number of segments that go through a specific index whose max and min have the same parity, in subquadratic time. I describe a solution that does this in $$$O(n*log(n))$$$

As you do in standard D&C, split each segment into two parts (the left half, and the right half, each on one side of the midpoint)

There are $$$O(n)$$$ segments on each side, so it is okay to iterate through all of them naively. First, calculate all of the min's and max's for all segments ending at the midpoint. Store them in two arrays, I'll call them $$$l$$$ and $$$r$$$.

Note: These are two arrays of pairs. In each pair, one element is the min, the other is the max of the segment it represents.

Now I just need to find the number of ways to pair an element form $$$l$$$ with an element from $$$r$$$ s.t. the min of the min's and the max of the max's have the same parity.

First sort the elements of both $$$l$$$ and $$$r$$$ by their max's.

WLOG asume the max of the max's is in $$$l$$$ (you can do a similar thing for $$$r$$$). Iterate through all of the elements in $$$l$$$. Store a pointer over $$$r$$$, and add the elements with a smaller max then the current element that we're considering in $$$l$$$ to a data structure. The number of r's that work for the current element that we're considering in $$$l$$$ is the number of elements in our data structure s.t. either:

  1. the minimum is less than the minimum of the element in $$$l$$$ that we are considering and it has the same parity as the maximum of the element in $$$l$$$ that we are considering
  2. or the minimum is greater than or equal to the current minimum (assuming that the max of the current element in $$$l$$$ has the same parity of the min of the current element in $$$l$$$)

What is that data structure? Here are the two queries we want to support.

  1. Find the number of elements <= x which has some specified parity
  2. Add an element to the data structure.

To handle this, we can have two segment trees (or BIT's or ordered sets). In one, we store only even elements, and in the other we store only odd elements. Then, the problem is reduced to standard ops on the data structures.

Using Case 2 of the master theorem, you can see that the complexity of this approach is $$$O(n*log^2(n))$$$.

Let me know if this is confusing.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the l and r array more clearly? Especially the part "calculate all of the min's and max's for all segments ending at the midpoint".

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      As in standard D&C, the goal here is to calculate the answer for all segments that pass through the midpoint. To do this, you look at each segment $$$[l...r]$$$ as a combination of $$$[l...mid]$$$ and $$$[mid+1...r]$$$. Because in this problem you only care about the min's and the max's of segments, that's all you need to store when considering the combination of two segments. In this case, the $$$l$$$ array stores both the min's and the max's of each segment whose right endpoint is the mid, and the $$$r$$$ array does the same except for segments whose left endpoint is the mid.

      → Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    This idea is quite interesting , Like using two pointer we can iterate over the satisfied ranges and just checking for number < min of curr with parity = max of element AND for > min of curr just thier cnts if(parity of min = parity of max)

    Can we have a better solution than this??

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Fakesolved :(

→ Reply