Amiri's blog

Can be MDOLLS on Spoj solved using LIS tecnique?
By Amiri, 8 years ago, In English

I saw MDOLLS problem in this list was in LIS part and I was wondered how it can solved using LIS?

The question is:

Dilworth is the world's most prominent collector of Russian nested dolls: he literally has thousands of them! You know, the wooden hollow dolls of different sizes of which the smallest doll is contained in the second smallest, and this doll is in turn contained in the next one and so forth. One day he wonders if there is another way of nesting them so he will end up with fewer nested dolls? After all, that would make his collection even more magnificent! He unpacks each nested doll and measures the width and height of each contained doll. A doll with width w1 and height h1 will fit in another doll of width w2 and height h= if and only if w1 < w2 and h1 < h2. Can you help him calculate the smallest number of nested dolls possible to assemble from his massive list of measurements?

I know this problem can be solved by maximum bipartite matching tecnique but I want to know is there any way to solve using LIS?

If we have w1 <= w2 and h1 <= h2 instead of w1 < w2 and h1 < h2 I have an O(n2logn) solution using LIS as follow:

Initially we sort dolls by their w values (and h In the next priority) and then try to remove LIS from new order of dolls. number of times we can remove LIS from our dolls is the answer.

But it's obvious that my solution shouldn't work for original version of MDOLLS with w1 < w2 and h1 < h2 conditions.

Please help me to know is there a solution using LIS for MDOLLS?

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sort in increasing order of w, and in case of ties, decreasing order of h.

Now find the longest non-increasing subsequence.

Consider an array of n integers, the number of increasing subsequences that cover all the array is equal to the longest non-increasing subsequence.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Pay attention When we have two dolls with the same w we can't choose both of them in a LIS!

    example:

    w = {2, 2}
h = {1, 5}

    answer is 2, how you handle this case?

    UPD: your answer for this case is correct too, but can you prove why it is correct?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Sort in increasing order of w, and in case of ties, decreasing order of h.

      w = {2, 2}

      h = {5, 1}

      Longest Non-increasing Subsequence = 2

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        your answer for this case is correct too, but can you prove why it is correct?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          My idea was that every element from the longest non-increasing subsequence will form a new increasing subsequence, and any element not from the longest non-increasing subsequence can be added to one of the previous increasing subsequence.

          If you want a formal proof check this

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 2   Vote: I like it +8 Vote: I do not like it

            Got it! Thank you very much

            UPD: Accepted.

            → Reply