Runda 1: Kłopoty z ogrodem (rozwiązanie)

Autor zadania: Przemysław Pietrzkiewicz

Łatwo można sobie wyobrazić rozwiązanie sprawdzające wszystkie możliwe spójne fragmenty ogrodu pana Wincentego. Niestety, jest ich aż N^2, a policzenie liczby drzew w każdym z nich zajmie dodatkowy czas równy średnio N. Takie rozwiązanie jest zdecydowanie za wolne dla podanych limitów czasowych.

Wzorcowe rozwiązanie

1. Policz najdłuższy fragment ogrodu rozpoczynający się w polu nr 1 spełniający warunek na maksymalną liczbę drzew.

2. Następnie będziemy sprawdzać kolejnych kandydatów na optymalny fragment ogrodu. Zapamiętujemy sobie początek naszego aktualnego kandydata (oznaczmy go przez S) i koniec (oznaczmy przez E). Teraz dopóki zmienna E nie wyszła poza ogród pana Wincentego, przesuwamy ją w prawo. Za każdym razem, kiedy w wyniku takiego przesunięcia zwiększymy liczbę drzew w kandydacie do liczby nieakceptowalnej, przestajemy na moment przesuwać E, i przesuwamy S do czasu, kiedy liczba drzew spadnie do legalnej liczby.

3. Wynikiem będzie najdłuższy legalny kandydat, który wystąpił w czasie naszego "przesuwania" obu zmiennych.

Dlaczego to działa?

Zmienna E, oznaczająca koniec aktualnego kandydata przechodzi wszystkie pola w ogrodzie. W związku z tym na pewno w którymś momencie będzie się pokrywać z końcem poszukiwanego, optymalnego fragmentu ogrodu. Zmienna P musi być wtedy w miejscu, w którym poszukiwany fragment się zaczyna, lub wcześniej. Dzieje się tak dlatego, że nigdy nie wyrzucamy z naszego kandydata większej liczby drzew, niż to konieczne, aby uzyskać liczbę dopuszczaną przez limit drzew w zadaniu.

Zatem po koniecznym przesunięciu P do przodu, zmienne P i E będą pokrywać się z poszukiwanym rozwiązaniem optymalnym. Zatem nasz algorytm zawsze takie rozwiązanie znajduje.

W jakim czasie?

Zmienną E przesuwamy N razy, zmienną P co najwyżej N razy, nasz algorytm jest w takim razie liniowy w stosunku do długości ogrodu.