Strona poświęcona algorytmom

Kółko MOI – 17 listopada 2018

Kochani,

2018.11.10
Zapraszam na jutrzejsze/sobotnie kółko MOI.
8:00 – 10:30, sala 217, Staszic.

——
8:00 – quiz
8:10 – omówienie pracy domowej
8:30 – 10:30
* zadanko proste – nowy algorytm
* zadanko trudniejsze (Mikołaj Bulge)
* jak sprawdzać masowo zadania (Mikołaj Bulge) – rozwinięcie dzisiejszego wykładu Kuby

——–
Dziś poznaliśmy najważniejszy algorytm grafowy – DFS.

Tuż przed zajęciami rozmawiałem z osoba która pracuje w Amazon/AWS (największy dostawca chmury na świecie).
W Polsce piszą kod i mają również R&D (Research & Development).

Programista zatrudniany przez AWS/Polska musi przejść proste testy algorytmiczne.
Musi pokazać, że umie myśleć, umie wykorzystać DFS, umie ogarnąć złożoność, ….

Każdy z nas kto będzie w finale MOI-a, kto będzie w finale OI-a będzie wiedział dużo więcej niż to co wymaga AWS czy Google od programistów.

My celujemy w dużo bardziej ambitne projekty niż programowanie.

Celujemy w R&D (Research & Development), celujemy w bycie tymi którzy zmieniają świat.
Celujemy w bycie tymi którzy znajdą lek na raka nie w milion lat ale w 1 rok!

Ale zawsze możemy zejść z drogi na Rysy i po prostu zostać w schronisku w Morskim Oku.
Odwrotnie się nie da.

———–
Dlatego każdy z Was musi zrobić dzisiejsze zadanie.

Dziękuje tym którzy zrobili je na zajęciach.
Bardzo proszę o dokończenie zadania wszystkich pozostałych.

———–
Dlatego każdy z Was musi zrobić dzisiejsze zadanie.

Dziękuje tym którzy zrobili je na zajęciach.
Bardzo proszę o dokończenie zadania wszystkich pozostałych.

W załączeniu mój kod na 100%.

——-
Zachęcam do obejrzenia poniższego filmu który tłumaczy DFS i pokazuje także standardowy kod DFS:
https://youtu.be/qH-mHxkoK0Q

Zrozumcie dogłębnie idę.
Zrozumcie jak działa.
Zrozumcie ograniczenia.

Wtedy będziecie mogli go zakwestionować, wtedy będzie mogli go zmienić, wtedy będzie mogli wymyślić coś lepszego/szybszego.

 

10.11.2018

Dziękuję za dzisiejsza zabawę.

Dziękuje Mikołajowi za super zadanie.
Ale przede wielkie podziękowanie za omówienie sprawdzarki i kurs pisania w Linux-ie.

Mikołaj zgodził się przyjść do nas za tydzień w sobotę i pomóc zainstalować Linux-a tym którzy go NIE mają.
To dla nas wielka szansa – skorzystajmy z niej!

——-
W pracy domowej mocne skupienie się na DFS (zadania od 1 do 3).
DFS musi być częścią naszego DNA.

Zadania na DFS są bardzo ćwiczeniowe.
Każdy z nas musi je zrobić.

——
Zachęcam do dokończenia dzisiejszego zadania Logistyka.

 

2018.11.18

Dziękuję tym którzy wysłali pierwszą cześć pracy domowej.
Super.
Dziękuję za walkę, za chęć zrozumienia DFS-a.

Dziękuję tym którzy wysłali Logistykę.
To mega ważne zadanie dla tych którzy chcą walczyć mocno na finale.
Robienie takich zadań da Wam gigantyczną przewagę w III etapie.

Przypominam – mamy czas na Logistykę do niedzieli 24:00 z pełną nagrodą.

——–
Dziękuję Ignacemu Gębusiowi i Piotrowi Pływaczowi za podesłane pakiety testowe do Jabłek i Gruszek.
Całość pakietów testowych jest na stronie:
http://algoorithms.pl/testy-do-zadan-moi-2018-2019/

W komentarzach na stronie dodawajcie linki do własnych testów jałbkowo-gruszkowych.

——-
Pod linkiem:
http://gurago.pl/m2018/xd.zip
jest pakiet Mikołaja Bulge zawierający skrypty Linux:
      ocen.sh – automatyczną sprawdzarkę naszych rozwiązań – mega użyteczne narzędzie
ocen2.sh – automatyczną sprawdzarkę naszych rozwiązań względem cudzych rozwiązań

Odnośniki w skryptach
a – skompilowany program wzorcowy w C++
b – skompilowany brut w C++

Mikołaj – jeszcze raz dzięki!

——–
Zadania DFS1 / DFS2 z pracy domowej mają za zadanie pomóc nam zrozumieć DFS-a.
Jeśli zrozumiecie algorytm to:
a. zawsze napiszecie ten algorytm – nawet za 10 lat
b. będziecie w stanie zakwestionować ten algorytm i napisać lepszy

Najbardziej mi zależy na punkcie b.
Byście kwestionowali to co dostajecie.
Byście zaprzeczali podawanym Wam regułom.
Byście wymyślali lepsze podejścia – nawet jeśli są to podejścia tylko dla szczególnych przypadków.

Ale żeby zaprzeczyć, trzeba zrozumieć.
Gdy zrozumiesz możesz zobaczyć słaby punkt, możesz poprawić.

———
Dochodzą nam 4 zadania.
Zad 5
Ciekawsze zadania z USACO
Każdy kto zrobi to zadanie – również dodatkowa nagroda – jak za Logistyke

Zad 6 – podzbiory
Zadanie dla każdego – konieczne do zrobienia

Zad 7
Przetestowanie jabłek i gruszek dla testów
http://algoorithms.pl/testy-do-zadan-moi-2018-2019/

Zad 8
Mały program w Linux-ie (bash).
Ma nam pomóc wejść w świat Linux-a

2018.11.22
Witajcie,

Zapraszam serdecznie na jutrzejsze kółko.

Jutro super czaderskie zadanie.
     a. Pomysł, pomysł, pomysł
b. I mało kodu.

Przy okazji poznamy nowy ważny trik.
Często spotykany na MOI-u / OI-u.

Zadanie z dużej Olimpiady Międzynarodowej (Licealistów).

Ale jak zobaczycie, zadanie okaże się banalne!
Każdy z Was stwierdzi, że na Olimpiadach Międzynarodowych (licealistów) dają proste rzeczy.

A jeśli będziemy robić z OI-a – a co gorsza Olimpiady Międzynarodowe, to oznacza, że na MOI-u zaszalejemy!

Uwaga!
Kahoota o 15:15 będzie miał istotne pytania w kontekście zadania!!!

Zapraszam jutro na ekscytująca podróż w świat fascynującej algorytmiki….

——–
Od razu zapraszam na sobotę.
Znów swoje show zrobi Mikołaj Bulge:
* Instalacja Linux-a dla chętnych
* Czaderskie zadanie

——–
Dziękuję Piotrkowi Pływaczowi który potwierdził testy Ignacego do zadania z jabłkami i gruszkami z MOI-a:
      http://algoorithms.pl/testy-do-zadan-moi-2018-2019/

Przypominam, że w pracy domowej jest wrzucenie testów do jabłek i gruszek.
Można do mnie, można przez stronę:
http://algoorithms.pl/testy-do-zadan-moi-2018-2019/

———–
Kto zrobił już test z MOI-a?
Pamiętajcie, można za niego uzyskać 100 punktów!

———-
Piszcie jakie macie drużyny do MOI-a…

—-
Praca domowa – podpowiedzi
DFS1 / DFS2 – musimy wczuć sie w DFS-a.
Opłaci się.

Strongly connected city – DFS

Jabłka i gruszki – nie mogę podpowiedzieć…

Podzbiory – 2 pętle.

—-
Praca domowa – całość
Wszystkie zadania – nagroda specjalna, jedno mniej – nagroda główna, pojedyncze zadania – nagrody zwykłe

Zadanie 1 – DFS1
Zadanie tylko w załączeniu
Warunek zaliczenia:
* Podanie kolejności wierzchołków

Zadanie 2 – DFS2
Zadanie tylko w załączeniu
Warunek zaliczenia:
* Podanie tablicy jak w zadaniu

Zadanie 3 – Strongly connected city
http://codeforces.com/problemset/problem/475/B
* Zaliczone testy na stronie
* Krótki opis algorytmu
* analiza złożoności, kod na 100%

Zadanie 4 – Testy do zadania jabłka i gruszki
W
ygeneruj 1000 testów w formacie
abcd1.in / abcd1.out
abcd2.in / abcd2.out

abcd1000.in / abcd1000.out
gdzie abcd to Twój własny dowolny tekst
i umieść w sieci + dodaj link w komentarzu na stronie:
http://algoorithms.pl/testy-do-zadan-moi-2018-2019/
lub prześlij do mnie jako spakowany zi

Zadanie 5 – Disruption
http://www.usaco.org/index.php?page=viewproblem2&cpid=842
* Zaliczone testy na stronie
* Krótki opis algorytmu
* analiza złożoności, kod na 100%

Zadanie 6 – Podzbiory
http://codeforces.com/problemset/problem/475/B
* Zaliczone testy na stronie
* Krótki opis algorytmu
* analiza złożoności, kod na 100%

Zadanie 7 – Jabłka i gruszki – sprawdzenie
Dla zadania Jabłka i gruszki sprawdź przynajmniej 2 paczki zip testów ze strony:
http://algoorithms.pl/testy-do-zadan-moi-2018-2019/

Zadanie 8 – Dodawanie w Linux
Zadanie tylko w załączeniu
Warunek zaliczenia:
* przechodzi własne 3 testy
* przesłany skrypt Do boju!

Walczymy!
Daniel



Dodaj komentarz

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