Code Reuse

So here is a pretty useful trick/hack.
Say you need to create a max-heap. However, the code that you are forced to use will only create a min-heap. What do you do?
Well one solution is to just negate all the input entries, and then create a min-heap. Then the most negative (or most positive depending on how you view things) will be at the top.

I used this trick on my last Data Structures homework assignment. The code that we were allowed to use would create a tree with the smallest element as the root. But we needed to find the largest element. Now I could have easily written my own code, but why should I when code has already been provided? So all I had to do was negate the input and then copy the given code (though I did have to change a few inequalities around). Overall it was a great feeling, like I was "beating the system".
I prefer to look at this as being creative and not as being lazy.

Sadly, I can't take all the credit for this method. I had seen it before while reading a TopCoder tutorial on the C++ STL. They were talking about how to implement Dijkstra's algorithm with a priority queue. In C++ the priority queue container will always put the largest element at the top by default (though you can easily change this).

Being In Control

So whenever I ask someone why they chose to drive a manual transmission instead of an automatic, the response usually sounds something like this. "Because I like the feel of being in control. It's like you, and not the car, are doing the actual driving." Now the funny thing is that this is also the reply I get from some people when asked why they prefer Windows over Linux. Well, they don't say driving, but rather talk about being in control of the computer. Guess that being in control means accepting that there are things you can't control.

Super Freak

I was talking to Ashley yesterday. The conversation was going pretty well. She was talking about how she is enjoying her time in Chicago before going back to MIT. Then somehow we got to talking about programming languages and physics. Personally, I'm pretty surprised that she didn't complain about having to learn to program. Back in high school she would avoid anything that involved using a computer, that wasn't looking stuff up on Google or Wikipedia. But I suppose you can only avoid it for so long while being at MIT.

Well after talking to her, for some reason I started to really freak out about the whole graduate school application process. I still have to write a draft of my personal statement, and take the Math GRE subject test. I have gotten all As in my major classes, participated in a summer research program (paper under consideration for publication), and also plan to do a senior thesis. All this on top of what I am sure will be strong recommendations. Yet for some reason I am still worried. I suppose that I am worried that this won't be good enough to get into the school(s) that I really want to attend.

Correction

Well I fixed my algorithm and managed to solve the problem (see previous post). Here is a general overview.

1. Create array of cumulative sums
2. Create Segment tree
3. Answer queries using segment tree

Each node of the segment tree contained about the location of the max and min elements of the cumulative sum array, that was spanned by the interval. For instance, the node that pertained to the interval [2,4] would contain information about the max and min elements of Sum[2...4], where Sum[] is the cumulative sum array. Also other information might need to be stored in each node, but I'll leave that up to you to discover. Don't want to spoil all the fun now do I?

Now I'm moving onto GSS3, which is more or less the same problem but with the ability to update sequence elements in addition to making queries. At the moment I plan to use the same code but modify certain parts so they they use binary indexed trees.

Found this to be a pretty interesting problem. Think I might try to implement a version for working with 2D arrays. Really it's not too hard to extend to more dimensions but the code just gets longer though the thought process stays the same. To me this is probably the major advantage of using segment trees over sparse arrays. But I must admit that I am not all that comfortable with the sparse array method, so it might extend just as easily (though I don't see it).

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.

EXAMPLE:
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)

Ans[n+1][n+1];
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)
Ans[i][i]=input[i];

for( int i = 1; i!=(n+1); ++i)
for( int j = i+1; j!=(n+1); ++j)
   Ans[i][j]=my_max(Ans[i][j-1],input[j],Ans[i][j]+Sum(input,k+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).

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.

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.