Friday, October 21, 2016

A few simple graph problems, and their interestingly cute solutions!


Recently, I was solving a few graph problems from here, and I found the questions to be simple yet challenging! By this, I just mean that the questions didn't ask for any advanced knowledge from my side, and yet it was a challenge to come up with simple solutions for them.

There were many questions, for which I too came up with my answers, but they were complex. On the other hand, the given solutions were quite simple, and they had an aesthetic beauty that only an algorithmist can understand. Hence, the cuteness.

I am just providing the questions here in brief, and the underlying thought process that led to those cute solutions. For a detailed study, which you must do, go here.



  1. Design an algorithm that finds all bridges in undirected, connected graph G in O(V · E) time.

    Actually this is the third part of one question. They beautifully and thoroughly made the students think over the solution. The key idea is to think of the BFS tree of the graph.

    First, they asked to prove that all the bridges will be present in the BFS tree of the graph. Then, to examine the running time of checking whether a given edge is a bridge or not. And finally they stated the problem that I mentioned.

    What an amazing way to teach students how to solve problems!

  2. To find an efficient algorithm to find the number of paths in directed acyclic graph G from s to t.

    Topological sorting, and storing the number of paths to all the vertices, using the previous counts to build the next ones!

  3. Suppose you are given a city map with unit distance between each pair of directly connected locations. Design an O(V + E)-time algorithm that finds the number of shortest paths between the source vertex s and the target vertex t.

    Always remember, BFS finds the shortest path to all the vertices in an unweighted graph. And then again, we can store the number of shortest paths to all the vertices, using the previous counts to build the next ones.

    But remember, we are finding the number of shortest paths in an unweighted graph!

  4. Consider a connected weighted directed graph G = (V, E, w). Define the fatness of a path P to be the maximum weight of any edge in P. Give an efficient algorithm that, given such a graph and two vertices u, v ∈ V , finds the minimum possible fatness of a path from u to v in G.

    Amazing question, and what a cute solution! A good reminder to self regarding what value does d[u] store for all the vertices. A simple change in RELAX method of Dijkstra's algorithm. Seriously, this never crossed my mind before I read the solution.

     
  5. Given four vertices u, v, s, and t in a directed weighted graph G = (V, E) with non-negative edge weights, present an algorithm to find out if there exists a vertex vc ∈ V which is part of some shortest path from u to v and also a part of some shortest path from s to t. The algorithm should run in O(E + V log V ) time.
    This is my favourite of all. The solution just requires understanding the basic definition
    d[u,v] = d[u,vc] + d[vc,v]. And there you have it.
I found all these questions to be quite mind-stretching, and yet looking out for only the elements of understanding in me!

 

Sunday, October 16, 2016

Waiting!


I really enjoyed watching this movie Waiting last night. It has something in it which most of us ignore.

If I am asked to summarize the message of this movie in a few sentences, it would go on something like this. Anything can happen in your life at any point of time. You might not accept it, but there is a good chance that someday something very bad will happen. You will be helpless. You will curse others for they have not felt your situation. But life moves on, and so should you!

If you ever face a situation where things are not in your hands, say just like in the movie, a very near one of you has met with an accident, crying doesn't help. Ofcourse, I agree it is easier said that done! But Naseeruddin Shah coveys it concisely - "However bad the situation may be, three things should never stop - eating, sleeping and bathing."

The movie also touches upon the issue of quality of life. And the opinion varies greatly, both in the movie and in real life. I am of the opinion that no one except the victim should have the right to decide what quality of life he wants to live.

But what if the affected person himself is depressed? I guess the doctor in charge should take over the rights. But how come we decide when shouold this be done. What if the quality of life for that person has really gone downhill just like it was depicted in Guzaarish? Conflicting!

I would love to hear your opinions in the comments!

..

While writing all this, two people and their quotes did cross my mind. And I guess quoting those down would be better than attempting to put it down in my own words.

Stephen Hawking has this great line in the end of the movie The Theory of Everything - "There should be no boundaries to human endeavor. We are all different. However bad life may seem, there is always something you can do, and succeed at. While there's life, there is hope."

This person has always been my inspiration. You ask, why? Read the lines in the previous para again. If this person whose quality of life worsened so much, could show this level of optimism, there should and must never be any point in my life where I should be sad or depressed about something bad going on with me!

Saturday, October 15, 2016

Lakes in Berland : Why coding your solution is a good idea?


I write about my solutions to the coding competition problems only for myself. For the problems that stretched my mind a little more. To bring myself a clarity of thought of what i did in the code. To understand my mistakes. Do not read it unless you have really nothing else to do in this awesome universe!

The question : Lakes in Berland. As simple as it could it be. I guess it didn't take me more than 10 minutes to figure out how to solve it. But there awaits the demon. The one everyone talks of. The implementation.

There is a reason why great programmers ask to code your solution. Because just knowing the solution isn't enough! And that is what happened in my case.

It took me quite a good long time, almost a day to get to a working solution! And no, it wasn't anything hard to code. It just reflects my weakness in implementing a solution.

..

While coding the solution, I was noting down all the mistakes that I did, due to which my test cases failed. Here they are in a proper format just to make myself realize my fallacies, and why I need to think a little more before submitting my solution all over again.

MIstake #0 : It took a lot of time to implement the dfs, and the lines of code that I wrote was way more than for the accepted code in C++; always a red signal.

Mistake #2 : I made a very big mistake as my code was allowing the non-starting vertices to be on the border, had to refactor my code to find the connected components!

Wednesday, October 12, 2016

Polycarp At The Radio - Importance of maths in programming!

Many people argue among themselves whether maths is important or not, when it comes to programming. I don't indulge in these arguments, neither this post is going to do anything similar.

But recently I tried to solve a problem which made me realize the importance of mathematical intuition when it comes to programming.

I started to solve this problem on Codeforces, Polycarp At the Radio, and hit sort of a dead end for more than a day.  But something got me hooked to this question. There was nothing special about it. No difficult algorithm tags. And still I was finding it difficult to code.

But I went on to code what I thought to be a good enough code to pass all the test cases. And no, I just didn't start monkey-typing on my keyboard. Yet the end result was around 200 lines of python code, with a lot of comments and debugging statements hidden within it.

And it doesn't stop there. My code still failed on a test case I knew of, I wasn't sure if there still exist other test cases it might fail upon, and just when things seemed to make sense, I realized I had no idea in hell or heaven how to change my code to pass this particular test case.

..

Finally, I gave up, and read the tutorial given for the same. And I just couldn't express how beautiful the solution is. So simple, so intuitive. I can't even say it to be mathematical. But something definitely mathematically intuitive.

And the code was just 40 lines long, with complete surety that it will work for all the test cases, whatever it may be! And this is why, my boy, mathematical intuition is important in programming.

I am linking a github gist here, containing both the buggy and the correct codes, to show how complex a program can get because of the lack of simple mathematical intuition.

Just give this puzzle a try before you hop on to another post of someone else! :)