difask's blog

How to solve problem "Reverse RMQ"?

By difask, 10 years ago, In English

I have an interesting problem on data structures.

We're given an array a[1..n]. Also we're given queries l,r,m and it means that min(a[l]..a[r])=m. We should restore array a.

How to solve? Thank you!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Here is the main idea. For example, you have query with maximum answer from all queries. Now you can just make all numbers from L to R equal to M because all that you know about those numbers is that they are not less than M and maybe some less numbers. So you do with next query and so on (of course you change only those numbers that weren't changed before). That's a good solution but too slow. You can see that K-th number is maximum answer from all queries that cover this number. So now we use the scanline idea: sort queries by L and go from first element to last, taking answer from set of current query answers. This solution works in O(NlogQ + QlogQ), where Q is the number of queries.

Sometimes you also need to check if such array can exist. You can just try to build it and then check all queries again by building a segment tree on A array. Asymptotic is the same.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    That's a good solution but too slow.

    As I understand we should for i-th position use maximal value that was in queries. Is it correct to build segment tree with maximums on queries. And then get an array. It isn't slow O(Q*logN)) and seems correct.

    taking answer from set of current query answers

    How efficiently keep set of query answers?

    Thanks!

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it 
      >How efficiently keep query answers.

      This is what scanline does the best. Basically for each query you make two events: adding M into set on L position and deleting it from set on R + 1 position. Then you sort these events by their position and just track them from first to last, processing all events for position K before setting this number. (Set actually means multiset, at least for C++)

      >Why not to build segment tree...

      You can do it like you want, I just prefere this solution. You can also use treap and maybe there are other solutions that are as efficient as this one.

      → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Yes, his idea is all correct. you can sort all the queries with start index then for each query follow the given procedure

for i in range(queries) :

L = i(starting point)
R = min(i(endpoint),(i+1)(startpoint)-1)
for this segment answer is M

basically the idea is to make all the segment disjoints and value for a given segment is the maximum of all queries value involved in that segment :)

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This task has already been used in TCO14 Round 2C (and I am the writer).

Here you can find the solution:http://apps.topcoder.com/wiki/display/tc/TCO+2014+Round+2C

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

Pff, my idea seems to be wrong, sorry :)

→ Reply