English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
Czy można by prosić o kilka małych testów?
Potwierdzam
12 random-ish max testów: [tu były trochę popsute testy, mniej popsute niżej]
Chyba nie są najmocniejsze, ale lepsze takie niż żadne. Ktoś coś?
Chyba nie są najmocniejsze, ale lepsze takie niż żadne. Ktoś coś?
https://codeforces.com/blog/entry/49769?#comment-337339
If you're reading this, you've been visited by the ghost of świstak past. Fast LCS implementations will come to you if you post "thank mr świstak" in this thread.
If you're reading this, you've been visited by the ghost of świstak past. Fast LCS implementations will come to you if you post "thank mr świstak" in this thread.
Potwierdzam :)
ditto
Potwierdzam jak wyżej.
Również potwierdzam testy Anadiego i Kamila.
Także potwierdzam testy Anadiego i Kamila.
Także potwierdzam testy Anadiego i Kamila.
Potwierdzam testy Anadiego i outy Kamila do paczki Wojtka.
Zauważę, że ciachanie obu na zmianę jest niepotrzebne. Można ciachać tylko jedno i taka sama złożoność.
Dzięki za szczegółową odpowiedź!
Googlamy prackę o ALCS https://www.sciencedirect.com/science/article/pii/S0166218X07002727 i przepisujemy krótki pseudokod, który w O(N*M) liczy dwuwymiarową tablicę ih[i][j]. Słuzy ona do tego, by liniowo odpowiadać na zapytanie: dla danych (i, j, k), znajdź LCS(A[0..i], B[j..k]). Sprowadza się to do policzenia wartości mniejszych/równych niż "j" w jakimś tam podprzedziale ih[i][...]. Zrozumienie tego pozwala użyć ekstra tablicy oraz sum prefiksowych, by dla danych (i, k) liniowo policzyć wynik dla wszystkich możliwych "j".
Podsumowując, robimy kwadratowy preprocessing, po czym dla zadanego prefiksu A i prefiksu B (które nazwijmy PA i PB), umiemy liniowo znaleźć wszystkie wyniki dla par (PA, sufiks(PB)).
=== Polecam w tym miejscu się zatrzymać i samemu skminić do końca, bo nie jest trudno. ===
.
.
.
Wczytujemy zapytania i odpowiadamy na nie offline. Robimy Divide&Conquer, na zmianę ciachając A i B na pół. Skupmy się na odpowiedzeniu na wszystkie zapytania, w których dany podprzedział A przechodzi przez środek słowa A. Nazwijmy dwie połówki słowa A jako AL i AR. Liczymy kwadratowo ALCS(reverse(AL), reverse(B)) oraz ALCS(AR, B), po czym odpowiadamy liniowo na każde zapytanie: pytamy te dwa alcs-y o odpowiednie prefiksy, dostajemy dwie tablice rozmiaru maksymalnie |B| i dają one nam wszystkie wyniki LCS(AL, prefiks B) i LCS(AR, sufiks B). Czyli udało nam się podzielić A na pół i możemy przeiterować się po tym, jaki prefiks podsłowa B będzie zmatchowany z lewą częścią podsłowa A.
Złożoność O(N^2 * log(N) + Q*N). Mój kod https://pastebin.com/iJB1TGmK
Podsumowując, robimy kwadratowy preprocessing, po czym dla zadanego prefiksu A i prefiksu B (które nazwijmy PA i PB), umiemy liniowo znaleźć wszystkie wyniki dla par (PA, sufiks(PB)).
=== Polecam w tym miejscu się zatrzymać i samemu skminić do końca, bo nie jest trudno. ===
.
.
.
Wczytujemy zapytania i odpowiadamy na nie offline. Robimy Divide&Conquer, na zmianę ciachając A i B na pół. Skupmy się na odpowiedzeniu na wszystkie zapytania, w których dany podprzedział A przechodzi przez środek słowa A. Nazwijmy dwie połówki słowa A jako AL i AR. Liczymy kwadratowo ALCS(reverse(AL), reverse(B)) oraz ALCS(AR, B), po czym odpowiadamy liniowo na każde zapytanie: pytamy te dwa alcs-y o odpowiednie prefiksy, dostajemy dwie tablice rozmiaru maksymalnie |B| i dają one nam wszystkie wyniki LCS(AL, prefiks B) i LCS(AR, sufiks B). Czyli udało nam się podzielić A na pół i możemy przeiterować się po tym, jaki prefiks podsłowa B będzie zmatchowany z lewą częścią podsłowa A.
Złożoność O(N^2 * log(N) + Q*N). Mój kod https://pastebin.com/iJB1TGmK
Okej, chyba rozumiem, czyli to jednak też bazuje na ograniczaniu najwyżej pomalowanego segmentu. Wydaje mi się, że nawet krążyłem nieświadomie przez jakiś czas wokół tego, ale ostatecznie się nie udało. Dzięki za rozjaśnienie. :D