double301's blog

By double301, history, 8 years ago, In English

Greetings Codeforces,

I've encountered a very interesting problem during my preparation for an internship interview. The problem is, given N distinct envelopes with specific width and height, determine what is the maximum amount of envelopes that you can russian doll(fit one inside of another). This problem can be solved in O(N*logN) by sorting them in ascending order based on their width and descending based on their height.After we do that we should find LIS which would be our answer.The reason we do descending on height is due to the fact that finding LIS while we have height in random/ascending order can lead into +1 answer while the envelopes have same width so we want to avoid that. Now here comes the twist,how could we solve this problem if we could flip the envelopes?

I was thinking about this approach but i can not prove it. Say we represent connection between 2 envelopes(ability to put one inside of another) as a directed graph,by doing this in O(N^2) complexity we could achieve multi component DAG where we could answer for each component "what is the longest path from source node X",now by doing this we would have to do this for every vertex except the last one that has outdeg 0(in every component), therefor i came to the conclusion that we should just reverse edges of every single component and solve it for "last" node in every component.Total complexity is O(N^2).

I am wondering is this a proper solution and is there a way of doing this quicker?

Cheers

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

| Write comment?
»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

You can simply solve the original problem with all envelopes and flipped envelopes. The reason is that an envelope can never fit into its flipped version, so a chain in the transformed problem can not contain the same envelope twice.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How would we deal with the case like this : 4x9,8x3,10x5 where the answer is 3 ? You suggest that we should take for each envelope N : min(n,m) M: max(n,m), sort them based on the solution of original problem and compute LIS?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Consider the problem with 3x8,4x9,5x10,8x3,9x4,10x5, the lis gives the solution 3x8,4x9,5x10.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I think this greedy transformation would work (even if the restriction would be with less than or equal, rather than strictly less than).