Przygotowanie XVIII Olimpiady Informatycznej


Dodałem treści zadań z wszystkich dni warsztatów. Są dostępne po kliknięciu małego przycisku Pliki u dołu tej strony. Zadania można wysyłać nadal na systemie Solve System [www.solve.edu.pl]

Prowadzący

Karol Pokorski
Jestem uczniem III Liceum im. Marynarki Wojennej RP w Gdyni. Od paru lat startuję w Olimpiadzie Informatycznej z paroma sukcesami. Rok temu prowadziłem (wydaje mi się, że udane) warsztaty z teorii gier oraz miniwykład o haszowaniu. Kontakt ze mną: moc.liamg|iksrokop.lorak#moc.liamg|iksrokop.lorak lub lp.ude.evlos|iksrokop#lp.ude.evlos|iksrokop.

Opis

Warsztaty potrwają 9 dni i będą stanowiły solidną dawkę wiedzy przydatnej do rozwiązywania zadań informatycznych. Każdego dnia skupimy się na jednym aspekcie (więcej w poddziale Program zajęć). Podczas każdego z dni prowadzony będzie wykład wprowadzający do danych algorytmów/struktur danych, podanych będzie kilka zastosowań do problemów, potem nastąpi chwila przerwy na kanapkę i regenerację sił, następnie praca rozwidla się w zależności od wyboru grupy, do której chce się przynależeć:
konkursowa - praca polega na samodzielnym rozwiązywaniu kilku zadań natury algorytmicznej, powiązanych bezpośrednio lub pośrednio z tematem wykładów. Czas pracy będzie ograniczony, a warunki będą symulowały warunki na Olimpiadzie. Dostępny będzie serwer wydruków, a zadania będą sprawdzane automatycznie (w specjalnym systemie zgłoszeniowym) na zestawie testów przykładowych.
warsztatowa - tak jak w grupie konkursowej rozdaję zadania (te same, co w grupie konkursowej) i wspólnie myślimy nad ich rozwiązaniem, konsultujemy pomysły, ja daję wskazówki. Jeśli starczy czasu, lub ktoś wie jak rozwiązać jakieś zadanie - rozwiązuje je na komputerze - w takiej sytuacji w przypadku problemów z kompilacją/poprawnością ja podchodzę i pomagam.
Po upływie czasu przeznaczonego na rozwiązywanie zadań - przechodzimy do omówienia zadań, na które zaproszone są obie grupy. Na omówieniu przedstawiam symulację wyników (progres najlepszych zawodników w grupie konkursowej w trakcie trwania zawodów). Zawodnicy, którzy poprawnie rozwiązali dane zadanie mogą zostać wytypowani (jeśli chcą) do omówienia zadania, w przeciwnym wypadku ja omawiam dane zadanie. Publikuję najlepsze wyniki z grupy konkursowej oraz wyróżniam pracowitych w grupie warsztatowej. Po warsztatach w czasie wolnym można poprawiać zadania, których się nie zrobiło/zrobiło błędnie. System oceni zgłoszenia automatycznie i poda pełne wyniki oceny natychmiast. Pracowici pod koniec warsztatów zostaną wyróżnieni.
Dwa dni będą wyglądać inaczej. Będzie luźniejszy i krótszy wykład, a zawody będą drużynowe. Będziecie rozwiązywać zadania w trzyosobowych drużynach. Wyniki będą pojawiać się na bieżąco a zawody będą dynamiczne według formuły z ACM ICPC. Wszelkie zasady będą dokładnie wyjaśnione jeszcze przed zawodami. Nie będzie wtedy podziału na grupę warsztatową i konkursową - będzie można tworzyć drużyny według własnego uznania (także mieszając grupy). W szczególnych przypadkach zasugeruję inny skład - nie będę jednak niczego narzucał na siłę.

Program zajęć

Zamierzam poruszyć następujące tematy:

  • algorytmy wykładnicze (wykorzystanie rekurencji, problem ośmiu hetmanów, maski bitowe, funkcja "widełkowa", zasada włączania i wyłączania, metoda meet-in-the-middle)
  • teoria liczb (NWD i NWD, sito Eratostenesa, rozkład na czynniki pierwsze, liczba dzielników liczby, rozszerzony algorytm Euklidesa, odwrotność modularna, małe twierdzenie Fermata, funkcja "fi" Eulera, logarytm dyskretny)
  • przeszukiwanie w głąb (algorytm DFS, sortowanie topologiczne, silnie spójne składowe, numeracja pre- i post-order, dwukolorowanie grafu, cykl Eulera, punkty artykulacji i mosty, dwuspójne składowe, 2-SAT)
  • algorytmy grafowe (alborytm BFS, algorytm Dijkstry, algorytm Bellmana-Forda, algorytm Floyda-Warshalla, najniższy wspólny przodek, drzewa, metoda odcinania liści, Find&Union, minimalne drzewo rozpinające)
  • teoria gier (twierdzenie Sprague-Grundy'ego, definicja pozycji wygrywających i przegrywających, nim-liczby, gra Nim oraz Staircase-Nim)
  • algorytmy tekstowe (funkcja prefiksowa, algorytm Knutha-Morrisa-Pratta, okresy, pierwiastki i szablony słów, lemat o okresowości, algorytm Manachera, drzewo TRIE, słownik podsłów bazowych)
  • programowanie dynamiczne (własność optymalnej podstruktury, problem wydawania reszty, problem plecakowy, najdłuższy wspólny podciąg, najdłuższy podciąg rosnący, odległość Levensteina)
  • przepływy i skojarzenia (definicja przepływu, metoda Forda-Fulkersona, algorytm Edmondsa-Karpa, algorytm Dinica, twierdzenie o maksymalnym przepływie i minimalnym przekroju, sposoby rozwiązywania zadań na przepływy, skojarzenia w grafach dwudzielnych, algorytm Hopcrofta-Karpa, turbo-matching)
  • struktury danych (drzewo potęgowe, drzewo przedziałowe, drzewo licznikowe, kopiec i stos)
  • technikalia (preprocessing, haszowanie, algorytmy i struktury danych działające w czasie pierwiastkowym, wykorzystanie biblioteki STL, wyszukiwanie binarne)

Spodziewam się, że nie wszystko nam się uda - przed warsztatami zostanie zrobiona ankieta, w której będziecie mogli wybrać co ma priorytet. Przeanalizuję to wszystko i te tematy będą analizowane w pierwszej kolejności. Poziom warsztatów będzie dostosowany do waszych wyników i opinii.

Wymagania

  • znajomość pojęcia złożoności obliczeniowej i pamięciowej,
  • biegła umiejętność programowania w co najmniej jednym języku programowania z podanych: C, C++, Pascal (z małym wskazaniem na C++, ale dowolny z tych języków jest akceptowalny),
  • chęci do zdobycia wiedzy i umiejętności przez pracę i zadawanie pytań,
  • umiejętność przyznania się do niewiedzy,
  • znajomość zasad panujących na Olimpiadzie Informatycznej, sposobu oceniania rozwiązań i typu zadań (to zostanie jeszcze powtórzone na pierwszych zajęciach, ale proszę się zaznajomić).

Zadania kwalifikacyjne

Kwalifikacja odbywać się będzie przez automatyczny system zgłoszeniowy (znajduje się on na stronie: [http://www.solve.edu.pl]). Należy się zarejestrować używając swoich prawdziwych danych. Po zalogowaniu należy wybrać konkurs o identyfikatorze WWW-Qual. Do rozwiązania są cztery dość łatwe zadania (na warsztatach spodziewajcie się nieco trudniejszych). Oceniana jest poprawność i efektywność metody użytej do rozwiązania zadania. Każde zadanie oceniane jest w skali 0-100 tak jak na Olimpiadzie Informatycznej. Wybór języka programowania jest częścią rozwiązania zadania. Wyniki dostępne są natychmiast po wysłaniu (w przypadku ich braku proszę o kontakt). Minimum kwalifikacyjne ustalam na 150 punktów (na 400 możliwych). Zadania pojawią się w systemie o północy 1. maja, system zamknie możliwość wysyłania zgłoszeń o północy 16. lipca.

Dodatkowe informacje

Dobrze byłoby mieć własny komputer. Ostatnio były dostępne komputery, ale jednak zawsze wygodniej pracuje się na własnych…

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License