Zadania

Tu pojawiać się będą komentarze do zadań, rozwiązania (przepisy! nie gotowe kody!), wyjaśnienia wątpliwości, porady i przestrogi. Zachęcam do dodawania własnych.

Uwagi ogólne

- Pod adresem http://www.speedyshare.com/982930565.html jest nowa testerka (do zad S włącznie), dodałem generator testów, narazie jest niedokończony, może się okazać, że coś nie działa itd, ale w najbliższym czasie powinno być OK //Maciek

Zanim wyślemy zadanie…

…dobrze zobaczyć, czy się kompiluje, i czy daje dobry wynik na teście przykładowym.
Ja [LD] znam bardzo niewielu ludzi, którzy takie programy potrafiliby napisać i przepchnąć "w ciemno".

Jeśli zadanie nie działa…

Jeśli przyczyną jest RTE - prawie na pewno zrobiliśmy coś, w wyniku czego wyjeżdżamy poza tablicę. Na przykład zwiększamy w pętli nie ten wskaźnik (for(int i=0; i<n; j++)), lub też zwyczajnie tablica jest za mała. Lub też np. chcemy porównać każdy element tablicy z poprzednim, zaczynając od pierwszego…

Możliwe też, że napisaliśmy scanf("%d",zmienna) zamiast scanf("%d",&zmienna).

Jeśli dostajemy TLE - po pierwsze, jaką mamy złożoność algorytmu? Na pewno dobrą? Najczęściej testerkę ciężko oszukać (choć wszystko jest możliwe) i algorytm kwadratowy nie przejdzie, jeśli dane mają wielkość 100 000.
Jeśli jesteśmy pewni, że to ten algorytm, trzeba sprawdzić, czy program gdzieś się po prostu nie wiesza, lub czy nie używamy cina/couta zamiast printfa i scanfa.

Odpowiedź ANS jest najpaskudniejsza, bo przyczyn może być multum. Czy dokładnie przeczytaliśmy treść? Czy program działa na teście przykładowym? Czy program działa, jeśli są dwa zestawy danych? Czy program działa na skrajnych (najmniejszych) danych?

Dobrze jest wpisać parę małych testów, żeby sprawdzić, czy wszystko jest w porządku. Przydatna może być testerka pana Macieja, żeby znaleźć test, na którym nasz program daje złą odpowiedź.

Jeśli taki test już mamy - cóż, żmudnie analizujemy, w którym momencie programu coś poszło nie tak. Klasyczną metodą jest wypisywanie wszystkich wyników pośrednich…

Tak, wiem, że to żmudne. Dobra wiadomość jest taka, że każdemu, kto będzie w życiu robił cokolwiek związanego z programowaniem (niekoniecznie algorytmicznego) umiejętność szukania błędów bardzo, bardzo się przyda.

Zadanie B

Złożoność musi być $O(\sqrt{N})$.

Algorytm

Dzielimy $N$ przez kolejne liczby naturalne, począwszy od $2$. Jeśli $N$ dzieli się przez jakąś liczbę, musi to być dzielnik pierwszy. Zapamiętujemy go.

Kończymy dzielenie na liczbie $\sqrt{N}$ - to, co pozostało z $N$, musi być jego ostatnim dzielnikiem pierwszym. Chyba, że jest równe $1$.

Zadanie C

Algorytm

Wczytujemy posortowaną tablicę, a następnie obsługujemy po jednym zapytaniu: wyszukujemy binarnie pierwsze, a potem ostatnie wystąpienie liczby (dwie różne procedury!).

Komentarze

Pytanie: Dlaczego nie można wyszukać pierwszego wystąpienia liczby, a następnie jechać po tablicy i sprawdzać, ile razy się powtórzą?
Odpowiedź: Pojedyncze zapytanie ma wtedy złożoność pesymistyczną $O(n)$, gdzie $n$ jest ilością liczb w tablicy. Na przykład, jeśli w tablicy pełnej samych trójek każemy wyszukać $3$…

Uwaga: W tym zadaniu trzeba dużo wczytywać i wypisywać - używanie cin/cout może być ryzykowne! Zalecam printf/scanf, mimo iż mają niemiłą składnię.

Zadanie E

Komentarze

Złożoność w tym zadaniu musi wynosić $O(n \log n)$. Nie ma innej opcji.

Wskazówka: Trzeba posortować obie tablice ślizgaczy (Jabby i Hana), a następnie zastanowić się, z kim sparować najsłabszy i najsilniejszy ślizgacz Hana.

Uwaga: W tym zadaniu trzeba dużo wczytywać - używanie cin/cout może być ryzykowne! Zalecam printf/scanf, mimo iż mają niemiłą składnię.

Zadanie F

Wskazówka: Skoro pan Duraj tłumaczył to na lekcji, pozwolę sobie to tutaj zamieścić. A więc doszlismy do wniosku na lekcji, iż mając szczyty P i Q, P<Q <=> x_P/y_P<x_Q/y_Q co jest równoważne x_P*y_Q<x_Q*y_P przy czym należy pamiętać, iż mogą leżeć na jednej linii, wtedy zgodnie z tym, co mówiliśmy na lekcji otrzymamy taką zasadę:
P<Q <=> x_P*y_Q<x_Q*y_P lub (x_P*y_Q=x_Q*y_P i y_P<y_Q)

Uwaga: W tym zadaniu iloczyn x*y może być większy niż 2³¹, a więc int go nie pomieści. Należy więc albo użyć long long przy porównaniu, lub oszczędzić sobie kombinowania i po prostu zadeklarować "iksy" i "igreki" jako long long

Zadanie H

Gdy macie ANS lub RTE:
1.Radzę dobrze się przyjrzeć funkcji odlacz: sprawdźcie jak działa dla pierwszego, środkowego, przedostatniego oraz ostatniego elementu. Dobre rozwiązanie powinno sobie poradzić też z usuwaniem elementów, których nie ma.
Sprawdźcie jeszcze zachowanie dla listy 1 oraz 2-elementowej.
2.Łączenie:
Mamy 4 przypadki:
*obie listy są puste
*druga jest pusta, pierwsza nie
*pierwsza jest pusta, druga nie
*obie nie są puste
Powinniśmy umieć wszystkie 4 obsłużyć.
3. Zestawy danych
Zwróćcie uwagę na zerowanie wskaźników na początki i końce 20 list
4. Szczególnie RTE:
Zwalnianie pamięci: dotyczy funkcji odłącz i zakoncz(zestaw).
Postaram się o jakieś chamskie testy.

Zadanie I

Złożoność w tym zadaniu musi wynosić $O(n+m)$ ($n$ - liczba rzek, $m$ - zapytań). Nie ma innej opcji.
//Luki92: To znaczy że każde zapytanie musi być obsłużone w czasie stałym! czyli O(1).

Zadanie L

Należy stworzyć strukturę element, która przechowuje wskaźnik na swoich obu synów, oraz wartość. W moim rozwiązaniu nie było rodzica.
Polecenie rysowania drzewa najlepiej zrobić rekurencyjnie (da się w 4 liniach): wypisujemy najpierw lewego syna, potem tyle plusów na którym jesteśmy poziomie*2, na końcu prawego syna. W związku z tym najlepiej napisać funkcję z dwoma parametrami: wskaźnik gdzie jesteśmy, oraz poziom.
Funkcje szukającą oraz dodawającą nowy element można połączyć w jedną, ze względu na ich bardzo podobną budowę.

Jak wczytywać dane, chyba nie muszę opisywać - najlepiej spojrzeć na własne kody zadań G lub H.

Pod koniec każdego zestawu należy czyścić pamięć(czy trzeba - to zadanie domowe dla klasy B HuMaNóW :-). Znowu się przyda rekurencja: usuwamy lewe i prawe poddrzewa-rekurencyjnie. potem usuwamy siebie. 3 linie kodu.

Porady na ANSY:
1) Trzeba sprawdzić co się dzieje przy pustym drzewie- jak nie dodamy żadnych elementów: przy wypisywaniu jak i poleceniu END.
2) Czy na pewno dobrze wypisujemy plusy
3) Czy jesteśmy takimi debilami i wypisujemy "TAK" zamiast "YES"?
4a) +1 :D
4b)A może powinieneś kopnąć komputer?

Ewentualne TLE to prawdopodobnie zapętlenie ze wskaźnikami.
RTE: Prawdopodobnie "wchodzimy" do wskaźnika NULL.

Zadanie Y1

Uwaga: liczba błędów w ustawieniu może przekroczyć zasięg typu int. Dobrze jest trzymać tę liczbę w zmiennej typu long long int.