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