I was recently puzzled by this problem:
- Given $$$n$$$ intervals $$$[l_i,r_i]$$$. Find the lexicographically minimum permutation $$$p_1,p_2,\dots,p_n$$$ of $$$1-n$$$ such that $$$p_i\in [l_i,r_i]$$$ for each $$$1\leq i\leq n$$$.
This problem comes from misreading the problem A Place For My Head from Petrozavodsk Summer 2017. Day 5. Moscow IPT Contest. The original problem requires that $$$q_i\in [l_i,r_i]$$$ where $$$q=p^{-1}$$$ is the inverse permutation of $$$p$$$ and has constraint $$$1\leq n\leq 2\times 10^5$$$.
I wonder if there exists a decent (subquadratic) solution for this (misread version) of the problem? Many thanks in advance!
Not very practical, but $$$\tilde{O}(n^{1.5})$$$ solution.
Suppose we can efficiently check if there exists a solution for a dynamic set of intervals. We will establish the values $$$p_1, \ldots, p_n$$$ one by one. To find optimal value of $$$p_1$$$, we binsearch the smallest $$$x \in [l_1,r_1]$$$ such that the solution exists if we set $$$r_1 := x$$$ (shrink the first interval to $$$[l_1,x]$$$). Once we have $$$p_1$$$, we can just set $$$r_1 := p_1$$$ permanently and continue with $$$p_2$$$. To test if solution exists we will use the following condition:
Claim. Solution exists if and only if for each $$$1 \leq l \leq r \leq n$$$: $$$|\{ i \mid l \leq l_i \land r_i \leq r \}| \leq r-l+1$$$.
We can view the problem as bipartite matching between intervals and elements $$$1, \ldots, n$$$ (each interval is connected with all contained elements). By Hall theorem we have perfect matching if and only if for each subset of intervals $$$J$$$ it is the case that $$$|\bigcup J| \geq |J|$$$. First, note that it is sufficient to restrict ourselves to sets $$$J$$$ such that $$$\bigcup J$$$ is connected (if we have disconnected subset that breaks the condition, one of the connected parts is also bad). Secondly, the claimed condition captures all subsets $$$J$$$ such that $$$\bigcup J$$$ is connected.
It remains to show how to test the condition for a set of intervals with updates. Let $$$M$$$ be an $$$n \times n$$$ matrix such that:
Then solution exists iff $$$\min_{i,j} M[i,j] \geq 0$$$. To maintain the matrix, we will use a data structure that allows 2D range $$$+$$$ operations and querying the minimum. These operations can be supported in $$$O(\sqrt{q} \text{ polylog } q)$$$ time, but it is not very pretty.
We can initialize the matrix for the initial set of intervals using $$$O(n)$$$ operations:
Then if we want to change input interval, we can update matrix using two operations as in (2). Overall we get $$$O(n \sqrt{n} \text{ polylog } n)$$$ running time.
This doesn't seem correct; if you plug in $$$p=n^2$$$ and $$$d=1/2$$$ into Lemma 1.2 of the linked paper then you get $$$\tilde O(n)$$$ per update, not $$$\tilde O(\sqrt n)$$$.
EDIT: Never mind, see the comment below.
The Lemma 1.2 refers to a variant with explicit point set (they refer to it in paper as "dD RANGE"). What we want is Theorem 1.3 (GRID RANGE variant). Also check out Table 1. The upper bound is for total running time of $$$n$$$ operations on $$$d$$$-dimensional grid.
I think this comment is the perfect example that people will thoughtlessly agree with a person of high authority without verifying whether whatever they said is true or false. No offense to anyone.
I think this comment is the perfect example that people are not seeing and using upvotes/downvotes the way they are intended to be. If I think a comment contributes positively to the discussion even if it is incorrect, I will still upvote it, especially after the poster acknowledged and corrected the mistake. Of course there are some upvotes that didn't go beyond "me see red, me updoot" but it's an irreversible action and I don't find any reason for anyone to downvote such a healthy discussion.
I can see how many down votes Benq would've gotten if he was gray.
To be more clear: i fully agree with your point
Agreed, though I don't think it is relevant to my comment. Newbies getting downvoted is a real issue — just a completely different one. My point is, calling out a comment that adds to the discussion like this is just weird.
My intention wasn't to call out Benq's comment just because he made a mistake, everyone makes them. I just think that upvoting a comment without verifying it's validity will only lead to further confusion. The best option here was not to vote and point out the mistake if possible.
We agree to disagree; personally I don't see any issue with upvoting his comment once he already corrected himself. I upvoted him to appreciate his efforts to help me understand the solution more thoroughly and I give other upvoters the benefit of the doubt, but I see where you are coming from.