Rock2000's blog

Flipkart coding test problem... Need help [update: Solved]
By Rock2000, history, 4 years ago, In English

I appeared for Flipkart coding test day before yesterday and got stuck on this problem:
You are given an undirected weighted graph with n vertices and m edges. In one move you can make any edge weight zero. You can perform atmost K moves. You have to tell what is the shortest path from a starting node A to an ending node B after performing atmost K moves.
1<=n<=1000
0<=K<n
1<=m<=10000
1<=w<=10^9 (weight of edge)
Can anybody please tell me how to approach this problem?
I found this problem on quora also but couldn't understand the approach clearly.
[UPD]: This problem has been solved thanks to ExplodingFreeze and _dobby_

Code
  • Vote: I like it
  • -18
  • Vote: I do not like it

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

Auto comment: topic has been updated by Rock2000 (previous revision, new revision, compare).

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

I think we can consider all the path from A to B. Now for each path $$$P_i$$$ let's say $$$e_i$$$ be the no of edges so pick least $$$max(0,e_i-k)$$$ edges w.r.t weight and update the final result.

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

    Can you tell me what is the time complexity of your solution?

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

    Its trivial to make the number of paths exponential. Consider the following construction:

       2   5   8
  / \ / \ / \
 1   4   7   10
  \ / \ / \ /
   3   6   9

    Now there are 2 ways from 1 -> 4, 4 from 1 -> 7, 8 from 1 -> 10 and so on. So we can easily make a graph with $$$2^{\frac{n - 1}{3}}$$$ paths using $$$n$$$ nodes and the naive solution of using all paths will TLE.

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

Please share ,where you got infos of these types of test . I am searching for an offcampus internship. How to get a chance .

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

It is the same problem as here K was small. I dont know what was value of k in your case but if k is small we can use a modified dijskarts to solve this problem. Link to original problem ..Problem.

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

Auto comment: topic has been updated by Rock2000 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

So we effectively want to find the shortest path from $$$A$$$ to $$$B$$$ such that we skip the weight of at max $$$k$$$ edges. So if there removal of edges wasn't there this would be a pretty simple Dijkstra problem, right? So is there some way to interpret the problem differently such that we can still use Dijkstra?

Lets examine the transitions between nodes. Say we are at $$$x$$$ and $$$v$$$ is some node adjacent to $$$x$$$. Lets also suppose we have skipped $$$y$$$ edges till now. When we move to $$$v$$$, we have to decide whether to skip this edge or not:

  • We can choose to add the weight of the edge to the answer we will now be at node $$$v$$$ have skipped $$$y$$$ edges.

  • We can choose to skip this edge we will be at node $$$v$$$ having skipped $$$y + 1$$$ edges.

In both cases there can be many ways (or possibly none) to reach each node for a specific count of edges skipped, and clearly the current state depends on nothing except these the current node and the number of edges skipped. So we just want to find the shortest path from node $$$A$$$ with $$$0$$$ edges skipped to node $$$x$$$ skipping $$$y$$$ edges. Or in other words, we want to find the shortest path to each pair {$$$x, y$$$}. And from some {$$$x, y$$$} we can move to {$$$v, y$$$} (where $$$v$$$ is adjacent to $$$x$$$) at a cost of the edge between them, or to {$$$v, y + 1$$$} at zero cost. Now we can notice this is effectively applying Dijkstra to the state { node, edges used } with the two moves being "edges" to the adjacent states. And we finally want the shortest path to $$$B$$$ skipping at max $$$k$$$ edges, so the answer will be the minimum of all {$$$B, y$$$} for all $$$0 \leq y \leq k$$$.

We have $$$n \times k$$$ states and $$$2 \times m \times k$$$ edges, so the total complexity is $$$O(m \times k \times log(n \times k))$$$ which should pass if $$$k$$$ isn't too large. $$$k \leq 1000$$$ should work as long as the time limit isn't too strict.

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

    Thank you very much. I was thinking in the same way but wasn't able to figure out that node will be {node,edges used} in dijkstra.

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

If A and B are not in the same component, then it is not possible.

Now, if $$$K \geq n$$$, then the answer is always $$$0$$$, as there definitely is a path with less than or equal to $$$n − 1$$$ edges, between A and B, so you can make all these $$$0$$$ (and some of the remaining extra edges, to complete the $$$K$$$ count).

Now, $$$k < n$$$, so $$$k < 1000$$$.

Let dp[i][j] be the minimum distance from A to node $$$i$$$ with $$$j$$$ moves used, where $$$1 \leq i \leq n$$$, and $$$0 \leq j \leq k$$$. This can be calculated in a similar fashion to Dijkstra's.

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

    Misread parent comment.

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

      Yes, the time complexity is $$$O(m \cdot K + n \cdot K \cdot log(n \cdot k))$$$, which is slower than $$$O((n + m) * K)$$$

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

        I misread your comment and thought you were directly performing a dp of some sorts, not Dijkstra >.> .

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

          Hi brother..i have a doubt why can't we just find the shortest path in the original graph between node a and node b and that would be our answer because we can apply k operation in this shortest path thus reducing it even further.

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

            What if there is a path with one edge with a huge weight but others with less weight?

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

    Thanks bro.

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

    Could you please elaborate this solution. I am not able to understand how the time complexity is brought down to O((n+m)*K) using this.

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

      The complexity is not reduced, my solution runs in $$$O(m \cdot K + n \cdot K \cdot log(n \cdot k))$$$, which is slower than $$$O((n + m) * K)$$$.

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

Auto comment: topic has been updated by Rock2000 (previous revision, new revision, compare).

→ Reply