Strona poświęcona algorytmom

KÓŁKO MOI – 24 LISTOPADA 2018

Witajcie,

24.11.2018
Dziękuję za dzisiejszy pracę.
Każda kropla naszego umysłowego wysiłku przenosi nas na wyższy poziom.

A dziś tych kropli było dużo.
Naprawdę dostaliście dziś 2 mocne zadanie.

Dziękuję ponownie Mikołajowi Bulge za super zadanie, omówienie i podzielenie się swoimi doświadczeniami.
W najbliższy piątek Mikołaj instaluje każdemu ochotnikowi Linux-a!
Zachęcam

—–
Każde z zadań pokazało pomysły jakie wykorzystuje się na MOI/OI.
Każdy kto dokończy do niedzieli do 24:00 choć jedno z następujących zadań:
   * Balony
   * Agenci
oraz z pracy domowej:
   * Strictly Connected city
   * Disruption
otrzymuje w piątek nagrodę – zaczyna zajęcia od swojego ulubionego napoju.

Co to znaczy dokończyć?
 * screen na 100%
 * wysłany kod
 * krótki opis algorytmu, analiza złożoności


Szczególnie zachęcam do dokończenia Balonów / Disruption.
Udając się na studia za granicę / do grupy naukowej .,, – jeśi pokażecie że:
   – macie 100% z Międzynarodowej Olimpiady Licealistów już jako 15 latek
   – macie 100% z Platinium USACO
jesteście super gośćmi, wyróżniacie się z tłumu, jesteście pożądani.

To super cenne skalpy.

Pokzaujecie, że:
a. Wasz mózg to wyjątkowy okaz
b. Chce Wam się

Uwierzcie mi, że znalezienie łączne a. i b. na rynku pracowników jest mega trudne.

Każde z rozwiązanych zadań z USACO / CEOI / Codeforces – wpisujcie sobie do osobistego CV!

—–
Uwaga
Specjalna nagroda za odpowiedź oraz uzasadnienie na następujące pytanie do zadania
   Strongly Connected City

Pytanie:
1. Ze skrzyżowania A mogę dojść do każdego innego skrzyżowania.
2. Ze skrzyżowania B mogę dojść do każdego innego skrzyżowania.

Czy z 1. oraz 2. wynika, że z każdego skrzyżowania mogę dojść każdego innego skrzyżowania?

Czekam…
Daniel

 

25.11.2018

[Kółko MOI] – Dziękuję za dzisiejszą zabawę
Witajcie,

Dziękuje wszystkim którzy wysłali rozwiązania zadań (Agenci, Career,  Strongly Connected City, Balony).
Wszystkich pozostałych zachęcam do dokończenia.
Zapewniam że zabawa jest przednia – służę pomocą w przypadku kłopotów.

Czekam na pierwszego śmiałka w Disruption.

Czas mamy do końca dziś/niedziela do 24:00.

———-
W pracy domowej mamy proste zadanie na kolejkę monotoniczną.
Zadanie obowiązkowe dla każdego.

Zrobienie tego zadania oznacza, że nie zmarnowałeś czasu w piątek.
Jeśli są kłopoty – piszcie – podeślę rozwiązanie.

Kolejka monotoniczna często pojawia się w MOI/OI.
Pozwala nam utrzymać złożoność liniową przy przeglądaniu tablicy i porównywaniu kolejnych elementów z wcześniejszymi.
Zwyczajne przejście do tyłu powoduje złożoność kwadratową!


W pracy domowej ponownie pojawia się zadanie z Bash/Linux.
Gdziekolwiek będziecie w informatyce, musicie znać Linux-a.
A w przypadku MOI-a / OI-a mega się Wam przyda do sprawdzarek.

W załączeniu rozwiązanie zadania Linux-a z poprzedniego tygodnia (dodawanie liczb) – Eryka i Ignacego.
Załączam, żeby Wam ułatwić wejście w świat skryptów Linux-a.

Przypominam, Mikołaj obiecał chętnym zainstalować Linux-a w piątek .
Skorzystajcie!!!

Więcej na temat pisania kodu w Linux-ie:
https://linuxconfig.org/bash-scripting-tutorial

 

23.11.2018

Witajcie,

Zapraszam na jutro (8:00 – 10:30).
Przygotowujemy się do MOI-a – będzie dość trudne zadanie MOI-owe
+ Mikołaj ma dla nas mocniejsze zadanko
+ instalacja Linux-a razem z Mikołajem
8:00 rano – zaczynamy Kahoote-m + omówienie pracy domowej.

——-
Jak Wam się podoba kolejka monotoniczna?

Prawda, że prosta?
Prawda, że piękna?

Ale jest w tym element gdzie możemy pokazać naszą genialność.
Kolejka monotoniczna jest trudna do zauważenia.

Jak zauważyć, że w danym problemie nie wszystkie  elementy mają znaczenie.
Że dany problem ma tą właściwość, że jak mamy
10 2 8 5 3 4 1
to
2 i 3 są bez znaczenia?

Analiza problemu, zauważenie, pomysł!
Jak zobaczymy, że ważne są tylko elementy malejące – reszta banalna!
To jest klue!

Ale w zamian?
W zamian mamy złożoność liniową (u nas 10^5)!
A nie kwadratową (10^10)
Czyli zamiast 3 lat program sie wykonuje 3 godziny!

—–
W załączeniu mój kod.
Bardzo Was proszę – dokończcie zadanie.
Będzie mieć piękny skalp – rozwiązane zadanie z Międzynarodowej Olimpiady Licealistów!

Do jutra!
Daniel

 



Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *