Problem statement:
John lives in HackerLand, a country with cities and bidirectional roads. Each of the roads has a distinct length, and each length is a power of two (i.e., raised to some exponent). It's possible for John to reach any city from any other city.
Given a map of HackerLand, can you help John determine the sum of the minimum distances between each pair of cities? Print your answer in binary representation.
Difficulty: Moderate
Submissions: 1319
The problem is a graph problem, so here is her analysis:
Spent over 1 hour to try to figure out the graph problem, what is my best bet to solve the problem.
Find simple problems to work on first:
Algorithm 1. Any two directed connected nodes, find shortest distance:
distance (n1, n3) = 10, go through node 1 -> node 2 -> node 3, instead of directly connected edge - 32
2. Any two nodes in the graph, find the shortest distance:
based on graph in the step 3, find a route from one node to another node, using BFS or DFS, for example, node 1 to node 4, node 1 -> node 2 -> node 4.
min distance (node1, node4)
Spend a lot of time here to try to design the algorithm:
1. using DFS/recursive/memorization solution:
evaluate the solution, problems in the design cannot be solved:
problem and its subproblems are overlapping.
min distance (node2, node4)
Not working
2. using BFS/queue, the design concerns:
1. Avoid loops
2. Stop early -
3. using DFS/stack, the design concerns:
Also, each edge's length is power of 2, different length.
1. Step 1-> Step 2:
Try to work on this graph, for each directed connected graph, use BFS algorithm, try to find a shorter route. For example,
edge(1, 3) = 32,
edge(1, 2) = 8,
edge(2, 3) = 2,
edge(1,3) > edge(1, 2) + edge(2,3), since 32 > 8 + 2,
So, the edge(1, 3) can be marked removable, this direct route will never be travelled.
Work out the above case:
start from node 1, add node 1 to the queue, and then, go through the queue, remove node from queue, add all neighbors to the queue, if it is not visited previously, and if it is the node 3, then only allow twice , as long as the sum is less than edge(1,3) = 32, continue; Make a single linked list, n2.prev = n1, n3.prev = n2,
2. To work on graph in step 3,
For each node in the graph, for example, n1, using DFS or BFS to find a route to node j, j<>i.
So, with those removed edges, only one route will be found through any two nodes, i<>j.
To be continued.
Follow up
April 26, 2017Need to write down C# version to solve this minimum spanning tree algorithm.
---
I’ve tasted success and I’m hungry for more. I’ll prove I’ve got what it takes to win. #CreateYourMark pic.twitter.com/jansdjv9pG— Lucas Pouille (@la_pouille) May 20, 2016
No comments:
Post a Comment