TOURMAP - Editorial

PROBLEM LINK

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Ad Hoc, Graph Theory, Associative Arrays

PROBLEM

You are given N nodes and N-1 directed edges. You have to arrange the N-1 edges such that they form a linear path from the first node (the one with no in-edges) to the last node (the one with no out-edges).

You also have to find the sum of cost of the edges, which can be done trivially.

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.

7 Likes

Hi,

I tried to solve this problem using linked lists and hashmaps. I declared a class “city” with the following members-

  1. String c1 (city’s name)
  2. city next (a pointer to the next destination/city)
  3. int val - cost of travelling to this city (this value is -1 if the city is the first city in the iternary)

I used a hashmap “map” also to store the addresses of the city (class) objects. In the hashmap city name was key and the city (class) object was value. Thus map.get(“city-name”) returned the class object corresponding to the city.

In every iteration i followed these steps-

  1. retrieve the two citynames city1 and city2 and the cost.
  2. create objects for city1 and city2. for city1 object val was set to -1 and next pointer was set as a reference to city2 object. for city2 object val was set to the cost and next set to null. If the object had been created for either of the cities in a previous iteration i simply updated val to the cost.
  3. Cost was continously added and stored.

In the end, the city with element val = -1 was taken as head (since no cost of travelling to this city was found). Thus with this head city i traversed down and displayed the result.

But i got incorrect answer for my submission. Could you please have a look at my


[1] and tell me what am i missing ?

Thanks ! 


  [1]: http://www.codechef.com/viewsolution/1522473

You have to be careful when you are working with global variables in problems with multiple test cases - see this one http://ideone.com/wboryX

Also take care about output format - see my second test case in above link.

My solution is here if you need to know what is requested result.

Hi,
I had solved this problem and here is the link to my solution
link text
But I got the runtime error upon submission. If somebody clears my doubt,it will be of great help.
Thanks in advance.

Hello @ejaj_hassan,

Well, it seems that your code does not respect the output format properly… :frowning:

It says specifically that the cities names must be space separated… And according to your output on IDEone, all the cities are joined together without any single space…

I would suggest you adding an extra white space between both cities and travel cost as well and it should get you the correct output format! :smiley:

Regarding the runtime error, I’d say that it’s almost for sure regarding the usage of stringstream… As it is basically the only thing I did not use…

Good luck,
Bruno

Hi @kuruma
Thank you so much for your answer. Well even if I insert a single space in output format, I was getting the wrong answer.I don’t understand your answer for that stringstream part. Kindly explain to me what does it cause to be so. Thanks again.

Ejaj

Hello again Ejaj,

Basically the reason I suggested you could try to use separate string and/or char variables to read input, instead of using stringstream to parse a whole line at once like you’re doing, is that sometimes stringstream can throw some unexpected exceptions, that can be found on sites like stackoverflow and cplusplus… Bottom line, stringstream requires careful usage and it’s much easier for this problem to follow the editorial idea and simply use strings :wink:

Bruno

hash_set is now deprecated. So which container is best replacement for it?

Hello,
I’m trying to solve this problem using only C++ map, but I get WA. Any hints where that comes from ? thnaks :slight_smile:
Here’s my code:
http://www.codechef.com/viewsolution/4184908
I found an error because i wasn’t initializing my variables at each turn, I added:

mymap.clear()
reversed_map.clear()
costmap.clear()

But i still get Wrong Answer :confused:

I finally got AC :smiley:
I was computing the travel cost when inputting the costs assuming that all cities will be visited.
I changed the computation to be done when searching for the ordered path and that got AC :))

Sorry, but could you please explain what the problem with counting while taking input is? Don’t we have to visit all the cities?

Really nice problem for learning STL maps and sets.

1 Like