I'm newcomer, so help me pls!
What's the RMQ problem?
RMQ (Range Minimum Query), who r u?
Moderator: Board moderators

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

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
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!
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!

 New poster
 Posts: 4
 Joined: Thu Jul 08, 2004 3:13 pm
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
endtoend. 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 spaceseparated 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
spaceseparated 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
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
endtoend. 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 spaceseparated 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
spaceseparated 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

 New poster
 Posts: 19
 Joined: Thu May 02, 2002 5:47 am
 Location: Zhongshan (Sun Yatsen) University
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 150200, 200250, ... , 800850, then manually from 850873 again. Maximal time to answer queries is 150 operations, and I think it ran fast enough.
General solution can be also short, try googling.
Compute "manually" min from 117 to 150, then you now mins from 150200, 200250, ... , 800850, then manually from 850873 again. Maximal time to answer queries is 150 operations, and I think it ran fast enough.
General solution can be also short, try googling.