logowanie

matematyka » forum » forum zadaniowe - zadania różne » zadanie

Konkursy, zadanie nr 180

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / 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





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj