Najdłuższy fragment ocen w limicie
W szkolnej platformie do analizy wyników próbnych matur uczeń przygotowuje funkcję najdluzszy(oceny, limit), która zwraca długość najdłuższego spójnego fragmentu listy ocen, którego suma nie przekracza limit. Oceny są liczbami całkowitymi od 0 do 100, a lista może mieć do 200 000 elementów. Nauczyciel uruchomił rozwiązanie oparte na dwóch zagnieżdżonych pętlach dla listy 200 000 ocen i limitu 1000; program przekroczył limit 1 s i został przerwany. Dla mniejszych danych wyniki były poprawne, ale dla listy [0, 0, 0] i limitu 0 funkcja zwróciła 1 zamiast 3. W repozytorium jest też gałąź, która dla limitu ujemnego zwraca 0, choć specyfikacja mówi, że limit może być ujemny tylko wtedy, gdy lista jest pusta. Zespół chce poprawić algorytm bez zmiany interfejsu funkcji, zachować czytelność kodu i dodać testy graniczne. W zadaniu nie chodzi o mikropotymalizację, lecz o wybór właściwej złożoności i poprawne traktowanie zer oraz wartości brzegowych.
1. Wyjaśnij, dlaczego rozwiązanie z dwiema pętlami przekracza limit czasu dla n=200000, i podaj złożoność, którą należy osiągnąć.
Read the worked answer
Liczba par (lewy, prawy) w dwóch pętlach jest rzędu n(n+1)/2. Dla n=200000 daje to około 20 miliardów iteracji. Nawet proste dodawanie w każdej iteracji przekracza 1 s, bo w praktyce wykonujemy dziesiątki miliardów operacji, a nie kilka milionów. Potrzebna jest złożoność O(n), ewentualnie O(n log n), a nie O(n^2). Ponieważ oceny są nieujemne, można użyć okna przesuwnego: utrzymujemy sumę fragmentu [lewy, prawy] i dopóki suma przekracza limit, przesuwamy lewy. Każdy indeks jest dodawany i odejmowany najwyżej raz, więc łączny czas jest liniowy. Ważne zastrzeżenie: dla liczb ujemnych to rozumowanie przestaje być poprawne, bo skrócenie okna nie zawsze zmniejsza sumę w przewidywalny sposób.
2. Zaproponuj poprawiony algorytm. Uwzględnij zera i ujemny limit; wskaż, gdzie w kodzie występuje błąd dla `[0,0,0]`, limit=0.
Read the worked answer
Szkic poprawnego rozwiązania dla listy nieujemnej:
lewy = 0
suma = 0
najlepszy = 0
for prawy in range(len(oceny)):
suma += oceny[prawy]
while lewy <= prawy and suma > limit:
suma -= oceny[lewy]
lewy += 1
najlepszy = max(najlepszy, prawy - lewy + 1)
return najlepszy
Dla [0,0,0] i limitu 0 suma nigdy nie jest większa od limitu, więc okno rośnie do trzech elementów i wynikiem jest 3. Typowy błąd to warunek suma >= limit zamiast suma > limit albo inicjalizacja najlepszy = 1; wtedy zera są przedwcześnie odcinane. Dla limitu ujemnego i niepustej listy wynik powinien wynosić 0, bo żaden niepusty fragment nie ma sumy niedodatniej, jeśli elementy są nieujemne. Dla pustej listy wynik również wynosi 0. Trzeba jawnie obsłużyć ten przypadek przed pętlą.
3. Podaj trzy testy graniczne i oczekiwane wyniki, które potwierdzą poprawkę.
Read the worked answer
Test 1: oceny=[0,0,0], limit=0, wynik 3. Sprawdza, czy zera nie są traktowane jak przekroczenie limitu. Test 2: oceny=[5], limit=4, wynik 0. Sprawdza przypadek, gdy pojedynczy element przekracza limit i okno musi zostać puste. Test 3: oceny=[2,3,1,2], limit=5, wynik 2, bo fragmenty [2,3], [3,1] i [1,2] mają sumę 5, a [2,3,1] ma 6. Warto dodać test oceny=[], limit=-1, wynik 0 oraz oceny=[1,1,1,1], limit=0, wynik 0. Testy powinny porównywać nie tylko wynik, ale też zachowanie dla dużej listy, np. 200 000 zer, aby potwierdzić, że algorytm nie zapętla się i działa liniowo.