Czy istnieje szybsze rozwiązanie problemu Google Code Jam Great Wall

Rozważ następujące pytanie Google Code Jam w rundzie 1C :

Wielki Mur Chiński zaczyna się od nieskończonej linii, której wysokość we wszystkich lokalizacjach wynosi .$0$

Pewną liczbę pokoleń , N ≤ 1000 , atakują murze ściany według następujących parametrów - początkowego dnia, D , wytrzymałość początkową S , rozpoczęcie zachód współrzędnych, W i początek wschód współrzędnych, E . Ten pierwszy atak występuje na dzień D , w zakresie [ W , e ] , przy wytrzymałości S . Jeśli w [ W , E ] jest jakaś część Wielkiego Muru , która ma wysokość < $N$$N \le 1000$$D$$S$$W$$E$$D$$[W,E]$$S$$[W,E]$$< S$, atak się powiódł, a pod koniec dnia ściana zostanie zbudowana w taki sposób, że każdy jej fragment w obrębie wysokości < S byłby wówczas na wysokości S (lub większej, jeśli jakiś inny atak ten dzień uderzył w ten sam segment siłą S ′ > S )$[W,E]$$< S$$S$$S' > S$

Każde plemię wykona do ataków przed wycofaniem się, a każdy atak zostanie określony iteracyjnie od poprzedniego. Każde plemię ma trochę δ D , δ X i δ S, które określają ich kolejność ataków: Będzie czekać δ D ≥ $1000$$\delta_D$$\delta_X$$\delta_S$$\delta_D \ge 1$ dni między atakami, będą przesuwać swój zasięg ataku jednostek za każdy atak (ujemny = zachodni, dodatni = wschód), chociaż rozmiar zasięgu pozostanie taki sam, a ich siła również wzrośnie / zmniejszy się o stałą wartość po każdym ataku.$\delta_X$

Celem problemu jest, przy pełnym opisie atakujących plemion, określenie, ile ich ataków odniesie sukces.

Udało mi się napisać kod działającego rozwiązania, które działa w około 20 sekund: Wydaje mi się, że rozwiązanie, które wdrożyłem, zajmuje czas , gdzie A = całkowita liczba ataków w symulacji (maks. 1000000 ), a X = całkowita liczba unikalnych punktów krawędzi w zakresach ataku (maks. 2000000 ).$O(A\log A + (A+X)\log X)$$A =$$1000000$$X =$$2000000$

Na wysokim poziomie moje rozwiązanie:

• Wczytuje wszystkie informacje Plemienia
• Oblicza wszystkie unikalne współrzędne dla zakresów ataku - O ( A $X$$O(A)$
• Reprezentuje ścianę jako leniwie zaktualizowane drzewo binarne w zakresach które śledzi minimalne wartości wysokości. Liść to rozpiętość dwóch współrzędnych X bez żadnych pośrednich wartości, a wszystkie węzły nadrzędne reprezentują ciągły przedział objęty przez ich dzieci. - O ( X log X $X$$X$$O(X \log X)$
• Generuje wszystkie ataki, które wykona każde plemię, i sortuje je według dnia - $O(A \log A)$
• Dla każdego ataku sprawdź, czy się powiedzie ( czas kwerendy w ). Gdy dzień się zmieni, przejrzyj wszystkie nieprzetworzone udane ataki i odpowiednio zaktualizuj ścianę ( rejestruj czas aktualizacji X dla każdego ataku). - O ( A log $\log X$$\log X$$O(A\log X)$

Moje pytanie jest następujące: Czy istnieje sposób to zrobić lepiej niż $O(A\log A + (A+X)\log X)$ ? Być może jest jakiś strategiczny sposób na wykorzystanie liniowej natury kolejnych ataków Plemion? 20 sekund wydaje się zbyt długie na zamierzone rozwiązanie (choć Java może być za to winna).

Oczywistym miejscem do poprawy jest ten krok:

Generuje wszystkie ataki, które wykona każde plemię, i sortuje je według dnia - $O(A\log A)$

Wiemy, że plemiona będą atakować od określonego dnia, w regularnych odstępach czasu. Oznacza to, że powinniśmy zasadniczo scalić wiele wstępnie posortowanych list. Również opis problemu mówi nam, że nigdy nie będzie więcej niż 1000 plemion (tj. 1000 list do scalenia); niewielka liczba w porównaniu z 1 000 000 maksymalnych ataków! W zależności od względnych czasów implementacji przełączenie może skrócić czas przetwarzania o połowę.

To naprawdę wszystko, co mogę zasugerować, aby zoptymalizować teoretyczną złożoność, ale nie mam dowodów, że byłoby to optymalne po tej zmianie.

Sam rozwiązałem zagadkę, ale użyłem znacznie głupszej reprezentacji ściany: binarne drzewo wyszukiwania (a std::mapdokładniej C ++ ) przechowujące miejsca, w których zmienia się wysokość ściany. Dzięki temu mogłem dodawać i usuwać węzły zgodnie z wymaganiami (tj. Jeśli skomplikowana sekcja została poddana dużemu, przytłaczającemu atakowi lub dotkniętym wielokrotnym atakom o tej samej sile, liczba węzłów znacznie by się zmniejszyła). To rozwiązało duże wejście w 3,9 sekundy (na moim laptopie programistycznym o średniej specyfikacji). Podejrzewam, że istnieje kilka powodów poprawy:

• Jak wskazałeś, boksowanie i rozpakowywanie może być kosztowne, ale kontenery oparte na szablonach C ++ całkowicie tego unikają.
• Chociaż zastosowana przeze mnie reprezentacja ściany jest teoretycznie gorsza, w zdecydowanej większości przypadków możliwość dynamicznego zmniejszenia liczby węzłów sprawiła, że ​​jest ona superszybka (większość przypadków testowych osiągnęła maksimum przy węzłach poniżej 1k, a wszystkie oprócz 2 były poniżej 10k) . W rzeczywistości jedynym przypadkiem, który zajmował znaczący czas, była # 7, która zdaje się testować wiele nieprzecinających się zakresów.
• Nie użyłem wstępnego przetwarzania (etapy są określane przez śledzenie, kiedy każde plemię zaatakuje dalej i poszukiwanie najniższej wspólnej w każdej turze). Znowu jest to teoretycznie gorsze, ale w większości przypadków podejrzewam, że niższy koszt ogólny oznacza, że ​​był on szybszy (przetestuję to i wrócę do ciebie). Aktualizacja : Dodałem kolejkę priorytetową dla ataków, podobną do metody opisanej powyżej (chociaż zamiast tworzenia dużej tablicy obliczałem ją w locie) i zobaczyłem, że czas dla dużych danych wejściowych skrócił się do 3,0 sekund.

Krótko mówiąc, chociaż myślę, że twój algorytm jest prawie optymalny w ogólnym przypadku, istnieje kilka sposobów na przyspieszenie go dla typowych danych wejściowych .

Następujące pytanie zostało usunięte z pytania, ponieważ jest to odpowiedź.

Patrząc na inne dyskusje i udane rozwiązania, wydaje się wskazywać, że opisane przeze mnie rozwiązanie jest prawie oczekiwanym algorytmem. Spowolnienie w moim rozwiązaniu wynika prawdopodobnie z leniwego korzystania z auto-boxingu i struktury drzewa opartej na wskaźnikach, a nie na tablicy - podejrzewam więc, że jeśli rozwiązanie istnieje, prawdopodobnie nie jest to całość o wiele lepiej niż tutaj.

Rozwiązanie można znaleźć tutaj . Jest bardzo podobny do tego, co tu zamieściłem; dlatego jestem o wiele bardziej skłonny wierzyć, że bardziej wydajne rozwiązanie nie istnieje.