English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: [SIS] Rozwiązanie
Jaka struktura była tu najbardziej optymalna?
Grammar nazi.
Nie ma bardziej i mniej optymalnych, są optymalne lub nie. :-P
PS. polecam zapamiętać, bo to chyba ulubiona doczepka promotorów. (-:
Nie ma bardziej i mniej optymalnych, są optymalne lub nie. :-P
PS. polecam zapamiętać, bo to chyba ulubiona doczepka promotorów. (-:
No dobra, zapamiętam, w takim razie, jaka była optymalna?
Ja miałem drzewo przedziałowe do zjadania od aktualnej szprotki w lewo (szprotki w drzewie są wkładane po niemalejących wagach, z ewentualnymi dziurami, gdzie waga = 0) i set dla wygody, żeby szukać kolejnej większej szprotki.
Nie jest za wolno szukanie szprotki po szprotce?
Nie, za każdym razem zwiększa się waga szczupaka co najmniej dwukrtotnie.
Edit: Całe rozwiązanie. Oflline - wczytuję queries i biorę wszystkie dodane szprotki - te z wejścia i te, które będą dodawane (usuwanie pomijam). Sortuję je po wagach i wyznaczam pozycję w drzewie przedziałowym. Im większa waga, tym bardziej na prawo wyląduje szprotka.
2 struktury: drzewo przedziałowe i set. Set trzyma pary, waga szprotki i pozycja w drzewie. Drzewo przedziałowe umożliwia zmianę konkretnej pozycji (dodanie i usunięcie szprotki), wyznaczenie końca lewego przedziału, potrzebnego do zjedzenia odpowiedniej sumy wag, a także zablokowanie/odblokowanie całego przeddziału - co następuje w momencie zjedzenia podczas ataku i cofnięciu tego zjedzenia, po zakończeniu symulacji. Operacje blokowania nie kolidują z modyfikacją pozycji, w dodatku zawsze będą występowały w taki sposób, że raz zablokowany przedział, będzie blokowany kolejny raz w przedziale zawierającym go całkowicie (ponieważ kolejne szprotki będę musiał zjadać coraz bardziej w lewo). Dlatego też nie jest wymagane lazy propagation, a zwykłe zablokowanie przedziału i wyzerowanie sumy oraz ilości szprotek.
Operacje: dodawanie -> wstaw parę do seta i zmień pozycję w drzewie przedziałowym. Usuwanie - usuń ostatnią szprotkę o danej wadze z drzewa oraz z seta.
Atak:
Znajdź największą szprotkę, jaką może zjeść szczupak (set). Wyznacz ile musi zjeść, żeby być w stanie zabrać się za kolejną -> wyznacz ten przedział operacją get left opisaną powyżej. Po drodze zobacz, czy jedząc nie osiągnie swojej docelowej wagi. Zjedz wszystko, co powinieneś i z seta wyznacz kolejną szprotkę do zjedzenia. W tym momencie waga szczupaka zwiększyła się min dwukrotnie. Więc powtarzamy te kroki, aż dojedziemy do ostatniej szprotki lub osiągniemy żądaną wagę. Tych kroków będzie log n i każdy krok zajmuje log n, czyli całość operacji to O(log^2n). Zjedzenie przedziału na lewo, to po prostu zablokowanie go z operacji powyżej i odłożenie go na stos. Po zakończeniu symulacji ściągam kolejno przedziały ze stosu i je odblokowuję. Wartości w drzewie przywracam, gdy ściągnę ostatni przedział, który zablokował dany węzeł.
Edit: Całe rozwiązanie. Oflline - wczytuję queries i biorę wszystkie dodane szprotki - te z wejścia i te, które będą dodawane (usuwanie pomijam). Sortuję je po wagach i wyznaczam pozycję w drzewie przedziałowym. Im większa waga, tym bardziej na prawo wyląduje szprotka.
2 struktury: drzewo przedziałowe i set. Set trzyma pary, waga szprotki i pozycja w drzewie. Drzewo przedziałowe umożliwia zmianę konkretnej pozycji (dodanie i usunięcie szprotki), wyznaczenie końca lewego przedziału, potrzebnego do zjedzenia odpowiedniej sumy wag, a także zablokowanie/odblokowanie całego przeddziału - co następuje w momencie zjedzenia podczas ataku i cofnięciu tego zjedzenia, po zakończeniu symulacji. Operacje blokowania nie kolidują z modyfikacją pozycji, w dodatku zawsze będą występowały w taki sposób, że raz zablokowany przedział, będzie blokowany kolejny raz w przedziale zawierającym go całkowicie (ponieważ kolejne szprotki będę musiał zjadać coraz bardziej w lewo). Dlatego też nie jest wymagane lazy propagation, a zwykłe zablokowanie przedziału i wyzerowanie sumy oraz ilości szprotek.
Operacje: dodawanie -> wstaw parę do seta i zmień pozycję w drzewie przedziałowym. Usuwanie - usuń ostatnią szprotkę o danej wadze z drzewa oraz z seta.
Atak:
Znajdź największą szprotkę, jaką może zjeść szczupak (set). Wyznacz ile musi zjeść, żeby być w stanie zabrać się za kolejną -> wyznacz ten przedział operacją get left opisaną powyżej. Po drodze zobacz, czy jedząc nie osiągnie swojej docelowej wagi. Zjedz wszystko, co powinieneś i z seta wyznacz kolejną szprotkę do zjedzenia. W tym momencie waga szczupaka zwiększyła się min dwukrotnie. Więc powtarzamy te kroki, aż dojedziemy do ostatniej szprotki lub osiągniemy żądaną wagę. Tych kroków będzie log n i każdy krok zajmuje log n, czyli całość operacji to O(log^2n). Zjedzenie przedziału na lewo, to po prostu zablokowanie go z operacji powyżej i odłożenie go na stos. Po zakończeniu symulacji ściągam kolejno przedziały ze stosu i je odblokowuję. Wartości w drzewie przywracam, gdy ściągnę ostatni przedział, który zablokował dany węzeł.
Co masz na myśli przez "zabrać się za kolejną"? Jeśli najmniejszą większą od obecnej, to czemu masa szczupaka miała by się zwiększać dwukrotnie? np. szczupak ma masę X >> 10^2, a szprotki:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, X+10^2
? Dobrze rozumiem, że taki krok będzie tylko jeden?
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, X+10^2
? Dobrze rozumiem, że taki krok będzie tylko jeden?
Szczupak waży X i może zjeść szprotkę u, ale nie może v, u < X < v.
u,v to są kolejne szprotki.
Szczupak zjada od u w lewo tyle, żeby być w stanie zjeść v. Załóżmy, że wystarczyło mu zjedzenie tylko u. Teraz waży X+u i przeniesie się w kolejne najbliższe (na prawo) miejsce, gdzie będzie szprotka w > X+u (albo na koniec). Szczupak będzie znowu zjadał tyle, żeby zjeść w, czyli po kolejnym kroku będzie mógł ważyć > 2*(X+u) -> ważył X+u przed kolejnym krokiem, a po kolejnym kroku może zjeść w > X+u.
u,v to są kolejne szprotki.
Szczupak zjada od u w lewo tyle, żeby być w stanie zjeść v. Załóżmy, że wystarczyło mu zjedzenie tylko u. Teraz waży X+u i przeniesie się w kolejne najbliższe (na prawo) miejsce, gdzie będzie szprotka w > X+u (albo na koniec). Szczupak będzie znowu zjadał tyle, żeby zjeść w, czyli po kolejnym kroku będzie mógł ważyć > 2*(X+u) -> ważył X+u przed kolejnym krokiem, a po kolejnym kroku może zjeść w > X+u.