Konkursy, zadanie nr 180
ostatnie wiadomości | regulamin | latex
Autor | Zadanie / Rozwiązanie |
pm12 postów: 493 | 2014-12-29 17:59:07 Pytanie kieruję do p. Śliwińskiego. Jak należało rozwiązać zadanie "Ciąg arytmetyczny II" z 20. rundy Algoligi ? |
magda95 postów: 120 | 2015-03-14 22:13:41 Może nie nazywam się Śliwiński, ale znam rozwiązanie, więc myślę że mogę odpowiedzieć Dla każdego testu rozważamy wartości różnicy pomiędzy wyrazami ciągu od -1000 do +1000. Dla każdej takiej różnicy (nazwijmy ją r) szukamy najdłuższego podciągu o róznicy r. Dokładniej, dla każdego kolejnego wyrazu (załóżmy że ma wartość a) sprawdzamy czy element o wartości (a-r) wystąpił wcześniej w tym ciągu - jesli tak, to długość ciągu kończącego się wyrazem a jest o 1 większa od ciągu kończącego się na (a-r). Złożoność rozwiązania - dla każdego testu mamy O(2000*n)~O(n^2) |
strony: 1 |
Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj