ASHWANTH_K's blog

Two Stack Sorting-CSES
By ASHWANTH_K, history, 12 months ago, In English
  • 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.
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

yes

→ Reply
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Another way to think of the problem is think of the range for how long each number has to be be in some stack. Then problem turns into you have set of ranges where you create edge between two ranges if they partially intersect, bipartite color this graph. It is a standard problem, you can look at solutions to JOISC port facility.

→ Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

thank you

→ Reply