Блог пользователя ASHWANTH_K

Two Stack Sorting-CSES
Автор ASHWANTH_K, история, 12 месяцев назад, По-английски
  • 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.
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

yes

→ Ответить
»
12 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
»
12 месяцев назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

thank you

→ Ответить