Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

A Classical Problem?

Revision en2, by JianfengZhu, 2023-05-19 11:51:55

You are given a permutation of $$$n$$$. Build an undirected graph of $$$n$$$ nodes. There is an edge $$$(i,j)$$$ if and only if $$$i<j$$$ and $$$p_i < p_j$$$. Please find the maximum matching of the graph.

I don't know how to do it in $$$O(n \log n)$$$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English JianfengZhu 2023-05-19 11:51:55 47 Tiny change: 'the graph.' -> 'the graph.\n\nI don't know how to do it in $O(n \log n)$.'
en1 English JianfengZhu 2023-05-19 11:51:17 205 Initial revision (published)