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 ≤ |X_i| ≤ 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 X_i cannot be visited unless all the vertices present in the set X_i-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=|X_j+1| where mask(k) = 1 if the k^th vertex of set X_j+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.