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:
- All of the vertices present in the union of the X sets should be visited at least once.
- 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.
Did anyone get the interview invite?
I got a mail for clearing the online round but my cool down period has not ended yet, so didn't go further with it :(
I have posted the editorial here: https://mirror.codeforces.com/blog/entry/64999