INSCRIPTION13 EDITORIAL- Cool Numbers

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.

5 Likes

Hello @kcahdog,

First of all, if you were the author of this contest, congratulations!! Problems were amazingly written and with good corner cases too :smiley:

I thought about using set interesction to solve this problem.

I would mark the coolness of all numbers by performing a pairwise intersection of the different vectors with 42 as the reference value, i.e., vectors where 42 would be present would be set with goodness 1 and 0 for number 42.

Then by performing a vector intersection with the pairwise vectors, I would construct a sort of “goodness” array…

Would this idea work?

Best,

Bruno

1 Like

@kcahdog, what is the meaning of “output should contain r lines”…? The output in the example testcases are contradicting this statement …!!

@skrcode We had made a mistake in the sample output and it was not possible to correct it later. However we had made an announcement and clarified in the comments section to many people. You should have seen that. we are sorry for the inconvenience

1 Like

@kuruma I am very busy now but will definitely try to answer your doubt later. The Problem setter was @tavan_edla and most problems were made directly and not copied. Glad you liked it

@kuruma. Yes, the basic idea is right. I’m not sure how you would implement the pairwise intersection, but wouldn’t it be O(n2) . We were looking for a linear time algo after the graph has been build carefully, so that queries are answered fast enough.