Two Stack Sorting-CSES

Revision en1, by ASHWANTH_K, 2023-11-21 21:58:59
  • Problem Link: https://cses.fi/problemset/task/2402
  • I have solved this problem using component merging ideas. complexity: $$$O(Nlog^2(N))$$$
  • Numbers belonging to the same component are assigned in the same stack.
  • One observation I could see was, that if I am able to do an output operation, it's always optimal to output the number as early, without delaying the output operation.
  • Another observation, we could maintain currently active numbers, and if any new number $$$X$$$ is added, we could make a component for all numbers < $$$X$$$
  • I felt happy to solve this problem on my own, as it had only 73 correct submissions till now.
  • I am curious to know if there exists a simpler approach (any mind-blowing observation/ lower complexity) to solve this.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ASHWANTH_K 2023-11-21 21:58:59 808 Initial revision (published)