UPDATE 3: Made change to the explanation of why the DP recurrence works.
UPDATE 2: Even though the DP recurrence for medium problem works flawlessly, I am now in doubt about the chain of reasonings I followed to prove it. If you can see the missing links, please comment. Until then, expect a 3rd update.
UPDATE 1 : Added a single dimension DP solution to medium problem.
Each month there is always one SRM whose timing just doesn’t suit me at all. The early morning SRM! And this SRM was one of those, a 7AM one for me. I either end up not performing well in such an SRM, or not participating at all. And this time it was the latter case. But I just tried it in practice room, and proves I would have done pretty well, as I was able to get both the easy and medium without much hassle. I didn’t bother with the hard problem yet.
[click to continue…]
Just as the title suggests, this SRM was a bitter disappointment for me. The easy problem was easy, but it took me some time to come up with a simplified solution. I made up for this delay with a successful challenge in the challenge phase. But the sad part was the medium problem. By reading the problem statement, I instantly knew it was a DP, and that the greedy solution won’t work. Part of my jumping straight to a DP solution was because of my current love for DP problems and thus being always preoccupied with a solution containing DP. But alas, things didn’t work as planned…
[click to continue…]
O boy! This was a tough SRM. In DIV2, only a small number of participants could solve the medium problem, and even fewer could get the hard one right. But problems were nice overall.
[click to continue…]
This blog is primarily a programmer’s blog about programming. So you will see lots of code snippets in most of my posts. To properly handle the indentation, syntax highlighting, line numbering and other such issues with code snippets in a post, I needed a reliable wordpress plugin. I tried a few different ones, and finally decided on SyntaxHighlighter Plus. It is easy to use (with one problem that I am going to discuss), and the final result is very nice looking, as you can see in my posts.
[click to continue…]
Graph theory is one of the most important topics of study in computer science. It is so, because a lot of real world problems can be modelled using graphs. A lot of natural and human-made structures, are in essence, graphs. For example, an organization’s administrative hierarchy can be modeled as a graph with certain employees working under certain project leads, which in turn report to certain department heads. It can be used to model transportation systems, electric circuits, human interactions, and telecommunication systems. Basically anything representing a relation of some sort between members of a set/group, can be essentially represented as a graph. That is why study of graphs is fundamental to computer modeling. In this first piece in a series of posts I want to write about graphs, we are going to introduce graphs, how they can be represented in computation, and some basic but very important algorithms that deal with graph traversal and exploration.
[click to continue…]
So a year of Topcoder SRMs came to end. It was the last SRM of the year today. It wasn’t an ideal SRM for me, should have done much better. But still, I ended gaining in rating, however little it be (+3).
Wasn’t such a great year for me to be honest. I had set a goal for myself much higher then where I eventually have got to. But slow and steady wins the race, eh? So I hope next year is much better for me. In order to improve faster, I’ve decided to blog every contest I participate in, specially Topcoder SRMs and Codeforces rounds.
[click to continue…]
Ah the elusive division one. Seems like I have to wait even more then I expected to be part of that elite(!). Because this SRM didn’t go that well for me. The easy problem was solved by many, very fast. My guess is that most of the people just looked at the examples, noticed a pattern, and submitted a solution on that. That is how I came up with the solution too, but I took a bit of time to prove the solution to myself. This delay caused me precious points that proved to be decisive in my rating lost at the end. The medium problem was a tricky one. I spent a lot of time trying to come up with a solution, and tried many fancy ways, but nothing seemed to work. In the very last few minutes I realized that there could be a brute force solution, but I went about implementing that the wrong way. With just one easy solved, submitted few precious seconds late then many, I ended up losing 28 points in my rating.
[click to continue…]
Statement
You have two eggs, and access to a 100 story building. The eggs you have are specially strong eggs. There is some floor on the building below which the eggs will not break, if dropped. What is the most number of drops you need to perform in order to guarantee that you will find that floor? In other words, what is the worst upper case bound on the number of drops you must make to determine this floor?
[click to continue…]
Apple introduced a new tool called Facetime during the launch of iPhone 4, that lets users of iOS and MacOS devices to have video chat in real time with their friends, with a pretty good image resolution. Skype recently also brought video chat facility to their mobile application. But in places where you have good wifi connectivity, and know that the person you want to call also has a Facetime supporting device, you would always want to go with Facetime, due to its better image quality, compared to Skype’s more compressed video.
But there is this one weird thing about Facetime. While on the iPod Touch, and Macbooks, you can use it instantly where ever you have access to wifi, it is not the same with iPhone. You will have to activate the service in order to use it on your iPhone. From what I’ve gathered, this activation process sends across couple of SMS messages to some Apple servers, after which, if it went well, you’ll be able to use Facetime on your iPhone.
[click to continue…]
You can throw any amount of browser speed benchmarks at me, show me how your browser has a lesser memory footprint, and/or reduced cpu load, but you won’t convince me to switch my browser from Google Chrome to something else. Well, not right away. That is, until Chrome does something terribly wrong, or other browsers pick up on some of the UI gems that Chrome has, or at least one of them. Read on…
[click to continue…]
