PROBLEM LINK
DIFFICULTY
SIMPLE
PREREQUISITES
Ad Hoc, Graph Theory, Associative Arrays
PROBLEM
Sridhar was a seasoned traveler. He liked to visit new places. More than all he was a meticulous planner. This time he was planning to visit Europe. He wrote down his travel itinerary like as follows:
If he wanted to visit Madrid, Paris, Munich, Warsaw and Kiev in this order, he would write it down like as:
Madrid Paris 100 Paris Munich 200 Munich Warsaw 150 Warsaw Kiev 120
More formally, if he wanted to go from A to B directly and the price is C dollars, then he would write
A B C
on a card. Each move was written on a different card. Sridhar was a great planner, so he would never visit the same place twice. Just before starting his journey, the cards got shuffled. Help Sridhar figure out the actual order of the cards and the total cost of his journey.
EXPLANATION
Let us assume we are given an array of edges E.
- E[i].from is the starting node of the edge i.
- E[i].to is the ending node of the edge i.
- E[i].cost is the cost of the edge i.
Let F be the set of cities that are mentioned as from in any of the edges.
- F must be a container that allows for efficient insertion and lookup.
- An example would be the hash_set container in C++, or the HashSet container in JAVA.
- Node that you can also use the set container in C++, but set is based on RB-Trees and allows insertion or lookup in O(log N) time, where N is the number of keys stored.
Let T be the set of cities that are mentioned as to in any of the edges.
- T must also be as efficient as F.
F - T (the subtraction of the set T from F) will contain only one city, say C. This city is the starting city for our resultant path.
Observe the following pseudo-code to calculate F - T.
for each f in F // O(|F|)
if T.contains(f) // O(1)
F.delete(f) // O(1)
Let, Fr be an associative array.
- Associative Arrays can also be deemed as Hash Tables.
- They allow O(1) storage and lookup of (key, value) pairs.
- An example would be the hash_map container in C++, or the HashMap container in JAVA.
- Node that you can also use the map container in C++, but map is based on RB-Trees and allows insertion or lookup in O(log N) time, where N is the number of (key,value) stored.
Observe the following snippet of pseudo-code for building Fr
for i = 1 to N-1 // O(N)
Fr[ E[i].from ] = i // O(1)
As you can see,
- Fr maps a city name to an integer.
- To be precise, Fr maps the city which appers as the from city in edge i to i.
Now, we have sufficient data structures to efficiently construct the path from the city C.
Observe the following snippet of pseudo-code
while Fr.contains(C) // O(|Fr|)
e = E[ Fr[C] ] // O(1)
print e.from, e.to, e.cost // O(1)
C = e.to // O(1)
The above snippet will efficiently spit the required path.
This problem can also be solved using Topological Sorting. Since the graph for this problem contains N nodes and N-1 edges, the complexity of the Depth First Search would remain O(N).
SETTERS SOLUTION
Can be found here.
TESTERS SOLUTION
Can be found here.
