Szczegółowe omówienie zadania Min Cost to Connect All Points:

Link do powyższego omówienia zadania Min Cost to Connect All Points: https://youtu.be/jOqGMOGJQ1s?t=1117
Omówienie kodu który zadania Min Cost to Connect All Points: https://youtu.be/jOqGMOGJQ1s?t=4744

Link do treści zadania Min Cost to Connect All Points i możliwości umieszczania rozwiązań: https://leetcode.com/problems/min-cost-to-connect-all-points/

–
Zadanie pokazuje algorytm Find And Union: https://youtu.be/jOqGMOGJQ1s?t=2036

–
Zadanie z LeetCode – platformy która zawiera zadania z interview / rozmów kwalifikacyjnych do Google, Facebook, Amazon: https://youtu.be/jOqGMOGJQ1s?t=17

–
Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109

–
Kod C++ programu "Min Cost to Connect All Points", który jest omówiony w powyższym filmie i który otrzymuje 100%

–

class Solution {
public:
int rep[1007];
int Find(int v) {
if (rep[v] != v)
rep[v] = Find(rep[v]);
return rep[v];
}
void Union(int u, int v) {
int a = Find(u);
int b = Find(v);
rep[a] = b;
}
int minCostConnectPoints(vector<vector<int>>& points) {
vector<pair<int, pair<int, int>>> kraw;
for (int i = 0; i < points.size(); ++i) {
for (int j = i + 1; j < points.size(); ++j) {
int d = abs(points[i][0] - points[j][0])
+ abs(points[i][1] - points[j][1]);
kraw.push_back({d, {i, j}});
}
}
sort(kraw.begin(), kraw.end());
for (int i = 0; i < points.size(); ++i)
rep[i] = i;
int wynik = 0;
for (int i = 0; i < kraw.size(); ++i) {
int d = kraw[i].first;
int u = kraw[i].second.first;
int v = kraw[i].second.second;
if (Find(u) != Find(v)) {
wynik += d;
Union(u, v);
}
}
return wynik;
}
};

–
Kod Python programu Min Cost to Connect All Points, który otrzymuje 100%:

class Solution:
rep = []
def Find(self, v):
if (self.rep[v] != v):
self.rep[v] = self.Find(self.rep[v])
return self.rep[v]
def Union(self, u, v):
a = self.Find(u)
b = self.Find(v)
self.rep[a] = b
def minCostConnectPoints(self, points: List[List[int]]) -> int:
self.rep = [i for i in range(len(points))]
kraw = []
for i in range(len(points)):
for j in range(i+1, len(points)):
d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
kraw.append([d, i, j])
kraw.sort()
wynik = 0
for d, u, v in kraw:
if (self.Find(u) != self.Find(v)):
wynik += d
self.Union(u, v)
return wynik