Tuesday, March 31, 2009

Printer Simulation


The question above was my "SPOJ victory of the day." On my first attempt at the problem I was thinking too hard about all possible cases. Needless to say this resulted in WA. However, today I looked at the problem and noticed that the bounds were extremely low. So I thought about just simulating the process, and realized after a little thinking that this would be O(n^2) in the worst case, which was not a problem considering the fact that the upper bound on n was about 100. After getting my solution accepted I noticed that there were relatively few TLEs, this should have alerted me sooner that a "trivial solution" was possible

I think the problem would be more interesting if they gave you the times that each job was added to the printer queue. The problem would still be solvable by simulation but it would require a little more "creativity" in doing so. However, the way I coded my solution, it wouldn't be too hard to adapt it for this variation. Basically I used a double-ended queue to keep track of the order of each job request. The reason for using this structure is that it has the ability to quickly add and element to the back and delete and element from the front. In addition I used a heap to keep track of which job currently had the highest priority.

Friday, March 27, 2009

Nice Quote

I was talking to my analysis professor about which classes I should take next semester. We were both clear that I was taking the 6000 level analysis, but then for my other class there was a choice between Functions of Complex Variables and Elements of Topology. His opinion on the subject can be summed up in the following quote,

"If we (the math department) were to only offer one course this (complex analysis) should be it."


Well I was looking for a hash-map in C++ since doing something like


Where myMap is an std::map<> takes logarithmic look up.

So after some looking around I did manage to find that there were hash-maps for C++, but after that I had to do some more searching to see what libraries I needed to include in order to use them.

Below is a little program that just prints the integers 1 to 10 followed by hello world, that makes use of a hash-map.

using namespace std;
using namespace __gnu_cxx;

int main()
hash_map<int,int> myhash;
for(int i=0;i<10;i++)
for(typeof(myhash.begin()) i=myhash.begin();i!=myhash.end();i++)
cout<<i->second<<' ';
cout<<"hello world\n";
return 0;

Certainly not the most user friendly stuff to type at the beginning but I suppose it is worth it. I should mention that when I wrote the second for loop I had no idea if it would compile or not since I didn't know that you could use iterators on hash_maps. Also unlike std::map, __gnu_cxx::hash_map does not store the keys in an ordered fashion, just something to be aware of.

As a side note, if you didn't add the line

using namespace __gnu_cxx;

you would have to type


This should be obvious but you never know when/if you'll one day forget.

Tuesday, March 24, 2009

My 2008 Putnam Results

As expected I managed to score a 20/120, in addition to this I finished 616/3627, so top 17%. To be honest I was hoping that I would have been in the top 15% but I'm not going to complain.

Oh in addition to this our school finished 12th, which is our best finish ever from what I've been told. Sadly I wasn't on the team (I had class at the time of the T.S.T), but hopefully I will be next year and we will finish just as high if not better.

Saturday, March 21, 2009

Hello World

#include <iostream>
int main()
cout<<"Hello world.\n";
   return 0;

You have no idea how long it took to get that to look nice. The part that caused the most problems was getting the '<' and '>'signs to display properly, thanks HTML. After that it was pretty straight forward, you just put the code in between either

<blockquote> ... </blockquote>
<code><pre> ... </pre></code>.

In case you were wondering, in order to display '<' you typed &_l_t_; (without the underscores). For some reason you can make '>' with the one on the keyboard, but you can also do &_g_t_; (once again without the underscores).

Friday, March 20, 2009

Units Actually do Matter

Just another reason no one likes biased news; be it liberal, conservative, 'Apple', or whatever.

You might remember this from a while back, if not then enjoy it now.

Saturday, March 14, 2009

[Inert Your Title Here]

Well it is almost the end of another Spring Break. I had originally planned to copy the Measure Theory portion of my Analysis notes into my new notebook, study look over some Differential Equations, and get in some SPOJ time. Needless to say things didn't go as planned. Pretty much all my free time was spent working on SPOJ.

Most of the problems were ones that I had previously started but for some reason was unable to generate an acceptable solution. The only totally "new" problems were JAVAC, SUMITR, and TRICENTR. None of these were all that difficult, but the source limit on SUMITR did cause some issues. I ended up writing the solution for that in C rather than C++.

Here are the other solved problems and my remarks.

ADOMINO: Exactly the same as AGGRCOW but there are some cases that AGGRCOW didn't have so some modifications needed to be added in order to work around these. Not sure if this should even count as a "new" problem really, but why not, it did take me more than 1 submission.

SBANK: I just needed to use a faster way to read the input. To think that I had this problem unsolved for about half a year only because of this.

SHPATH: I had to implement Dijkstra's with a priority queue (a heap like data structure) rather than a set. Personally I prefer to use the set solution but I can see why the priority queue method is faster.

STABLEMP: My idea of using a greedy algorithm was correct. The problem was in the way I was storing the necessary information. Just imagine my embarrassment when I discovered this small but important mistake.