Konkursy, zadanie nr 180
ostatnie wiadomości | regulamin | latex
| Autor | Zadanie / RozwiÄ…zanie |
pm12 postów: 493 |  2014-12-29 17:59:07Pytanie 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