Longest subsequence which is a union of K increasing subsequences

Revision en2, by Savior-of-Cross, 2022-03-24 09:26:50

I was reading mango_lassi's blog and in one of the paper referred in his blog, I found a $$$O(N^2)$$$ algorithm for constructing a longest k-increasing subsequence (a subsequence of maximum length which is a union of k increasing subsequences). While implementing it, ko_osaga told me about the problem E in "AMPPZ-2015 MIPT-2015 ACM-ICPC Workshop Round 1" (id #6275 in opentrain) where the problem asks to construct such subsequence with constraint $$$N \le 2 \cdot 10^5$$$ and $$$K \le 20$$$.

The official solution runs in $$$O(N \cdot K \cdot (K + \log(N)))$$$. The first half seems to be doing the RSK mapping, but I couldn't figure out why the second half works. It seems to be unrolling the mapping from the back, and maintaining $$$K$$$ intervals for each row in the tableau. And the editorial only explains the first half. Can someone please explain why it works?

Official Solution

Erid-near-windmill

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Savior-of-Cross 2022-03-24 09:26:50 161 (published)
en1 English Savior-of-Cross 2022-03-24 08:23:00 5731 Initial revision (saved to drafts)