| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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.
How would you count pairs $$$i < j$$$ such that $$$a_i < a_j$$$? Can you extend the idea?
Can we efficiently determine for each $$$j$$$ the number of $$$i < j$$$ such that $$$a_i < a_j$$$?
Let $$$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.
In 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.
Maintain $$$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.
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
You're right, I misread it.
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.
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.
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.