Spotkanie pośrodku
Skracanie wykładnika przez podział przestrzeni wyszukiwania
Spotkanie pośrodku to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Gdy brute force działa zbyt wolno
Niektóre problemy mają N rzędu 40, a sprawdzanie wszystkich 2^N podzbiorów jest beznadziejnie wolne. Technika meet in the middle pozwala rozwiązać takie zadania o średnim rozmiarze. 🤝
Główna idea
Należy podzielić dane wejściowe na dwie połówki. Każdą połówkę rozwiązujemy metodą brute force, a następnie sprytnie łączymy oba częściowe wyniki.
Zmniejszenie wykładnika o połowę
Dwie połówki rozmiaru N/2 wymagają po 2^(N/2) operacji zamiast łącznie 2^N. To zmniejszenie do pierwiastka kwadratowego zamienia 2^40 w przyjazne 2^20.
Klasyczny cel: subset sum
Należy sprawdzić, czy jakiś podzbiór ma sumę równą celowi T. Problem subset sum dla N bliskiego 40 to podręcznikowy przykład techniki meet in the middle.
Wyliczanie pierwszej połówki
Należy wypisać każdą sumę podzbioru z lewej połówki i ją zapisać. Dla N/2 elementów daje to zaledwie 2^(N/2) sum.
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []Wyliczanie drugiej połówki
To samo należy zrobić dla prawej połówki, tworząc pełną listę jej sum podzbiorów. Otrzymujemy dwie listy o możliwym do obsłużenia rozmiarze.
Łączenie za pomocą wyszukiwania
Dla każdej prawej sumy r potrzebna jest lewa suma równa T minus r. Zbiór lub posortowana lista pozwala szybko sprawdzić jej obecność.
need = T - r
found = need in left_setDwa sposoby dopasowywania
Dla dokładnych celów należy użyć zbioru haszującego. Aby liczyć rozwiązania lub znajdować sumy najbliższe celowi, należy posortować jedną połówkę i wykonać w niej wyszukiwanie binarne.
Koszt czasowy
Całkowity nakład pracy wynosi około 2^(N/2) pomnożone przez czynnik logarytmiczny związany z wyszukiwaniem lub sortowaniem. To właśnie ta złożoność sprawia, że N bliskie 40 staje się osiągalne.
Pamięć jako kompromis
Przechowywana jest cała jedna połówka, więc zużycie pamięci rośnie do 2^(N/2). Należy przechowywać tylko to, co konieczne, aby zmieścić się w limicie.
Gdzie jeszcze się sprawdza
Poza problemem subset sum technikę tę można stosować do znajdowania maksymalnego podzbioru poniżej limitu, liczenia par i problemów w stylu logarytmu dyskretnego. Dobrze wykorzystuje przejrzysty podział.
Szybkie sprawdzenie
Stosują Państwo meet in the middle do problemu podzbiorowego z N elementami. Jaki jest przybliżony koszt czasowy?
Podsumowanie
Należy podzielić dane na dwie połówki, rozwiązać każdą metodą brute force, a następnie dopasować lewe i prawe sumy. W zamian za niewielkie zużycie pamięci otrzymuje się ogromne przyspieszenie. 🚀
Często zadawane pytania
Czy lekcja „Spotkanie pośrodku” jest bezpłatna?
Tak — pełny tekst „Spotkanie pośrodku” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Spotkanie pośrodku”?
Skracanie wykładnika przez podział przestrzeni wyszukiwania Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Spotkanie pośrodku”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Stany wygrywające i przegrywające w grach
- Nim i liczba Grundy’ego
- Spotkanie pośrodku
- Szybkie debugowanie: testy obciążeniowe i triage