vaibhav29498's blog

By vaibhav29498, history, 6 years ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone get the interview invite?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 :(

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have posted the editorial here: https://codeforces.me/blog/entry/64999