Відео

Ommggg amazing explaination

4:40 bookmark

好棒好棒🙃

For anyone confused about the "for j=1 to j = 7" part, here is my take at explaining this: For every point p in S, we need only to check points q in distance dist(p, q) <= d. Recall that every pair of points in the left sector has distance at most d. Same thing for the right sector. (If it wasn't that way, we would have a smaller d.😏) Take a paper and draw a circle (a filled circle, not just circumference) of radius d and center point p. Try fitting as many points inside as you can, so that all points in the left half are at least d distance apart from each other. And in the right half, also they are d distance apart. You get a hexagon (6 vertices + 1 center = 7) i.imgur.com/FWN0Okm.png Thus we can iterate through S and check just the next 7 points.

this is amazing. Thank you so much for saving our souls in algorithm class.

hello, i wish you could do more explanation videos like this. I really appreciate your clear explanation!!!

Thank You ma'am.

how did she arrived at the 2nd strip

very very nice explanantion....

Incredible explanation, the best I have found, thank you very much!!!!!!!!!!!!!!!!!!!!!!!!!

牛逼 上课没听懂在你这里听懂了

we definitely need more of these explanations from you

wow this was amazing. thank you so much for this!!

i have a question. does the question assume there are coincident points? if coincident points arent allowed, then when checking in the 2d * d rectangle, can we just check for the next 5 points instead of 7? since coincident points will not happen. thanks.

The only tutorial on the channel had to be the on the topic i was looking for.

Best explanation, bar none

OMG, that was the BEST explanation EVER! You're a lifesaver, thanks a TRILLION!

great explanation, thank you

I think it's enough to iterate j from 1 to 4 because in each side the maximum number of points is 4

Great Explanation but i have not understood clearly

now find the optimal solution for N-dimensional Euclidean space.

For split pairs why we iterating 1 to 7?

That was awesome Keep it going🎉🎉

W vid

感恩

amazing amazing amazing and the best explanation for this problem. Thank you

講的很好！😊

how did you find delta in 6,8 do you brute force the left and the right with out divide it ?

3:55 7 points explanation

so great , that was i am loving version.

Thank you so much , I wanted to bring to your attention a concern I have regarding the time complexity of the closestPair function in this algorithm. Specifically, when calling the function for all elements of Y in the following lines: dl = closestPair(X[1 .. mid], Y); dr = closestPair(X[mid+1 ... n], Y); I believe this approach increases the time complexity. The search for the strip is performed in Y, which has a length of N. Consequently, the work done by subproblems becomes O(N), where N is the number of all the points of the problem. This happens because Y is not getting smaller through the dividing process. I propose a modification where the work by subproblems is O(L), where L is the length of the subproblem. To achieve this, the Y in the call to closestPair(X, Y) should contain the same elements as X, with X being the array that undergoes division. Thank you for considering this suggestion.

Great explanation mam.

Thank you! :D

5:57 Why for j=1 to 7? what's the 7 about?

woah wasn't expecting to find this after reviewing dynamic programming

Pls accept my LinkedIn request 🥺

الله يدخلش الجنة يارب

3:35 2-delta distance 4:08 2d*d O(1) for each point

God Bless you, you are great

thank you

This video does not contain enough detail to understand. This one is better ua-cam.com/video/kCLGVat2SHk/v-deo.html&ab_channel=AlgorithmsbySharmaThankachan

Thank you! Great explanation!

8:00 Y sorted points also need to be halved before recursion to ensure optimal complexity, right? This can be done via (id) based filtering of Y into Y_left & Y_right based on a HashSet representation of what goes into X_left & X_right. Am I missing something? Great explanation otherwise :)

thanks a lot for your explanation

Code in c++ : #include <iostream> #include<bits/stdc++.h> using namespace std; bool compare(pair<int,int>a , pair<int,int>b) { return a.second<b.second; } long dis(pair<int,int>& a , pair<int,int>& b) { long d = (long)(a.first-b.first)*(a.first-b.first)+(long)(a.second-b.second)*(a.second-b.second) ; return d ; } long fun(vector<pair<int,int>>&x , int s ,int e ) { if(s>=e)return LONG_MAX; if(e-s+1==2) { long d = dis(x[e],x[s] ) ; return d ; } int mid = (s+e)/2 ; long l = fun(x, s, mid) ; long r = fun(x,mid+1 , e ) ; long d = min(l,r) ; vector<pair<int,int>> arr ; for(int i =s ; i<=e ; i++) { if(x[i].first>= x[mid].first-d and x[i].first<=x[mid].first+d) arr.push_back(x[i]); } sort(arr.begin(),arr.end(),compare) ; for(int i = 0 ; i<arr.size() ; i++) { pair<int,int> t =arr[i] ; int z=6 ; for(int j=i+1; j<arr.size() and z>0 ; j++) { long dd = dis(t,arr[j]); d =min(d, dd ) ; z-- ; } } return d ; } long closestPair(pair<int, int>* points, int n) { //Write your code here vector<pair<int,int>> x ; for (int i = 0; i < n; i++) { x.push_back(points[i]); } sort(x.begin() , x.end()) ; long ans = fun(x ,0 ,n-1 ) ; return ans ; } int main() { int n; cin >> n; pair<int,int>* arr = new pair<int,int>[n]; for(int i = 0; i < n; ++i) { cin >> arr[i].first >> arr[i].second; } cout << closestPair(arr, n); delete[] arr; }

Who told you the brute force solution was n squared? Once a test has been performed, it can be tagged as done. Then that pair test does not need to be done again. Consider 4 points; 1,2 3,4 1 needs to test 2,3,4 2 only needs to test 3,4 (because 1,2 test is already done)) 3 only needs to test 4 That is only 6 tests need to be performed, not 16 (n squared) Formula is probably factorial n... Please get gour facts right!

Beautiful algorithm explained by a beautiful voice

Hello. I doubt you're watching the comments on this video of yours still, but I really need to point that you have a beautiful voice. This song reminds me of some really pleasant and far-away memories. As many of them are slowly fading away, the calming sound of this cover is helping me, a lot. 0:58 to 1:23 makes me cry almost everytime. Thank you for making this video, Have a long life.

Quality content, I was looking for. Thank you!

Such a beautiful baddie..🥹🥹🥹 Ur so talented Ling