amit.codename13's blog

Algorithm for Robotic sort problem
By amit.codename13, 14 years ago, In English
I am trying to solve this problem,

http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3961

I can think of a O(n2) algorithm but its too slow for this problem. 
I think some data structure built with trees and linked list should solve this problem
Can anybody give some hints/ideas for this?
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
I know how to solve this problem with Cartesian tree. It allows you to reverse any segment in O(log2n).
Idea is like in RMQ with group operations.
To do this, you need to store in each vertex additional bool rev - need we to reverse this subtree, or not.
When we try to modify or query some vertex, check this value and if it's true, swap two childs, and <look comment at bottom>
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Not so. "swap two childs, and" set l.rev=!l.rev; r.rev=!r.rev.
    → Reply