Wednesday, July 29, 2009

Range Minimums and Maximums

WARNING!!! The following algorithm is incorrect! For a counter example consider the set { 9 , -10 , -10 , 5 , 5 }. It will say that the answer to Q(1 , 5) is 9, but it is fact 10. However, though it is incorrect it does provide you with a good place to start.

At first I was going to talk about the SPOJ problem ORDERS in this post, but decided to put that off. Mainly because I found something else more interesting in addition to the fact that I still haven't completely finished ORDERS.

First off, here is a link to a TopCoder tutorial on RMQ (range minimum query). This post is by no meant a substitute for the tutorial. I would recommend reading the tutorial after this post (only because you are already here) to see more on the topic. Now the problem I will be discussing is GSS1. I would like to point out at this time that the solution I am going to give WILL NOT GET ACCEPTED!! It is far too slow, but should give you a good idea on where to start or proceed.

So suppose we were naieve and decided to do all our preprocessing at the beginning and then ansewr each query in O(1). Obvioulsy the first data structe we think of is an array. So we will let Ans[i][j] be the answer to the query Q(i,j).
Now how does one go about creating this array? Well obviouly the answer to Q(i,i) is the input[i], where input[] is the given array, so

Ans[i][i] = input[i].

Now suppose that we know the value of A[i][j] how would we find Ans[i][j+1]? Well, there are three possibilities.
  1. Ans[i][j+1] = Ans[i][j]
  2. Ans[i][j+1] = input[j+1]
  3. Ans[i][j+1] = Ans[i][j] + Sum(input, k+1, j+1)
In the above k is the index of the last element that is used to make A[i][j] (more on this in the example later on). So using this we can build our array Ans[][] in O(n^2), which actually isn't that bad for small cases.

input = { 1 , 2 , -2 , 4 , -1 , 1 }

So Ans[][] will be a 6x6 array.

Ans[1][1] = 1 clearly. Now for Ans[1][2], we can either use Ans[1][1], only use input[2] or add to Ans[1][1]. So in this case we will want to add to Ans[1][1], thus giving Ans[1][2] = 3. Note that k was 1 so Sum(input, k+1, j+1) = 2

Now for Ans[1][3] we have the following cases;
  1. Ans[1][3] = Ans[1][2] = 3
  2. Ans[1][3] = input[3] = -2
  3. Ans[1][3] = Ans[1][2] + Sum(input, 3, 3) = 3 - 2 = 1
So trivially we want Ans[1][3] = Ans[1][2] = 3.

Just for good measure consider Ans[1][4];
  1. Ans[1][4] = Ans[1][3] = 3
  2. Ans[1][4] = input[4] = 4
  3. Ans[1][4] = Ans[1][3] + Sum(input, 3, 4) = 3 -2 + 4 = 5
Thus it is best to take all the elements in this case giving Ans[1][4] = 5. And you continue this process.

Well here is the C++ code that you have been waiting for (unless you like some other language). Once again I would like to say that this method WILL NOT WORK!! for the case on SPOJ. (note I assume that the first element of the array input[] is 0, just to make things easier to code)

memset(Ans,0,sizeof(Ans));//not needed but I just like to know what's in my arrays

for( int i = 1; i!=(n+1); ++i)

for( int i = 1; i!=(n+1); ++i)
for( int j = i+1; j!=(n+1); ++j)

I'll leave the implementation of my_max( ) and Sum( ) up to you, along with a way to keep track of k. Note that you will need to be "creative" when making Sum( ) so that the above stays O( n^2) and doesn't become O( n^3).

In the link to the tutorial at the beginning of this post he describes other methods to solve this problem. Some have much better performance. The one I plan on using has preprocessing time O( n) and answers queries in O( log n). Some of the other methods that he claims are easy to code (though I would disagree) have preprocessing time O( n) and answers queries in O( sqrt(n)) and preprocessing time O( n log n) and answers queries in O(1).

Tuesday, July 21, 2009

DAGs and DP: aka one thing I'm good at and another that I'm not

So I haven't solved an SPOJ problem in a while. Mainly because I've been doing other things. Well today the drought is over. I managed to solve RENT.

I'll just describe how I went about solving this one. I should mention that the idea was not totally mine. Anyway, I will assume that you have either read the problem or are familiar with it's statement.

Well first off there is the obvious O(2^n) algorithm but obviously this is out of the question considering that the program has 3s to run and n can be as large as 10000. So the next thing to try is looking for a DP solution. This is where DAGs (Directed Acyclic Graphs) come into play, though it might not be obvious.

You construct the graph in the following way. There is an edge between vertex U and vertex V if there is an even starting at time U and ending at time V. Also the weight of the edge is equal to the amount of money you will get for selecting that activity. At this point you execute the DP portion by using a variation of a DFS (So as to not spoil the problem completely I'll let you figure that part out yourself). Just remember that you are looking to make the MOST money in the alloted time.

This method is O(E+V) once you have created your graph. I think the way I created my graph is close to O(E). With a few optimizations the above will work (at least in C++), my solution finished in 1.71s so if you are using Java or another language that isn't particularly "fast" some additional tweaks (or a completely different algorithm) might be necessary. I would like to mention that there are other methods to solve this problem but I didn't find them to be quite is intuitive or obvious. Plus I like working with graphs, and thought that transforming this into a graph problem was rather interesting.

EDIT: Now I also want to edit my algorithm so that it will also tell you which events to select. I don't see this being all that difficult, so I'll probably think about it later this week, and hopefully have an solution (an efficient one that is) by Sunday.

Wednesday, July 15, 2009

New News

Not sure if I mentioned on here before, but I have a job for the summer. Sure I'm glad to have a job but I really would rather be doing something that is more math or computer related. And more computer related than using MSOffice. This has further motivated me to become quant. Also I'm preparing for the GRE, ideally I would like to take it before I start school again. However, I am not sure I'll be able to learn all the vocab (random words and roots) by that time; as well as do lots of practice problems and test. Then I get to take the math subject test in October, and again in November if needed.

In some of the free time I have I've managed to start another blog, start leaning regular expressions, learn Bash programming, read a few chapters from an algorithms book, and learn a little more about C++. So not too bad if I don't say so myself, however none of these topics has really been explored to much depth. Notice the lack of math on that list, it's pretty depressing. I'm considering buying a book on Measure Theory (either with relation to probability or integration) and another on Stochastic Processes.

Well that's all for now. Just though I'd drop by and give a brief update since I've been somewhat busy recently.