INSCTS4- Cool Numbers
Problem Setter: @tavan_edla
Editorialist : @kcahdog
Problem Statement:
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.
Solution:
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[2001][2001].
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[2001] 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[2001][2001]; //already created
bool visited[2001]; //initialize to zero
int depth[2001]; //Required answers
queue<int> q;
void bfs() //Function Declaration
q.push(42); //42 is starting point,push it in queue
visited[42]=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.