Roundgod's blog

By Roundgod, history, 16 months ago, In English

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!

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

| Write comment?
»
16 months ago, # |
Rev. 2   Vote: I like it +73 Vote: I do not like it

Not very practical, but $$$\tilde{O}(n^{1.5})$$$ solution.

Spoiler
  • »
    »
    16 months ago, # ^ |
    Rev. 2   Vote: I like it +48 Vote: I do not like it

    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.

    • »
      »
      »
      16 months ago, # ^ |
      Rev. 2   Vote: I like it +51 Vote: I do not like it

      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.

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      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.

      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          16 months ago, # ^ |
          Rev. 3   Vote: I like it +12 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            16 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              16 months ago, # ^ |
                Vote: I like it +9 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                16 months ago, # ^ |
                  Vote: I like it +15 Vote: I do not like it

                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.