English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
Równoważne będzie znalezienie najdłuższego niemalejącego podciągu sum prefiksowych, który zawiera pref[0] i pref[n] :)
Załóżmy, że będziemy to zadanie robić na odwrót. Zamiast szukać najmniejszej liczby połączeń, będziemy zaczynać ze wszystkimi połączeniami i zastanowimy się ile możemy usunąć. Żadna różnica, tylko wygodniej mi się tak myślało. Więc zrobimy sobie dp.
Dp[i] - największa ilość połączeń które można usunąć, z i-tym włącznie(!!). Więc zróbmy to najpierw w O(n^2). Chcemy policzyć dp[i], przeiterujmy się po wszystkich mniejszych j, stwierdzając, że tam będzie poprzednie cięcie. Ale musi też zostać spełniony warunek, że suma na przedziale od j+1 do i będzie nieujemna. Więc chcemy wybrać tylko takie j które to spełniają, i wziąć maksimum z ich wartości dp. W ten oto sposób mamy O(n^2). No to teraz wiemy już, że braliśmy wartość tylko z tych punktów, że spełniony był ten warunek o nieujemnej sumie. Jak go szybko sprawdzić. Niech pref to tablica sum prefiksowych. Żeby j oraz i mogły być kolejnymi cięciami, to pref[i] - pref[j] >= 0, czyli pref[i] >= pref[j]. Dobra, możemy zatem posortować sobie po wartości sumy prefiksowej rosnąco. Iterując się teraz w naszej nowej kolejności dalej liczymy to samo dp. Teraz nie musimy się martwić o to, że wyjdzie przedział z ujemną sumą. Jedynie chcemy brać teraz maximum po wszystkich dp które miały mniejszy indeks od i, a to da się w prosty sposób robić na jakimś drzewie przedziałowym maxów. W ten sposób dostajemy O(n*log(n)). Liczę, że da się coś zrozumieć :)
Dp[i] - największa ilość połączeń które można usunąć, z i-tym włącznie(!!). Więc zróbmy to najpierw w O(n^2). Chcemy policzyć dp[i], przeiterujmy się po wszystkich mniejszych j, stwierdzając, że tam będzie poprzednie cięcie. Ale musi też zostać spełniony warunek, że suma na przedziale od j+1 do i będzie nieujemna. Więc chcemy wybrać tylko takie j które to spełniają, i wziąć maksimum z ich wartości dp. W ten oto sposób mamy O(n^2). No to teraz wiemy już, że braliśmy wartość tylko z tych punktów, że spełniony był ten warunek o nieujemnej sumie. Jak go szybko sprawdzić. Niech pref to tablica sum prefiksowych. Żeby j oraz i mogły być kolejnymi cięciami, to pref[i] - pref[j] >= 0, czyli pref[i] >= pref[j]. Dobra, możemy zatem posortować sobie po wartości sumy prefiksowej rosnąco. Iterując się teraz w naszej nowej kolejności dalej liczymy to samo dp. Teraz nie musimy się martwić o to, że wyjdzie przedział z ujemną sumą. Jedynie chcemy brać teraz maximum po wszystkich dp które miały mniejszy indeks od i, a to da się w prosty sposób robić na jakimś drzewie przedziałowym maxów. W ten sposób dostajemy O(n*log(n)). Liczę, że da się coś zrozumieć :)
Jak rozwiązaliście zadanie?
Patrząc po rankingu nie było ono wcale takie trudne, ale mi się nie udało nawet bruta wykminić. :(
Patrząc po rankingu nie było ono wcale takie trudne, ale mi się nie udało nawet bruta wykminić. :(
Potwierdzam
Potwierdzam
Potwierdzam
U mnie działa 2,5s na laptopie, czyli koło 5s na sio.
1.2s na moim kompie, który jest około 3 razy szybszy niż SIO.
Swój czas też byś podał, skoro pytasz.
Swój czas też byś podał, skoro pytasz.
Na razie 15 minut xD
Potwierdzam. Ile działa Wam na big.in?
Potwierdzam
https://easyupload.io/dzgted -- 9 małych testów, po jednym od n=2 do n=10, zawsze do 300'000 wierzchołków i 100 zapytań.
Poniższe dwa inputy podaję z haszami md5 zamiast outów. Przypominam komendę: cat output | tr -d " \t\n\r" | md5sum
https://easyupload.io/klixvv -- n=100'000, q=100, moja md5sum to 0c019e6dd5a21a8ba6985c6fc021cd6c
https://easyupload.io/e3srrt -- n=q=300'000, moja md5sum to 6789e17890a5a72b2adfcd98b8da3a1c
Poniższe dwa inputy podaję z haszami md5 zamiast outów. Przypominam komendę: cat output | tr -d " \t\n\r" | md5sum
https://easyupload.io/klixvv -- n=100'000, q=100, moja md5sum to 0c019e6dd5a21a8ba6985c6fc021cd6c
https://easyupload.io/e3srrt -- n=q=300'000, moja md5sum to 6789e17890a5a72b2adfcd98b8da3a1c
Też potwierdzam :)
Potwierdzam