Codenation hiring contest: What's the solution to this problem?

Revision en1, by vaibhav29498, 2019-02-01 11:33:56

I recently gave the Codenation hiring contest organized on 26 January 2019. I encountered the following question:

We are given a weighted undirected graph with N vertices (1 ≤ N ≤ 100). There are X disjoint sets of vertices (1 ≤ X ≤ 10, 1 ≤ |Xi| ≤ 10). A vertex may not be a part of any set. We have to start at vertex a and reach vertex b. The following conditions should be met:

  1. All of the vertices present in the union of the X sets should be visited at least once.
  2. A vertex present in set Xi cannot be visited unless all the vertices present in the set Xi-1 have been visited.

We have to determine the minimum cost. If the task is impossible, print -1.

I tried the following approach for the same:

I implemented a 3D dynamic programming approach in which dp[i][j][mask] represents the minimum cost to perform the task if we are currently at the vertex i after visiting sets 1..j, and mask is a binary array of length=|Xj+1| where mask(k) = 1 if the kth vertex of set Xj+1 has been visited. We will then use DFS and return the answer when all the sets are visited and we are at vertex b.

However, due to less time, I couldn't debug my code so I am not sure about the validity of this approach. I will be grateful if someone could share their approach.

Tags #dynamic-programming, #dfs, bit-masking, #interview

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English vaibhav29498 2019-02-01 11:33:56 1408 Initial revision (published)