Kod: Zaznacz cały
https://szkopul.edu.pl/problemset/problem/QpsiPJisfHa1XkxhnFe27aSH/site/?key=statement[Algorytmy] Zająknięcia [B] PA 2010
-
matexik
- Użytkownik
- Posty: 15
- Rejestracja: 8 kwie 2017, o 10:14
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 3 razy
[Algorytmy] Zająknięcia [B] PA 2010
Mam problem z takim zadaniem: . Jak można w rozsądnym czasie rozwiązać ten problem?
Ostatnio zmieniony 9 paź 2017, o 03:26 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Afish
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
Re: [Algorytmy] Zająknięcia [B] PA 2010
Da się łatwo w sześciennym, dla każdego \(\displaystyle{ i}\) robimy dwa ciągi rozcinając wejście w indeksie \(\displaystyle{ i}\). Następnie dla tych dwóch ciągów obliczamy długość najdłuższego wspólnego podciągu i z tego obliczamy ostateczny wynik.
Mam wrażenie, że dałoby się to przyspieszyć tak, aby nie liczyć przy zmianie \(\displaystyle{ i}\) całych tablic od nowa, ale jeszcze nie wiem jak.
Poza tym moją pierwszą myślą było wyszukiwanie binarne. Gdybyśmy potrafili odpowiedzieć w czasie kwadratowym, czy da się zrobić zająknięcie długości \(\displaystyle{ k}\), to pozostaje tylko binarnie znaleźć wynik, ale nie wiem jeszcze, jak to sprawdzić.
Mam wrażenie, że dałoby się to przyspieszyć tak, aby nie liczyć przy zmianie \(\displaystyle{ i}\) całych tablic od nowa, ale jeszcze nie wiem jak.
Poza tym moją pierwszą myślą było wyszukiwanie binarne. Gdybyśmy potrafili odpowiedzieć w czasie kwadratowym, czy da się zrobić zająknięcie długości \(\displaystyle{ k}\), to pozostaje tylko binarnie znaleźć wynik, ale nie wiem jeszcze, jak to sprawdzić.