INSCTS4- Cool Numbers
Problem Setter: @tavan_edla
Editorialist : @kcahdog
The problem is equivalent to finding the depth of a number in a tree which has 42 as the root of the tree and each edge represents that the number is in the same sequence as its root.The distance of a disconnected node is -1.
The main challenge of the question is to construct a graph using the different sequences. Once we have the graph we can perform a simple Breadth First Search or use a Shortest path algorithm to find the shortest path from that number to 42. If such a path does not exist, you have to print -1 as the answer.
It is given that the range of numbers in the sequence is less than or equal to 2000. Hence we can use an adjacency matrix of size 2001*2001 to represent the graph for all edges.
Here is the sample procedure to create the Adjacency matrix:
Declare adjacency matrix as int graph.
Here n is the number of sequences and m is the number of elements in each sequences.
Here a is a 100*100 array to store inputs.
Code to Create Adjacency Matrix :
for( i=0 ; i<n ; i++ ) //Number of sequences for( j=0 ; j<m ; j++ ) //Number of elements in each sequence scanf( "%d", &x ); //scan element a[ i ][ j ]=x; //Store it in input array for( k=0 ; k<j ; k++ ) //Connect x to previous elements in same sequence graph[ a[ i ][ j ]][a[ i ][ k ] ]=true; graph[ a[ i ][ k ]][ a[ i ][ j ] ]=true;
We can then pre-compute the depth of each element of the 2D matrix using a BFS algorithm and store it in an array depth as we this is the range of values in the input.
We initialize the depth of 42 to 0 and perform a Breadth First Search starting at row 42 of the adjacency matrix and calculate the depth of each node in the graph.
Here is a sample BFS Procedure :
bool graph; //already created bool visited; //initialize to zero int depth; //Required answers queue<int> q; void bfs() //Function Declaration q.push(42); //42 is starting point,push it in queue visited=true; while(!q.empty()) int s=q.front(); q.pop(); //select element from front of queue for(int i=0;i<=2000;i++) //Check all elements connected to q and insert in queue if(!visited[i]&&graph[s][i]) depth[i]=depth[s]+1; q.push(i); visited[i]=true;
After this procedure is over, the depth for each element will be stored in the array depth
Once we can pre-compute all depths, we can answer each query in O(1) time.
You can see this Top Coder tutorial to learn more about BFS
Link to the Setter’s solution will be put up soon.