acash's blog

Need help with time complexity for Flipkart Interview Problem
By acash, history, 4 months ago, In English

Problem statement A series of highways connect n cities numbered from 0 to n — 1. You are given a 2D integer array highways where highways[i] = [city1i, city2i, tolli] indicates that there is a highway that connects city1i and city2i, allowing a car to go from city1i to city2i and vice versa for a cost of tolli. You are also given an integer discounts which represents the number of discounts you have. You can use a discount to travel across the ith highway for a cost of tolli / 2 (integer division). Each discount may only be used once, and you can only use at most one discount per highway. Return the minimum total cost to go from city 0 to city n — 1, or -1 if it is not possible to go from city 0 to city n — 1.

Example 1: Input: n = 5, highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], discounts = 1 Output: 9 Explanation: Go from 0 to 1 for a cost of 4. Go from 1 to 4 and use a discount for a cost of 11 / 2 = 5. The minimum cost to go from 0 to 4 is 4 + 5 = 9.

Time complexity As per my understanding Time complexity for this would be k * E log (V * k). Since Each edge can be reached with k different number of discount values and with decreased toll value everytime (k * E) and also this means each vertex may be present in heap k number of times (log(V * k)). Here K is the number of discounts. Is it correct ?

  • Vote: I like it
  • -1
  • Vote: I do not like it

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

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

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

make two identical graph G(u,v) and G'(u,v) such that G'(u,v) initialize to G(u,v) now for edge E(u,v) make and from node u to v with weight w/2 where u belongs to G and v belongs to G' now apply dijkstra's shortest path algorithm from node 0 and find distance of node n-1 of graph G' here is code for this problem

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<pair<ll,ll>>>v(2*n);
    ll x,y;
    ll c;
    for(int i=0; i<m; i++){
        cin>>x>>y>>c;
        x--;
        y--;
        v[x].push_back({c,y});
        v[x].push_back({c/2,y+n});
        v[x+n].push_back({c,y+n});
    }
    set<pair<ll,ll>>s;
    s.insert({0,0});
    vector<ll>dist(2*n,1e15);
    dist[0]=0;
    while(!s.empty()){
        auto p=s.begin();
        ll dis=p->first;
        ll node=p->second;
        s.erase(p);
        for(auto pr: v[node]){
            if(dist[pr.second]>dis+pr.first){
                auto itr=s.find({dist[pr.second],pr.second});
                if(itr!=s.end()){
                    s.erase(itr);
                }
                dist[pr.second]=dis+pr.first;
                s.insert({dis+pr.first,pr.second});
            }
        }
    }
    cout<<dist[2*n-1];
}
→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this is for discount = 1 if you have k number of coupons then make k+1 copies of graph

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

k is not required inside log as far I understand your solution

See this Click

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

    Could you guys Please help with time complexity of this ? indresh_hErd ANIKET_IITB

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

    I think k also come in log as well because basically we are making k copies of original graph so TC: k(E+V)log(kE)

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

      why log(KE) ? We always insert vertex in heap a vertex can be relaxed with k different values or in other words we end up visting the same vertex with k different values. So a vertex can be present inside heap k number of times and for all vertex it is v*k shouldn't it be log(v*k) ?

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

        we don't insert vertex in heap we insert touple ( vertex ,weight) in heap. vertex can come again in heap with different weight. so Log(EK) will come

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

        Yes I agree with you log(kV) is correct

        Regarding aniket's explanation altough we are inserting tuple but the unqiue component in it is the vertex and vertex will atmost k times as explained by you

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

Djikstra

→ Reply