Toll fee Balancer

Came across an interesting Graph based problem. Try solving the problem, I will post my solution soon

In city to travel from a point A to B there are multiple routes, there can be direct route from A->B and there can few other routes with one or more intermediate nodes like A->C->B or A->C->D->B etc. Each road connecting two points have a cost, so any vehicle using that road should pay that cost to the authorities. This now implies that traveling from A to B will have different costs based on the route that you take.

Let me take an example




In the above figure Node '1' is the starting point and '4' is the ending point and there are 3 different routes to connect 1 and 4, each road has a original cost marked in BLUE. So the cost taking the direct road from 1-4 is 10, whereas taking the path 1-3-4 is just 8 (because 1-3 is 5 and 3-4 is 3), similarly the cost of taking the 3rd route 1-3-2-4 is 12.

Now the problem is to reassign the cost of individual roads so that the cost of all possible routes remains the same. You cannot reduce the cost of a road, but you can increase it. In the above example the cost of road 1->4 and 3->4 is reassigned and the extra cost for these roads are marked in RED. Now taking any of the routes will cost the same amount 12.

Note: There can be few cases with no solution too.


Solution >>>

Here is my solution to the problem

The main objective is to change the cost of the all the routes to the costliest route's cost. In the above example the costliest route is 1-3-2-4 with cost 12. For every other than 1-3-2-4, traverse from the end and try to adjust the fees of the current road. You can do this only if this road is connected by one road, in other words the IN-DEGREE of this road has to be 1. If this road has in-degree more than 1 then traverse back to the previous road in this route and repeat the check. If you cannot find any road with in degree 1 then exit with no solution.

Adjusting the fee of a road is simply done by adding the {cost difference between the costliest route & this route} to this road's fee.

Algorithm

1. Find the costliest route available with us and lets call it as X;
2. Y = ROUTE_COST(X);
3. For (every route other than X) as A
  Begin
4.    R = the last road in this route A;
5.    while (R<>NULL && IN_DEGREE(R) > 1)
     Begin
6.        N = the Previous road connecting to the road R in this route A;
7.        R = N;
     End;

8.    if (R===NULL) then exit with "No Solution";

9.    C = ROUTE_COST(A);
10.  ROAD_FEES(R) = ROAD_FEES(R) + (Y-C);
  End;

Let me know if you see any issues.

Avoid using Fur

The cruelty behind the Fur industry is painful.
See what is happening inside chinese Fur Farms (Warning: Please don't watch this video if you are sensitive)



Pledge to go fur-free at PETA.org.

Let us save them by avoiding Fur.

New members

Yesterday we added two new members to our house. They are just meant for entertaining us and nothing else.

Member 1:
Name: Tropicana Bowling Kit
Origin: Pins from Vinayaka Bakery and Ball from Sapphire






Member 2:
Name: Monopoly
Origin: Sapphire (a Toy shop near Garuda Mall)




The fun has just begun.. :)

The Truth

I came across this video titled "The girl who silenced the world for 5 minutes". Its a video from one of the UN meetings and this girl addressed the audience on the world's environment related issues.

I know she would definitely make you silent for a while!!

Open Hack Day - 2009

It is back again this year.. Yahoo! Open Hack day 2009 being organized at Taj Residency, Bangalore. The second day of the event has begun and the hackers just have 2 hours, 45 minutes left out to complete their ideas. Bangalore has always been very responsive to technical events, this year around 300 people have turned out for this event which included some college students. Yesterday was a eventful day with loads of technical talks, discussions, idea sharing sessions, dance, beer, red-bull, XBOX, PS2, party and of-course HACKING.. I had a chance to make my first external presentation/training yesterday, a memorable one for me.


This time I can really feel the high security at The Taj after the Mumbai attacks, the security was so alert that made few security guards to stop Yahoo!'s founder Filo and asked for his ID.. lol..

With hackers all around me trying to do final integration and presentation of their hacks which they developed through out the night even without taking a small nap (and of course there were few people who played XBOX all the night without any sleep :-P ) I am really eager to know the results..

All the best Hacker!!!

More pics at http://www.flickr.com/search/?q=hackdayindia&ss=2&ct=6

Bangalored

Recently I came across the term "Bangalored". Before going to a dictionary and figuring out what it is, I started making few wild guesses. Could that be a synonym for "struck in traffic" or "costly" or "high tech"? But I was totally wrong, this term means "losing a job just because the project is outsourced". The outsourced place need not be Bangalore it can be any place in the world, still the term remains the same. More info @ http://en.wiktionary.org/wiki/Bangalored

Thanks to all Indian consultancy companies who is responsible for this new term :-). And I hope we Bangalorians are not bangalored anytime.