Flipkart coding test problem... Need help [update: Solved]

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
using namespace std;
using namespace __gnu_pbds;
// Policy based data structure 
typedef tree<int, null_type, 
			less_equal<int>, rb_tree_tag, 
			tree_order_statistics_node_update> 
	indexed_set;  
#define ll long long int
#define pii pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define vi vector<ll>
#define vii vector<pii>
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define yes cout<<"YES"<<endl; return;
#define no cout<<"NO"<<endl; return;
#define flus fflush(stdin); fflush(stdout);
#define F first
#define S second
#define np next_permutation
#define inf 1e18
#define mod 1000000007
#define N 1005
#define pi (double)2*acos(0.0)
#define minpq priority_queue <ll, vector<ll>, greater<ll>>
#define maxpq priority_queue<ll> 
/*******************************************************************/
struct state{
	ll dist,node,used;
	state(ll dist1,ll node1,ll used1){
		dist=dist1;
		node=node1;
		used=used1;
	}
	bool operator<(const state&s) const{
		if(this->dist==s.dist){
			if(this->node==s.node){
				return this->used < s.used;
			} else{
				return this->node < s.node;
			}
		} else{
			return this->dist < s.dist;
		}
	}
};
ll n,m,a,b,k;
vii adj[N];
ll dist[N][N];
void solve(){
	cin>>n>>m>>a>>b>>k;
	rep(i,0,m){
		ll u,v,w;
		cin>>u>>v>>w;
		adj[u].eb(v,w);
		adj[v].eb(u,w);
	}
	rep(i,0,n+1){
		rep(j,0,k+1){
			dist[i][j]=inf;
		}
	}
	rep(i,0,k+1){
		dist[a][i]=0;
	}
	map<pii,pii> pa;
	set<state> s;
	s.insert(state(0,a,0));
	while(!s.empty()){
		state curr=*s.begin();
		// curr.print();
		s.erase(s.begin());
		for(auto ch:adj[curr.node]){
			if(dist[ch.F][curr.used]>dist[curr.node][curr.used] + ch.S){
				state temp(dist[ch.F][curr.used],ch.F,curr.used);
				auto it=s.find(temp);
				if(it!=s.end())
					s.erase(it);
				dist[ch.F][curr.used]=dist[curr.node][curr.used] + ch.S;
				pa[{ch.F,curr.used}]={curr.node,curr.used};
				temp.dist=dist[ch.F][curr.used];
				s.insert(temp);
			}
			if(curr.used+1<=k and dist[ch.F][curr.used+1]>dist[curr.node][curr.used]){
				state temp(dist[ch.F][curr.used+1],ch.F,curr.used+1);
				auto it=s.find(temp);
				if(it!=s.end())
					s.erase(it);
				dist[ch.F][curr.used+1]=dist[curr.node][curr.used];
				pa[{ch.F,curr.used+1}]={curr.node,curr.used};
				temp.dist=dist[ch.F][curr.used+1];
				s.insert(temp);
			}
		}
	}
	ll ans=inf;
	rep(i,0,k+1){
		ans=min(ans,dist[b][i]);
	}
	if(ans>=inf){
		cout<<-1<<endl;
	} else{
		cout<<ans<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	// cin>>t;
	t=1;
	while(t--){
		solve();
	}
}

Comments (20)

Write comment?

Rock2000

4 years ago, # |

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

→ Reply

Trgt_2021_explosion

-10

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.

4 years ago, # ^ |

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

ExplodingFreeze

← Rev. 4 →

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.

spakk9

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

It was oncampus.

AM_I_Learning

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.

← Rev. 2 →

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.

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.

_dobby_

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.

← Rev. 8 →

Misread parent comment.

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)$$$

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

saurabh247

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.

+11

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

Thanks bro.

aca123321

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.

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)$$$.

Rock2000's blog