Video

Bhai shorts ki DSA series upload Karo then tier 2-3 wale relate kar payenge .. shorts video bnao nhi toh time waste hai on CZcams this is my opinion 😊.. best of luck Bhai

Bahiya ive written its rec code its showing tle 3d dp

Great explanation my man 🤗

Thanks a ton bhaiya for the help.....🙏🏻🙏🏻🙏🏻

class Solution: def maximumLength(self, nums: List[int], k: int) -> int: n = len(nums) c = Counter(nums) if k == 0: return max(c.values()) if max(c.values()) == 1: return min(k + 1, n) runs = {} best = [0] * (k + 1) for x in nums: if x not in runs: runs[x] = [1] * (k + 1) else: runs[x] = [z + 1 for z in runs[x]] runs[x][1:] = [max(lo + 1, xrun) for lo, xrun in zip(best, runs[x][1:])] best[1:] = [max(lo + 1, b) for lo, b in pairwise(best)] best = [max(b, xrun) for b, xrun in zip(best, runs[x])] return max(best) that's Python easy solution

i have a doubt in second optimization (was able to think of first one on own). The doubt is why prev index doesn't matter. condition says nums[i] != nums[prev] . Like assume nums[i] =1 say at some i we and trying to calculate for j=3 and there was a sequence let say 1 2 2 1 so obv a length of 4 is already precalculated for some prev index also ending at 1 and j=2 as u can see . Now if you will calculate ans for current i you will say 1 + dp[p][2] as you ans => 1 + 4 but actually this is wrong na coz you made a sequence of length 5 saying there are 3 indices in 1 2 2 2 1 1

where to study dp from, I always write the recursive solutions but can't write the iterative ones, even here my solution to the problem with smaller constraints got accepted but couldn't solve the 4th one, something similar happened in one of the problems of recent Amazon hack-on OA. Please suggest some resource

If someone solves this using DP with O(n*n*k) TC and SC, is it good enough to get Strong Hire or Hire verdict at Google for L4 and above?

ya i understood this quiz but we could have done one more thing....iterate from (0--->k) and use a temp array to store the updated values for overallMaxForK array throughout the j loop and then do overallMaxForK = temp bcoz we require values of overallMaxForK array only for p = (0--->i-1) so we can update the array once the j loop is over Am I right ??

I was using only a map to store the length of the max sequence ending at that particular value...so had problem while updating the map, and the second array which represent the length of the longest subseq with atmost k different pairs simultaneously....implementation issues...but glad i could think in somewhat the same direction as yours !!

can anyone explain why it is giving MLE bool check(vector<int>&ele,int k){ int n=ele.size(); int count=0; for(int i=0;i<=n-2;i++){ if(ele[i]!=ele[i+1]){ count++; } } return count<=k; } vector<vector<int>>ans; void getsub(vector<int>&nums,int i,int n,vector<int>&ele){ if(i>=n){ ans.push_back(ele); return; } ele.push_back(nums[i]); getsub(nums,i+1,n,ele); ele.pop_back(); getsub(nums,i+1,n,ele); } int maximumLength(vector<int>& nums, int k) { int n=nums.size(); vector<int>ele; getsub(nums,0,n,ele); int MAX=0; for(int i=0;i<ans.size();i++){ if(check(ans[i],k)){ int m=ans[i].size(); MAX=max(MAX,m); } } return MAX; }

Still not understood

thanks bhaiya 🙏🙏 quite helpful video .... best thing for me is I was trying this from last 1hr but was unable to come up with a soln and i found this video.

Answer to quiz: The reverse might result in wrong answer because we don't wanna use the result of something[j - 1] or something[j] computed at index i to be used for something[j] at the same index.

Nice Thank you... C felt kind of standard but for D i thought similar approach but end up storing for each K using vector<map> and then finding maxx for each k for every iteration.. Took O(n*k*k) . It got accepted 😅 tho I was expecting it to be MLE.

sir the lecture was godly.

Sorry brother, you lost me at white theme. BTW, keep up the good work.

In the problem E suppose i declare both the array inside Int main then i get some random output why ?? rest mine logic was same , also i have matched from your submission

Today in Codechef 134 B i solved 3rd problem using it. It was amazing as you Sir.

Time complexity(fun part was truly fun) until i saw the last ques, that one's a menace. Need to grow a lot. Thanks for the video!

For problem 'F' Let's say we are calculating for x = 6 and i = 6 in that case cnt = 0 here we didn't count any extra points, then why would we subtract - 1 from the count

int lastElementLessThanD(vector<int> arr, int d) { auto it = std::lower_bound(arr.begin(), arr.end(), d); if (it == arr.begin()) { // If lower_bound returns the beginning of the array, // it means all elements are greater than or equal to d. return -1; // Indicating no such index found } else { // Return the index of the last element less than d return std::distance(arr.begin(), --it); } } int32_t main() { // your code goes here jaldi_kar_kal_panvel_nikalna_hein int t = 1; cin >> t; while(t--){ int n, k, q; cin >> n >> k >> q; vi a(k); scan(a,k); vi b(k); scan(b,k); while(q--){ int d; cin >> d; if(d <= a[0]){ cout << (d*b[0])/a[0] << " "; continue; } if((k-2) >= 0 && d >= a[k-2]){ int x = d - a[k-2]; int tot_d = n - a[k-2]; int tot_t = b[k-1] - b[k-2]; int prin = b[k-2] + (x * tot_t) / tot_d; cout << prin << " "; continue; } int idx = lastElementLessThanD(a,d); // cout << endl << d << " : " << idx << endl; int x = d - a[idx]; int tot_d = a[idx+1] - a[idx]; int tot_t = b[idx+1] - b[idx]; int ans = b[idx] + (x * tot_t) / tot_d; cout << ans << " "; } cout << endl; } return 0; } Sir, can you plz tell me where is the problem in this solution for Problem E?? I have used BS on array "a" only ..but it have me TLE on 7th case.

Time complexity +1

Amazing as always! Can you suggest some resources for bit manipulation. I always feel very underconfident while solving them.

Bhaiya I am not getting this in Problem F lets say x is 0. then for that x we calculated the max y possible. But this specific x and y combination will contribute in both quadrants. Then how come multiplying it by 4 gives the correct answer

I think there is a small correction in explanation of problem E. In the example that you took you multiplied distance with distance instead of time: explained equation: d * (a[i] - a[i-1) / (b[i] - b[i - 1]) correct equation: d * (b[i] - b[i - 1])/(a[i] - a[i - 1])

in problem F we are multiplying by 4 for all the points but why are we not checking if any of our points lie on x or y axis bcz then we should multiply by 2 only

i do not get it why cnt(10)+cnt(01)-1 in problem d

Problem E for way more easier than D ,I wasted a lot of time in problem D finding the edges cases

in problem what was the apprroach for optimal solution, it was not clearly understood

Thank you vaia💜

For Problem C : Both points of the second arc has to be on the same side of the first arc

In problem 2, I tried to store all the chars in map and if map.size was 1 it was impossible or else it would be possible so I did print the last half and then first half of string which was giving me wrong ...I didn't get why ?

Thank you for sharing these so quickly Abhishek, I really like the way you deconstruct problems into simple explanations.

Thanks sir! Will watch tomorrow in local while traveling to college...

Sir what if , for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { // code in o(1) } } TC - O(m * n) but what if for(int j=1;j<=n*m;j++) { // code in o(1) } TC - O(n*m) both time complexities are same or differnt

1:29:50 SELF REFERENCE

1:32:23 I didn't get how i-4 , k=4 has 0 operations and how i=3 , k=2 has 2 operations? like all we are doing is multiple k by i so how is it taking more than 1 operations ? and in case if i=4, k=4 what is happening ? i ididn't get it at all

Awesome time complexity lecture!!!

Awesome

sir please change the mic, your voice is not clear

To be very honest, after your first class on cf contest discussion, I thought I have wasted my 1k rs at wrong place but from todays session I proved wrong. Thanks for this amazing session , Now I can say I have learned something new today

after all these years, i am able to understand the time complexity. Thanks Sir!

what a good exapmles thanks sir

Nice sir, fully Understand

Sir Are you Teach "cp" ? in Upcoming video,

That's what we want , now sir take it from basic to advanced I know you will can.