12 Urodziny Polskiego Spoja

macbon · Mar '19

12 Urodziny Polskiego Spoja

Serdecznie zapraszam wszystkich użytkowników polskiego Spoja do udziału w konkursie zorganizowanym z okazji jego 12 urodzin. Będą to odrobinę inne zawody niż te, które były rozgrywane na polskim Spoju do tej pory. Zmiany są następujące:

Liczba zadań zostanie zmniejszona do 3-4
Zadania będą różnie punktowane
Czas na rozwiązanie zadań wyniesie tylko 1h 40min 41s

Skąd te zmiany? Po pierwsze przygotowanie 3-4 zadań zajmuje zdecydowanie mniej czasu niż 10-20, co daje szanse na częstsze rozgrywanie konkursów niż raz na pół roku. Po drugie uważam, że warto podnieść wagę czasu w zawodach. W obecnej wersji nie będzie już możliwości zrobienia sobie dłuższej przerwy na przemyślenie zadań. Oczywiście postaram się tak dobrać poziom trudności, aby ich rozwiązanie w danym czasie było realne.

Konkurs rozpocznie się w poniedziałek, 25 marca 2019 o godzinie 20:00:00 i potrwa do 21:40:41, czyli godziny kiedy Marcin Sasinowski opublikował 12 lat temu newsa o powołaniu do życia polskiego Spoja.

Do zobaczenia!

macbon · Mar '19

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/h2lRPb25

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/k1ZWAP17

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/ZKbVh217

12 Urodziny Polskiego Spoja