Zapraszam do dzielenia się swoimi opiniami dotyczącymi takich krótkich zawodów i zadań! Poniżej będę sukcesywnie zamieszczał omówienia zadań.
Pangram
W zadaniu wystarczyło zliczyć wystąpienia każdej z 26 liter. Najprościej można to zrobić deklarując tablicę na 26 elementów. Na początku w każdej komórce zapisujemy wartość zero. Pierwsza komórka będzie przechowywała liczbę wystąpień litery a, druga litery b itd. Następnie przechodzimy przez wyraz znak po znaku i zwiększamy wartość w komórce odpowiadającej danej literze o 1. Ostatni etap to sprawdzenie czy wszystkie komórki mają wartość większą od 0 i czy są sobie równe.
Rozwiązanie wzorcowe: https://ideone.com/h2lRPb
Kule
Większość osób próbowała rozwiązać to zadanie wybierając po kolei najpierw pierwszą kulę, potem dobierając do niej drugą, a na końcu trzecią. Niestety takie rozwiązanie (3 zagnieżdżone pętle) ma złożoność O(n^3) co przy 8000 kul da wynik przekroczenia limitu czasu.
Wystarczy tylko delikatnie zmienić podejście, aby nasze rozwiązanie stało się zdecydowanie szybsze. W pierwszej kolejności wybieramy kulę środkową (najbardziej zewnętrzna pętla). Teraz mając środkową kulę szukamy w tablicy po jej lewej stronie lżejszej kuli na wyższym podeście (pierwsza wewnętrzna pętla), a następnie po jej prawej stronie szukamy cięższej kuli na niższym podeście (druga wewnętrzna pętla). Jeżeli istnieje wiele takich kul to oczywiście wybieramy najcięższe. Te dwie wewnętrzne pętle nie są zagnieżdżone tylko następują jedna po drugiej dzięki czemu wykonają one łącznie n sprawdzeń. Całkowita złożoność takiego rozwiązania wyniesie zatem O(n^2) co przy 8000 elementów jest akceptowalne.
Rozwiązanie wzorcowe: https://ideone.com/k1ZWAP
Chińska kompania reprezentacyjna
Dla każdego wzrostu zapisujemy pozycje na jakich występuje. Możemy do tego celu użyć tablicy wektorów. Indeks w pierwszym wymiarze odpowiada danemu wzrostowi. Następnie analizujemy kolejne wzrosty. Dla każdego z nich szukamy najdłuższego podciągu, w którym występuje maksymalnie k innych elementów. Można to zrobić liniowo przechodząc wektor dla danego wzrostu przy wykorzystaniu techniki dwóch wskaźników. Po znalezieniu maksymalnych podciągów dla każdego wzrostu wybieramy najdłuższy z nich. Całkowita złożoność rozwiązania to O(n). Opis ten jest dosyć skąpy, ale w połączeniu z analizą kodu myślę, że każdy zrozumie ideę. Jakby coś dalej było niejasne pytajcie.
Rozwiązanie wzorcowe: https://ideone.com/ZKbVh2