Блог пользователя AakashHanda

Автор AakashHanda, история, 6 лет назад, По-английски

I decided to write this blog, as a lot of people were requesting for the editorial of Shortest Path Constrained problem from CodeNation Hiring Test, held on 26th January, 2019

Problem

Statement

There is a weighted undirected graph with N nodes and M edges. You are also given X different sets of nodes — S1 to Sx. You have to give the shortest possible distance between a start node — a and a destination node — b, along a path following the following rule: For all i < j, before visiting a node in Sj, you must visit all the nodes in Si.

The distance is defined as sum of weights of edges along the path traversed.

Note :-

  1. The path must contain all the nodes in union of Si for all 1 ≤ i ≤ X
  2. for all 1 ≤ i, j ≤ X and i ≠ j.
  3. The path may go through any node, including a and b, more than once. The constraint is that it must end at b

Constraints

  • 2 ≤ N ≤ 100
  • 0 ≤ w ≤ 100000
  • 0 ≤ X ≤ 10
  • 1 ≤ |Si| ≤ 10 for all i ≤ X
  • Nodes are numbered from 0 to N - 1
  • The graph does not contains multiple edges or self edges, and is connected

Solution

Let us first solve the problem of how to visit all the nodes in a set Si, in shortest possible distance, such that we end up at node x. This problem can be solved using dp + bitmask. Suppose dp[bitmask][x] stores the minimum distance, for this particular set, such that the nodes with bits set to 1 in bitmask are visited, and we end up at node x. Now for all k such that kth bit is 0 in bitmask, we can update dp[bitmask|k][k] = min(dp[bitmask][x] + dist(x, k), dp[bitmask|k][k]). dist(x, k) gives us the smallest distance from x to k and can be pre-calculated using Floyd-Warshall Algorithm.

Now, in this problem, we need to do the above for all the sets, while making sure the nodes from next sets are not visited. To do that, we maintain a list of illegal nodes. When we visit a set Si, we remove the nodes of this set from the illegal list. Now, we create an auxiliary adjacency matrix, which does not contain the nodes from the illegal list. Now we can run the above dp.

We can initialize the dp for Si + 1 using the dp for Si, as shown in the code below.

Code

Click to Expand

Sample Cases (Including corner cases)

Click to Expand

Полный текст и комментарии »

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

Автор AakashHanda, история, 6 лет назад, По-английски

Hi Everyone,

CodeNation, Bengaluru is conducting an online hiring test on 26th January, 2019 at 5:00 PM IST.

Register here: https://goo.gl/forms/7aopASH1dchGbjHE3 for the Online Test Shortlisted candidates will win a chance to interview with us for SDE and SDE Intern positions.

Eligibility Criteria:

  1. Indian nationals
  2. 2019/2020 graduates
  3. Students from all the branches of BTech, Mtech, Bsc, Msc, BCA, MCA, MS .
  4. Students who have never interviewed with CN or have interviewed before July 2018

Upd:

  1. Contest Link: Link
  2. Password: CN26119

Полный текст и комментарии »

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

Автор AakashHanda, история, 7 лет назад, По-английски

I have been trying to solve this problem for some time now but have been unable to figure out a way to find the grundy values for rows. I tried writing a bruteforce solution which gives me the grundy values of rows to try to figure out the relation between grundy values and position of stones in a row but have not been able to observe any pattern.

Any hints would be appreciated.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится