LOJ 1075 - Finding Routes

Tags : Associative Array, Map, Dictionary, Key-Value Pair

We will be given inputs for a pair of two places. First place is the origin and the second place is the destination. We have to link these pairs in such a format that we get one single route. This single route is a directed one directional link that tells how to traverse through all the places in which order. We will be given the number of total steps required from the ultimate start point to reach the ultimate end point.

Helpful Resources

• Associative array - Wikipedia
• Introduction to Hash Tables and Dictionaries (Data Structures & Algorithms #13) - CS Dojo -YouTube
• Map in C++ Standard Template Library (STL) - GeeksForGeeks - YouTube
• Map (Go Programming Language) - GeeksforGeeks - YouTube
• Python Maps - TutorialsPoint

Solution

This is an implementation problem that we can solve with map/associative-array/dictionary/similar key-value pair data structure.

To keep record of the unique places, will assign an unique number/ID to each unique place's name. We will have two arrays:

• Count array : This will store the how many places are directly connected to it. The number of directly connected places can help us determine if this particular place is the ultimate start/end point or not. The ultimate start point will have no other place before that leads to it since it is the place from where traversing starts, in other words the count will be 1. Similarly, for ultimate end point, the count will be 1 too BUT there will be no place to go to after it.

• Next Destination array : This array's index = initial destination (here, initial destination does not mean the ultimate start point) and value = next destination. Basically, index ---> value = currentPoint ---> nextPoint. It will help us storing we can go from where to where. Note that, we will not be updating this array as if the places were bi-directional links. What we won't do : nextDestination[ID1] = ID2 & so nextDestination[ID2] = ID1. We are not updating in a bi-directional way.

For input, we take two maps:

• <Place, Unique Number> map: will save the inputs taking the place's name as the key.

• <Unique Number, Place> map: will save the inputs taking the unique number assigned to that place as the key.

A map itself can avoid duplication of key entry, however if we push it anyways then the value will get updated which we don't want, so we will check if a key (Place's Name) has been added or not. We are keeping two maps so that we can easily search up a place's unique number by putting it to the map and vice versa.

Now when we finally have everything done, we can easily determine the ultimate start point by the help of both count and nextDestination arrays. For example let's take a set of inputs:

4
SwimmingPool OldTree
BirdsNest Garage
Garage SwimmingPool

Now if we have done everything according to above mentioned procedures, we will have nextDestination and count array like this:

Since now we know the ultimate start point we can start traversing as we also have what is next, after that, then again after that... to the ultimate end point.

Now if we just loop the following until the number of steps required is met, we get all the outputs.

Current Place's Name = <Unique Number, Place>[Current Place's ID]
Next Place's ID = Next Destination[Current Place's ID]
Current Place's ID = Next Place's ID  

The above implementation is accepted.

Solution in C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    //Enable fast I/O
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int testCases, steps, uniqueNumber, startPoint;
    string firstPoint, secondPoint;

    cin >> testCases;

    for (int test = 1; test <= testCases; test++)
    {
        cin >> steps;

        // Index is the origin and Value is the destination
        int nextDestination[steps + 1];


        // How many destinations are directly linked?
        int count[steps + 1];


        memset(nextDestination, 0, sizeof(nextDestination)); // Setting to 0 for false
        memset(count, 0, sizeof(count)); // Setting 0 for no direct connections

        map<string, int> placeIndexMap; // Map to store index as value
        map<int, string> indexPlaceMap; // Map to store string as value

        uniqueNumber = 1;
        for (int i = 1; i < steps; i++)
        {
            cin >> firstPoint >> secondPoint;

            // Checking if duplicate key or not
            if (!placeIndexMap[firstPoint])
            {
                placeIndexMap[firstPoint] = uniqueNumber;
                indexPlaceMap[uniqueNumber] = firstPoint;
                uniqueNumber++;
            }

            // Checking if duplicate key or not
            if (!placeIndexMap[secondPoint])
            {
                placeIndexMap[secondPoint] = uniqueNumber;
                indexPlaceMap[uniqueNumber] = secondPoint;
                uniqueNumber++;
            }

            /*
            Remember, we are updating the array for one direction.
            Thus, when the count of directly connected places of a place is 1 but nextDestination array has 0 for that uniqueNumber, means that the place is the ultimate end point.
            And when count is 1 and nextDestination is 1, it means that it is the ultimate start point.
            */

            // Updating a for the next point
            nextDestination[placeIndexMap[firstPoint]] = placeIndexMap[secondPoint];
            // We won't be updating the nextDestination for the other way around

            count[placeIndexMap[firstPoint]]++; // Incrementing how many places are directly linked
            count[placeIndexMap[secondPoint]]++; // Incrementing how many places are directly linked
        }

        // Finding the ultimate startPoint
        for (int i = 1; i < uniqueNumber; i++)
            if (nextDestination[i] && count[i] == 1)
            {
                startPoint = i;
                break;
            }

        cout << "Case " << test << ":\n";

        for (int i = 1; i <= steps; i++)
        {
            cout << indexPlaceMap[startPoint] << "\n";
            //Assigining the next start point (current start point's end point)
            startPoint = nextDestination[placeIndexMap[indexPlaceMap[startPoint]]];
        }

        cout << "\n";
    }

    return 0;
}

Tutorial source