esskk's blog

Help with problem
By esskk, history, 6 years ago, In English

Calculate number of ways to partition array in groups of consecutive elements,so that for each group following condition holds:the length of group is not less than minimum element in that group and length of group is not greater than maximum element in that group.Each element must belong to exactly one group. Constraints: N <= 5*10^5 Ai <= 10^9

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

Comments Comments (6)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

do with upper_bound() and lower_bound()

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

U cant brute this Should do with nlogn or sth

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

can you write a link on this ploblem, please

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

    It isn't online

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

      If this problem is related to some other contest that is still going on, then most likely no one will help you before it's over. Therefore, we need to know where this task comes from, otherwise it will be dishonest in relation to other participants

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

We can easily come up with an O(n2) DP recurrence: , where RMQ is the range maximum, and RMQ′ is the range minimum. Note that RMQ′ (i + 1, j) - (j - i) is an increasing function for a fixed j, so we can use two pointers to find all valid i.

We can dynamically maintain the suffix maxima as we use the two pointers algorithm using a deque of tuples (left end, right end, maximum) (shortened to (l, r, x)). We are now going to add an extra field lz to our tuple. If j ≥ lz, we are only going to add dpl + j - lz... r to dpj, instead of adding dpl... r. Note that lz = x + l + 1, so we can just sort our tuples by x + l + 1 in a set.

This algorithm is slow if we have many tuples in our deque. However, its amortized time complexity is actually .

→ Reply