RMQ (Range Minimum Query), who r u?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
allornothing
New poster
Posts: 4
Joined: Thu Jul 08, 2004 3:13 pm

RMQ (Range Minimum Query), who r u?

Post by allornothing »

I'm newcomer, so help me pls!
What's the RMQ problem? :o

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

The RMQ problem is a very interesting problem.

The problem itself is just as simple as finding the minimum element between two indices.

The naive solution can be < O( n^2 ), O( 1 ) > or < O( 1 ), O( n ) > (< Preprocess, Query>). It can be done cleverly in <O( n log n ), O( 1 )>. In fact, the general RMQ problem reduces to the LCA problem, which can be reduced to the +/- 1 RMQ problem, which can be solved in <O( n ), O( 1 )>.

There are a few good short papers on this, so perhaps you should look it up.. the math is fun! :)

allornothing
New poster
Posts: 4
Joined: Thu Jul 08, 2004 3:13 pm

Post by allornothing »

Thanks! :)
And what's about this problem, does the solution use RMQ? How to solve?

Problem 7: Cave Cows 2 [Brian Dean, 2004]

In one cave Bessie is planning to explore, a long corridor is made
up of N segments (1 <= N <= 25,000 and numbered 1..N) joined
end-to-end. Each of these segments has a particular width which
can only be traversed by a cow whose "fatness" index is no larger
than that width. A cow can travel along a sequence i..j of these
segments only if its fatness index is no larger than the minimum width
of all of those corridors. Corridor widths are integers in the
range 1..1,000,000,000.

In order to plan her caving expedition, Bessie needs to answer a
collection of Q (1 <= Q <= 25,000) queries of the form "what is the
maximum fatness of a cow that can pass through the sequence i..j
of corridors?". Please help Bessie with her dilemma.

PROBLEM NAME: cavecow2

INPUT FORMAT:

* Line 1: Two space-separated integers, N and Q

* Lines 2..N+1: Each line gives the integer width of a corridor. Line
2 describes corridor 1; line 2 describes corridor 2; and so
on.

* Lines N+2..N+Q+1: Each line corresponds to a query and contains two
space-separated integers i and j (where i < j), giving the
indices of the corridors at both ends of the query interval.

SAMPLE INPUT (file cavecow2.in):

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

OUTPUT FORMAT:

* Lines 1..Q: Each line contains the integer answer to a query

SAMPLE OUTPUT (file cavecow2.out):

5
38
20
5

Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

Post by Gigi's Baby »

Hi,
Could anyone tell me which problems in UVA are RMQ or LCA problems ?

nibbler
New poster
Posts: 22
Joined: Fri Jun 04, 2004 10:30 pm

Post by nibbler »

I solved Cave Cows 2 like this: divide the segments into groups of 50, and preprocess the min of every group. Example querry: what is min from 117 to 873?
Compute "manually" min from 117 to 150, then you now mins from 150-200, 200-250, ... , 800-850, then manually from 850-873 again. Maximal time to answer queries is 150 operations, and I think it ran fast enough.
General solution can be also short, try googling.

Post Reply

Return to “Algorithms”