Like usual, I’ve been dying on a problem for the last > 2 hours. This time, it’s Sort it Out.
The editorial of the problem says:
How do we choose the smallest set where its complement is an increasing sequence? We choose a set where its complement is a Longest Increasing Subsequence (LIS). Finding the length of the LIS is a classic problem and can be done in O(N\log{N}) time. What about finding the K-th lexicographically smallest set? We use the complement of the K-th lexicographically largest LIS.
I’ve been trying to prove that the complement of the K-th lexicographically largest LIS is the K-th lexicographically smallest set, with no success. Can someone help me?