fake_id_123's blog

By fake_id_123, history, 3 years ago, In English

Given an array which is also an permutation.
How many tuples are there such that

$$$ i < j < k < l$$$ and $$$ a_i < a_k < a_j < a_l $$$

Another variation was

$$$ i < j < k < l < m $$$ and $$$ a_i < a_k < a_j < a_m < a_l $$$

P.S., this was interview question so no constraints were given, what is best complexity can we achieve.

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How would you count pairs $$$i < j$$$ such that $$$a_i < a_j$$$? Can you extend the idea?

Hint for Pairs
Solution for Pairs
Hint for K-Tuples
Solution for K-Tuples
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i guess,you have misread the question or i might have not understood your solution, but its $$$a_i < a_k < a_j < a_l$$$ instead of $$$a_i < a_j < a_k < a_l$$$, else we could have solved with $$$ K - 1 $$$ fenwick trees

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This seems very similar to 1400D - Зигзаги. You should be able to solve it in $$$O(n^2)$$$ with similar ideas. This should also be extensible to solving the harder variation in $$$O(n^2 \log n)$$$ by using a Fenwick tree to track the number of $$$(l, m)$$$ pairs usable with a given $$$(j, k)$$$ pair.

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

    Could you give more details of $$$O(n^2 logn)$$$ approach, isn't it 2d query, so it must be either $$$n^2{logn}^2$$$ or $$$n^2$$$ if preprocessed, which I am not sure how.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      For a fixed $$$j$$$, the number of $$$(l, m)$$$ pairs that work with the pair $$$(j,k)$$$ is equal to the number of $$$(l,m)$$$ pairs that work with $$$(j, k+1)$$$ plus the number of pairs $$$(k+1, m)$$$ that work with $$$(j, k)$$$. The former can be remembered from a previous iteration, and the latter is exactly the number of values $$$m > k+1$$$ with $$$a_j < a_m < a_{k+1}$$$, which can be found with one Fenwick tree query and update per iteration.

      This can probably be optimized to $$$O(n^2)$$$ by changing the order of the loops, but I have made little effort to work through the details.