[Video Tutorial Series] Graph Theory: From Beginner to Intermediate - Dardev

general
, ,
44

This problem is really good, will get you more views for sure from leetcode viewers!

It’s based on Dijkstras algo…

1 Like
45

Thanks mate!

46

Thanks. Its fantastic. I have “already solved a similar problem” … this is very trivial. Let me just solve it.

47

I will make a video editorial later; but here is my code with explanation in comments at start. Does it make sense?

/*Binary Search*/
/*
1) Given a range L....R; consider a valid sequence l...r. such that l.....r+1 is invaid. 
2) How many strings can be formed by this subsequence, that begin with l?
3) Ans is r-1+1
4) Now consider the larger sequence L... R. let us walk from L to IND 
5) Such that for each of these chars, the longest valid string ENDS before R.
6) The contribution of all these are static and can be calculated from presums of step 3.
7) the portion from IND+1 to R, well these end with R. So we can use summation formula to get their contri
8) Statis sum is Sigma(R-(IND+1)+1) = (R-IND)(R-IND+1)/2
8) Final Ans is static+summation.
*/

#include <bits/stdc++.h>
#define int long long
#define kpr fastIO()
#define endl "\n"
using namespace std;
 
void fastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}

void preproc(int Arr[], int maxLimits[], int n, int k)
{
    int cnt_0 = 0, cnt_1 = 0, i, ind = 1;
    for (i = 1; i < n; ++i)
    {
        if(Arr[i] == 1)
        {
           cnt_1++; 
        }
        else
        {
            cnt_0++;
        }
        if(cnt_0 > k or cnt_1 > k)
        {
            while(cnt_0 > k or cnt_1 > k)
            {
                maxLimits[ind] = i-1;
                if(Arr[ind] == 1)
                {
                    cnt_1--;
                }
                else
                {
                    cnt_0--;
                }
                ind++;
            }
        }
    }

    for(ind; ind < n; ++ind)
    {
        maxLimits[ind] = n-1;
    }


}

void prefixSums(int maxLimits[], int psums[], int n)
{
    psums[1] = maxLimits[1] - 1 + 1; int temp;
    for (int i = 2; i < n; ++i)
    {
        temp = maxLimits[i] - i + 1;
        psums[i] = psums[i-1] + temp;
    }

}

void solve(int maxLimits[], int psums[], int k, int l, int r )
{
    int ans, summation;
    auto itr = upper_bound(maxLimits+l, maxLimits+r, r) - maxLimits;//starting index of first string that ends at loc greater than r
    int ind = itr - 1; //starting index of the last string that ends before r.
    ind = min(ind,r);
    ans = psums[ind] - psums[l-1];
    summation = (r-ind)*(r-ind+1)/2;
    cout << (ans+summation) << endl;
}


int32_t main()
{
    kpr; int t, n, k, q; cin >> t;
    while(t--)
    {
        cin >> n >> k >> q; ++n; int Arr[n], maxLimits[n]; char c;
        Arr[0] = 2;
        for (int i = 1; i < n; ++i)
        {
            cin >> c;
            if(c=='0')
                Arr[i] = 0;
            else
                Arr[i] = 1;
        }

        preproc(Arr, maxLimits, n, k);
        int psums[n] = {0}; int l, r;
        prefixSums(maxLimits, psums, n);
        for (int i = 0; i < q; ++i)
        {
            cin >> l >> r;
            solve(maxLimits, psums, k, l, r);
        }

    }
}
1 Like
48

okay cool

1 Like
49

Really grateful for direction and feedback.

Its easy to get lost … without viewer feedback.

Thanks @vai53 @ss

1 Like
50 
typedef tuple<int,int,int> tupl;
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& edges, int src, int dst, int k) {
        vector<pair<int,int>>adj[n];
         for(int i=0;i<edges.size();i+=1){
             adj[edges[i][0]].push_back({edges[i][1] , edges[i][2] });
         }
    
        
   
    // min priority queue  of tuple <cost , node , remaining K >   
    priority_queue<tupl , vector<tupl>, greater<tupl> > pq;
    
    pq.push({0,src,k});
        
    int cost = 0;
    if(src == dst)
            return 0;
       
    while(!pq.empty()){
        
        tupl tt = pq.top();      
        pq.pop();
        
        cost = get<0>(tt);
        
        int node = get<1>(tt);
        
        int new_k = get<2>(tt);
        
        if(node == dst)
                return cost;
        
        if(new_k >=0)
        {
            
            for(auto xt : adj[node])
            {
                
                pq.push({cost + xt.second , xt.first , new_k-1});
            }
        }
    }
        return -1;
    }
};
1 Like
51

Excellent job!

52

Great Explainations . Keep up the good work bro