JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Range minimum query on any online judge?
 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) -> -1update: array[1] = 7array = {2, 7, 3} query(0, 2) -> 2Thanks 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 9I 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
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Range minimum query on any online judge? Previous Thread  |  Next Thread