4
$\begingroup$

I encountered the following problem on Codeforces.

An array of integers $p_1,p_2,…,p_n$ is called a permutation if it contains each number from 1 to n exactly once. For example, the following arrays are permutations: $[3,1,2],[1],[1,2,3,4,5]$ and $[4,3,1,2]$. The following arrays are not permutations: $[2],[1,1],[2,3,4]$.

There is a hidden permutation of length $n$.

For each index $i$, you are given $s_i$, which equals to the sum of all $p_j$ such that $j<i$ and $p_j<p_i$. In other words, $s_i$ is the sum of elements before the $i$-th element that are smaller than the $i$-th element.

Your task is to restore the permutation.

How can I solve this problem using segment trees in $O(n\log n)$ time?

I tried to understand the solution on Codeforces but I could not understand it. Their solution:

Let us fill the array with numbers from 1 to $N$ in increasing order.

1 will lie at the last index $i$ such that $s_i=0$. Find and remove this index $i$ from the array and for all indices greater than $i$, reduce their $s_i$ values by $1$. Repeat this process for numbers $2,3,\ldots,N$. In the $i$th turn, reduce the elements by $i$.

To find the last index with value zero, we can use segment tree to get range minimum query with lazy propagation.

I do not understand what is stored in segment tree (like least number in the given range) and how the update is done in $O(\log n)$ time in this case. Can you show me an example input and show me what happens in each iteration?

My attempt: I tried to solve this problem by making a segment tree where each node will contain the smallest number in the range corresponding to that node. But I was not able to solve the problem.

For example: Suppose I have sample input:

5
0 1 1 1 10

My segment tree will look like:

                           [1-5](0)
                          /        \
                      [1-2](0)      [3-5](1)
                    /      \         /      \
                [1-1](1) [2-2](1)   [3-4](1) [5-5](10)
                                   /       \
                              [3-3](1)      [4-4](1)

Value adjacent to each range is minimum value in its sub tree. I failed to solve using this approach since update will take $O(n)$ time.

$\endgroup$
  • $\begingroup$ @Mike You are right that in a standard segment tree, updating an interval of leaves requires $O(n)$ time: Actually this is already somewhat of an improvement over the naive approach where you call update on each leaf; since a single update takes $O(\log n)$ time (the single leaf change propagates up to the root), then updating all leaves[k] for $i\leq k \leq j$ could take $O(n\log n)$ time. To get to $O(n)$ time, what you are doing is updating all the leaves in sequence, then recomputing the tree from the leaves to the root, and since there are $2N$ nodes, this is $O(n)$ time. $\endgroup$ – Matthew C Oct 31 '19 at 18:07
  • $\begingroup$ All that is to say, that you can augment your standard segment tree so that the following particular kind of interval update takes $O(\log N)$ time: increment all leaves $k$ in $i\leq k \leq j$ by the same constant $C$. Note this isn't the same as the above discussion, where you could update leaves to their unique new values in total $O(N)$ time; here you really must be calling the same kind of update on all leaves in your interval. Anyway, for instructions on how to augment your segment tree see geeksforgeeks.org/lazy-propagation-in-segment-tree $\endgroup$ – Matthew C Oct 31 '19 at 18:09
  • $\begingroup$ And you can see in your problem that this is exactly the kind of update you are doing; decrementing ALL leaves to the right of some given node by a constant; "all leaves to the right" is an interval of leaves, and the decrement is by the same amount for each ($-i$, at step $i$ in the solution)) $\endgroup$ – Matthew C Oct 31 '19 at 18:13
0
$\begingroup$

The segment tree is useful in this problem because you need to maintain an array of values where the supported operations are: 1) decrementing all elements in a range by the same amount and 2) querying a range for its (rightmost) minimum-value location.

In this problem, the values maintained in the array are the sums $s_i$, that have to be adjusted as described by the solution.

In your example, the subsequent contents of the array will be as follows:

0 1 1 1 10 # we query range (1, 5) and obtain position 1 (rightmost minimum)
∞ 1 1 1 10 # we remove the value at position 1, by setting it to INFINITY
∞ 0 0 0 9  # we subtract 1 from all values to its right (range (2, 5))
∞ 0 0 0 9  # we query range (1, 5) and obtain position 4 (rightmost minimum)
∞ 0 0 ∞ 9  # we remove the value at position 4
∞ 0 0 ∞ 7  # we subtract 2 from all values to its right (range (5, 5))
∞ 0 0 ∞ 7  # we query range (1, 5) and obtain position 3 (rightmost minimum)
∞ 0 ∞ ∞ 7  # we remove the value at position 3
∞ 0 ∞ ∞ 4  # we subtract 3 from all values to its right
∞ 0 ∞ ∞ 4  # we query range (1, 5) and obtain position 2 (rightmost minimum)
∞ ∞ ∞ ∞ 4  # we remove the value at position 2
∞ ∞ ∞ ∞ 0  # we subtract 4 from all values to its right
∞ ∞ ∞ ∞ 0  # we query range (1, 5) and obtain position 5 (rightmost minimum)
∞ ∞ ∞ ∞ ∞  # we remove the value at position 5 and stop. 

Since the sequence of minimum positions was P = [1, 4, 3, 2, 5], it means that in the hidden permutation number 1 is at position 1, number 2 is at position 4, and so on. Hence the hidden permutation is [1, 4, 3, 2, 5], the inverse of P (although in this case it's the same).

$\endgroup$
  • $\begingroup$ I think this treads ground that's already familiar to OP. What they need to know is why "update range" can be done in $O(\log n)$ time (and the answer to that is lazy propagation). $\endgroup$ – Matthew C Dec 1 '19 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.