English
Ostatnie posty
Potwierdzam
Potwierdzam
Potwierdzam
Potwierdzam
Potwierdzam
Potwierdzam.
Potwierdzam.
n + m <= 40
https://easyupload.io/mgjpck
https://easyupload.io/mgjpck
Zapraszam do porównania odpowiedzi.
https://easyupload.io/guz79b
https://easyupload.io/guz79b
No ogólne szacowanie, że to jest O(log n) istotnie nie było jakoś bardzo trudne, ale w kontekście dania tego zadania istotne było jednak doszacowanie ile dokładnie. Najwredniejszy test jaki mieliśmy wymagał przy odrobinie pecha około 30 iteracji, a dowód podobny do tego, który opisał Tomek po doliczeniu do końca dawał szacowanie, że około 100 iteracji daje już bliskie 0 prawdopodobieństwo porażki. Jak ktoś ma chwilę, to zachęcam do pokminienia jak udowodnić lepsze szacowanie/poszukać lepszego testa
BTW dobry trik implementacyjny z tą stałą od ostatniego update'a (chociaż while(clock) prostsze 😆)
BTW dobry trik implementacyjny z tą stałą od ostatniego update'a (chociaż while(clock) prostsze 😆)
e
Ja mam tak samo jak opisał Mateusz. Dowód na liczbę iteracji:
W danej iteracji każda składowa ma ≥ 50% szansy połączyć się z inną (dopóki da się). Nie są to zdarzenia niezależne dla różnych składowych. Ale wartość oczekiwana liczby tych, które się z niczym nie połączą to ≤ 50% z nich. Z nierówności Markowa wiemy, że szansa na to, że nie połączy się ≥ 75% z nich wynosi ≤ 50%/75% = 2/3.
Zatem z prawdopodobieństwem ≥ 1/3 liczba niedokończonych składowych maleje o czynnik ≤ 7/8. Więc średnio wystarczy O(log n) iteracji.
Ja robię tak, że kończę gdy przez 30 iteracji z rzędu nic się nie połączy. Liczba 30 tu reprezentuje log (liczba potrzebnych iteracji) + log(1/ε) = log log n + log (1/ε) + O(1) dla ε ≈ 2^(-20). To gwarantuje, że prawdopodobieństwo błędu wynosi ≤ ε, i całe rozwiązanie działa w czasie O(n(n+k)(log n + log (1/ε))).
W danej iteracji każda składowa ma ≥ 50% szansy połączyć się z inną (dopóki da się). Nie są to zdarzenia niezależne dla różnych składowych. Ale wartość oczekiwana liczby tych, które się z niczym nie połączą to ≤ 50% z nich. Z nierówności Markowa wiemy, że szansa na to, że nie połączy się ≥ 75% z nich wynosi ≤ 50%/75% = 2/3.
Zatem z prawdopodobieństwem ≥ 1/3 liczba niedokończonych składowych maleje o czynnik ≤ 7/8. Więc średnio wystarczy O(log n) iteracji.
Ja robię tak, że kończę gdy przez 30 iteracji z rzędu nic się nie połączy. Liczba 30 tu reprezentuje log (liczba potrzebnych iteracji) + log(1/ε) = log log n + log (1/ε) + O(1) dla ε ≈ 2^(-20). To gwarantuje, że prawdopodobieństwo błędu wynosi ≤ ε, i całe rozwiązanie działa w czasie O(n(n+k)(log n + log (1/ε))).
Obrazek z przejściami dla pieszych jest zbyt ogólny — wydaje mi się, że może pojawić się w przypadku jakichkolwiek problemów. Czy mogę uzyskać wskazówkę dotyczącą tego problemu?
Nie ma
Potwierdzam