matrix_mlv's blog

Need Help in Timus 2034 Caravans
By matrix_mlv, history, 4 years ago, In English

I need hints and suggestions for Problem 2034 Caravans on Timus Online Judge. I could not find a proper explanation for the problem online. Problem on Timus 2034

Only clues that I could get is to do two BFS from node s and d and get the nodes that lie on the shortest path and now is stuck how to calculate the answer from this.

thanks for any help.

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

»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

You need three DP arrays: d[N], h[N], and v[N], where d[u] is the minimum distance between nodes (r) and (u), h[u] is present maximum distance between (r) and any node along the shortest path between (s) and (u), and v[u] is the present minimum distance between (s) and (u), respectively.

  1. Initialize all elements of d and v to -1, all elements of h to 0.
  2. Initialize d[r] to 0, and do BFS starting from node (r) to compute d[u] for all other nodes. Let node (a) be the front node of the BFS queue, and let b = d[a]+1. Then, for each node (u) adjacent to (a), if d[u] = -1, then the DP value d[u] should be set as d[u] = b, and (u) should be pushed to the BFS queue.
  3. Initialize h[s] = d[s], v[s] = 0, and do BFS starting from node (s) to compute h[u] and v[u] for all other nodes. Let node (a) be the front node of the BFS queue, and let b = v[a]+1. Then, for each node (u) adjacent to (a), let c = min(h[a],d[u]). If v[u] = -1 or (v[u] >= b and c > h[u]), then the DP values v[u] and h[v] should be updated as v[u] = b and h[u] = c. If the updated node (u) is not equal to (f), then (u) should be pushed to the BFS queue.

The answer to the problem should be equal to h[f] after the end of step 3.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you explain the h[N] part little bit more ?? Like what we are doing with "c = min(h[a],d[u])". Thanks!!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Consider the sample input given in the problem statement

      7 7
1 2
2 4
2 5
3 4
4 6
5 6
6 7
1 7 3

      The first BFS run starting from node 3 should generate the following 1-indexed array.

      d = [3,2,0,1,2,2,3]

      as the minimum distance between node 3 and nodes 1,2,..,7. There are two shortest-distance paths between nodes 1 and 7 with minimum distance 4. 

      1. 1,2,4,6,7
2. 1,2,5,6,7

      The problem goal is to compute the maximum of the minimum distance between node (r) and any node (u) along one of the shortest paths between nodes (s) and (f).

      The expression min(h[a],d[u]) is the expected update to h[u] at node (u) that is adjacent to the present node (a) in the second BFS run starting from node (s) if either the node (u) has not been visited yet, v[u] = -1, or has been visited but it is a valid update where v[a]+1 <= v[u] and min(h[a],d[u]) > h[u]. When node u has a valid update, the values of v[u] and h[u] are updated. Furthermore, if u is not equal to f, then the updated node u is pushed to the BFS queue.

      The second BFS run starting from node 1 should generate the following 1-indexed arrays 

      v = [0,1,3,2,2,3,4]
h = [3,2,0,1,2,2,2]

      Therefore, the answer to the sample test case is h[7] which is equal to 2.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have added few comments to my Accepted code , please start reading from main function . I hope it may help .

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I did this problem using binary search + bfs.

Let's reframe the statement a little. Let x be the farthest distance that robber can travel from r. we have to find the minimum value of x, such that robber can block all the shortest paths from s to f.

Why binary search works? If x distance blocks all shortest paths, then so does x + 1, and if x distance doesn't block all shortest paths, then x — 1 doesn't either. So there's the standard pattern of 0 0 ..... 0 1 1 ...... 1, where we have to find the first 1.

Now first calculate the shortest distance of f from s, using ordinary bfs, maintaining a distance array. Store this value, say min_path.

Now let's come to the predicate function for binary search. If x is the farthest distance robber can travel, do a bfs from r, only till nodes i, upto which distance[i] <= x. mark all these nodes visited. Now do a bfs from s to f, calculating length of shortest path from s to f. If this is equal to the min_path, then there still remains a shortest path that is not blocked (0), else if it comes out greater than min_path, then all shortest paths have been blocked (1).

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used a similar approach, bfs + binary search

    Here is my Accepted Code --> https://pastebin.com/puQ53JMZ

    Hope it helps

    → Reply