JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Range minimum query on any online judge? | Reply
Hello,
I've implemented a solution that works with all cases I try. However, I'm not pretty confident about its bug-freedom so I would like to field test it with some online judge.

Do you know any problem on any online judge (including TopCoder) that it's the classic Range minimum query problem?
Re: Range minimum query on any online judge? (response to post by wack-a-mole) | Reply
Here's one
Re: Range minimum query on any online judge? (response to post by mhayter1) | Reply
Thanks a lot! I got accepted.

Do you know of any other problem that also asks for updates in an arbitrary position of the array?
For example:
array = {2, -1, 3}

query(0, 2) -> -1

update: array[1] = 7
array = {2, 7, 3}

query(0, 2) -> 2

Thanks again!
Re: Range minimum query on any online judge? (response to post by wack-a-mole) | Reply
This is the dynamic range minimum query. I guess you have implemented a segment tree to solve it.

Usually when I want to check whether some solution is correct, I write some trivial solution, a generator for test cases, and a program which runs the generator and the two solutions, compare their output, and if they are different stops. This way you can check whether your solution is wrong and what case it fails (this works best on small test cases). If you can't find a test case that you fail from ... say 1000 test cases .. you can be 'almost' sure your solution is correct. I do this quite often indeed.
Re: Range minimum query on any online judge? (response to post by anastasov.bg) | Reply
@anastasov.bg Is there any algorithm/data structure that can solve the online version of the RMQ problem in O(1) time per insert/query rather than O(log n)? (I basically want to be able to insert elements in one direction, so even if there is a solution for such a case, it would be good).

For example:
Given: 8 71 6 1 28 11 93 87 19 82 22 33 31 7 9
I want to be able to insert an element at every stage:
[1] 8
[2] 8 71
[3] 8 71 6
[4] 8 71 6 1
[5] 8 71 6 1 28
... and so on ...

and be able to answer queries from any 'k' to the end of the current range. So, after the for the range "8 71 6 1 28" (step-5), I want to be able to answer queries for:
0-4, 1-4, 2-4, 3-4, 4-4 (all in O(1) time).
Re: Range minimum query on any online judge? (response to post by wack-a-mole) | Reply
This problem can be solved using the RMQ version in wich you must modify the values between queries.
Re: Range minimum query on any online judge? (response to post by wack-a-mole) | Reply
This
RSS