fake_id_123's blog

By fake_id_123, history, 6 weeks ago,

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.

• +10

 » 6 weeks ago, # |   0 How would you count pairs $i < j$ such that $a_i < a_j$? Can you extend the idea? Hint for PairsCan we efficiently determine for each $j$ the number of $i < j$ such that $a_i < a_j$? Solution for PairsLet $N$ be the length of the permutation. Create a fenwick tree on $N$ elements and process indices $j$ in increasing order. After processing index $j$, increment position $a_j$ in the tree. Before processing $j$, query the tree for the number of $a_i < a_j$. Keep a total count of valid pairs. Hint for K-TuplesIn the solution for pairs, the fenwick tree represents previously seen 1-tuples. At any particular $j$, querying the tree determines how many existing 1-tuples may be extended to 2-tuples using the new element. Solution for K-TuplesMaintain $K-1$ fenwick trees $T_1, T_2, ..., T_{K-1}$. Position $y$ in $T_x$ indicates the number of $x$-tuples ending with value $y$. Process elements of the array left to right as before. After processing an element with value $y_0$, update position $y_0$ in each tree. Keep a total count of $K$-tuples.
•  » » 6 weeks ago, # ^ |   0 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
•  » » » 6 weeks ago, # ^ |   0 You're right, I misread it.
 » 6 weeks ago, # |   0 This seems very similar to 1400D - Zigzags. 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.
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 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.
 » 5 weeks ago, # |   0 Is this problem similar to this one ?
•  » » 5 weeks ago, # ^ |   0 It could have been similar if they asked number instead of possibility, we can solve this one easily by calculating suffix prefix minimum in linear space