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

general
, ,
32

Thanks! One thing at a time.

I will finish graph series; then dynamic programming will be started. I have loads of good ideas for DP too (since its one of my stronger subjects)!

Subscribe to stay notified.

One more Dijkstras coming up this evening! Already done, but am releasing it in the evening! <3

2 Likes
33
1 Like
34

Uploaded Detection/Retrieval of Negative Cycle

2 Likes
35

Digraph Cycle Retrieval

36

I am uploading Topological Sort theory now.

1 Like
37
38

Reuploaded first 9 videos with better audio

3 Likes
39

Reuploaded first 12 videos for better audios. All videos have good audio now. Will continue the series.

40

Just uploaded Graph 17: Longest Flight Route :: Modified Dijkstras(CSES 16: 1680) - YouTube

I have also given a homework assignment this time. Go ahead and get active in comments!

1 Like
41

Finished uploading ONE more Dijkstras and one more Topological Sort problem!

1 Like
42

Although I completed all graph theory from CodeNCode , I saw some of your videos quite well explained , try to complete solve all question of CSES in graph category .

1 Like
43

Offtopic : could you please make a video editorial of CodeChef: Practical coding for everyone and explain your solution

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!