All messages

General: Odnośnie metod implementacji prawdopodobieństwa

Public message

Warto wiedzieć parę rzeczy przy korzystaniu z prawdopodobieństwa w C++. Zwykły rand zazwyczaj powinien w zupełności wystarczyć. Warto jednak pamiętać o ustawieniu srand(time()) (lub srand(milisekundy)) w sytuacjach gdy ktoś może hackować to rozwiązanie, np na codeforces. Warto zwrócić uwagę na wielkość liczby zwracanej przez rand. Jeśli próbujemy wylosować liczbę z większego zakresu niż ma rand, może to być problemem. W szczególności na codeforces rand zwraca liczby z przedziału [0, ~32000), więc można łatwo dostać WA nie pamiętając o tym. Ostatnia podpowiedź. Jeśli rand zwraca liczbę [0, 100), a chcemy dostać liczbę [0, 1000), to rand*rand%1000 działa źle. Nie dość że rozkład prawdopodobieństwa może nie być najlepszy, to jeszcze prawdopodobieństwa konkretnych reszt są złe. Np prawdopodobieństwo że rand*rand nie jest nieparzysty, więc rand*rand%1000 jest nieparzysty, to tylko 1/4. Lepiej zrobić rand*100+rand, da to w pełni losową liczbę z przedziału [0, 100*100).

General: Najbliższe kółko odbędzie się normalnie

Public message

Zapraszam!

General: Najbliższe kółko odwołane

Public message

Z okazji dnia dziecka kółko jest odwołane! Miłego wieczoru! :D Widzimy się za tydzień

General: Dzisiejsze kółko

Public message

Odbędzie się jak zwykle. Nie mam zaplanowanego tematu na dziś, więc kółko spędzimy na pojedynczych algorytmach bez większej kategorii, omawianiu zadań i tematach na życzenie uczestników. Na początku kółka zbiorę życzenia na tematy paru ostatnich kółek Zapraszam!

General: Kółko trwa

Public message

Jeśli jesteś zbyt leniwy by wejść na teamsy by sprawdzić czy dziś kółeczko się odbywa, to TAK, ODBYWA SIĘ :P

General: Dzisiejsze kółko

Public message

Odbędzie się normalnie. Tematem będą optymalizacje dynamików otoczką wypukłą

General: Pojawiły się zadania z zachłanów

Public message

Macie na nie dwa tygodnie - za tydzień będzie kółko z optymalizacji dp otoczką wypukłą. Jest ich mniej niż zazwyczaj, więc zachęcam do myślenia :)

General: Dzisiejsze kółko

Public message

Hej wszystkim! Nie dam rady pojawić się na kółku dzisiaj. Macie wolne :) PS. Jeśli ktoś bardzo chce porobić dziś algorytmikę, to pod wieczór pojawią się zadania na następny tydzień.

General: Jutrzejsze kółko

Public message

... odbędzie się jak zwykle o godzinie 17! Przypominam o zadaniach, zachęcam do myślenia, gdyż smutno omawia się zadania których nikt nie zrobił :( Link do ankiety z waszymi sukcesami: https://docs.google.com/forms/d/e/1FAIpQLSe9O5mKxMsLz5pYaR-1iRWFwb1IVoOV_3ntpHSWRuMyyut4ag/viewform?usp=sf_link

General: Powodzenia wszystkim na finale!

Public message

Życzę dużo punktów, ale przede wszystkim dobrej zabawy!

General: Dzisiejszy brak kółka

Public message

Ze względu na zaskakującą frekwencję dzisiejsze kółko nie odbyło się. Za tydzień dzień próbny finału, zatem kółka wtedy również nie będzie. Widzimy się za dwa tygodnie!

General: Dzisiejsze kółko

Public message

Na dzisiejszym kółku omówimy zadania z przepływów. Link do ankiety z rozwiązanymi zadaniami: https://docs.google.com/forms/d/e/1FAIpQLSekvsknN4mvXlOm0KrjZc7XAbQL50bVR1Vo-c_-z_q2sUubdg/viewform?usp=sf_link

General: Dzisiejsze kółko zaczynamy o 18

Public message

...żeby nie nachodzić na omówienie jeśli się przedłuży i dać wam chwilę wytchnienia po omówieniu. Za to kółko powinno być (hopefully) krótsze niż normalnie, więc liczę że nie skończymy za późno

General: Wyjaśnienie ostatnich zagadnień

Public message

Zaciąłem się ostatnio na kółku na problemie orów prefiksowych. Otóż w taki sposób w jaki to prezentowałem nie da się dojść do sukcesu. Wynika to z faktu, że wynikanie (a => b v c) jest równoważne (~a v b v c). Gdybyśmy taką formułę umięli rozwiązać 2-SATem, umielibyśmy rozwiązać 3-SATa, który jest NP. Można natomiast rozwiązać w bardzo podobny sposób problem "maksymalnie jeden na prefiksie". Zachęcam do zastanowienia się nad tym, omówię ten sposób na żywo na następnym kółku. Link do materiałów zewnętrznych z skojarzeń w grafach dwudzielnych wraz z dowodami lematów: http://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wyk%C5%82ad_7#lemat_3 A już w ten wtorek kółko z przepływów!

General: Jutrzejsze kółko

Public message

... odbędzie się zgodnie z planem. Tematyką będą skojarzenia w grafie dwudzielnym i 2-SAT. Od jutra kółko zaczynamy punktualnie: 17:00 Nie będę czekać na wszystkie osoby, gdyż tracę na to co tydzień ~10 minut, o które później muszę wydłużać

General: Zadania

Public message

Pojawiły się zadania! Dodatkowo, zadanie "ustawianie hasła" może się po dzisiejszym kółku stać prostsze. Zachęcam do ponownego zmierzenia się! Zadania z CD i HLD pojawią się w bliższym czasie

General: Materiały z kółka

Public message

Tutaj zamieszczam materiały do zagadnień z kółka: Drzewo sufiksowe: http://smurf.mimuw.edu.pl/node/578 EerTree: https://www.geeksforgeeks.org/palindromic-tree-introduction-implementation/ Aho-corasic: Tutaj nie przygotowywałem się z żadnych materiałów, więc polecam poszukać na własną rękę. Artykuł na wikipedii nie wygląda źle, a jeśli nie, to polecam poszukać na CFach

General: Dzisiejsze kółko...

Public message

... odbędzie się zgodnie z planem, o 17. Zapraszam :)

General: Najbliższe kółko...

Public message

... również zostanie poprowadzone przez Kubę Wasilewskiego, który jest srebrnym medalistą MIĘDZYNARODOWEJ olimpiady informatycznej (w ramach poprawy wobec poprzedniego ogłoszenia). Tym razem tematem będzie HLD. Ze względu na nowy semestr i kolizję terminów, najbliższe kółko zostanie jednorazowo przesunięte na godzinę 18.

General: Jutro 2 etap OIa

Public message

Cześć wszystkim! Uświadomiłem sobie, że jutro zaczyna się drugi etap OIa. Stąd żebyście się nie rozpraszali ani nie forsowali przed zawodami, odwołuję kółko. Za tydzień zaś zajęcia gościnnie poprowadzi Kuba Wasilewski, srebrny medalista olimpiady informatycznej! Tematem będą centroidy. Powodzenia na zawodach!

General: Następnego kółka nie ma :(

Public message

Hej wszystkim. Niestety ze względu na natłok sesyjny nie będę w stanie poprowadzić kółka za tydzień, ani tym bardziej znaleźć zastępstwa. W związku z tym proponują odpocząć, a jeśli ktoś jest spragniony informatyki, podobijać zadania z kółka/preoia. Także, jako że jesteśmy w połowie roku, prosiłbym was o wypełnienie krótkiej ankiety z feedbackiem dla mnie. Wszelkie odpowiedzi pomogą mi w lepszym prowadzeniu kółka :) https://docs.google.com/forms/d/e/1FAIpQLSdSq-1tuvZY1NNojddBVtCugBk7M8b5c8_5CZAebKx437OBhw/viewform?usp=sf_link

General: Za tydzień PREOI

Public message

Przypominam że w przyszłym tygodniu odbywa się druga część PREOIa. Zachęcam do startu! Jednocześnie z tego powodu kółko w ten wtorek jest odwołane

General: Materiały z kółka

Public message

Materiały z kółka zostały wrzucone na teamsy. Są dostępne w zakładce pliki, w materiałach z zajęć. Zadania na macierze zostały dodane!

General: Kółeczko dziś

Public message

Hej wszystkim! Przypominam że dziś znów jest kółeczko, dzisiejszym tematem będą macierze :) Zapraszam!

General: Kółko dzisiaj!

Public message

Cześć wszystkim! Po długiej przerwie kółko wraca do starego planu i odbędzie się dzisiaj. Przypominam że już obowiązuje wymóg 100 punktów w rankingu ;)

General: Przerwa i ferie

Public message

Hej wszystkim! Mam nadzieję że miło spędzacie ferie. Za tydzień kółka znów nie będzie, ze względu na odbywającego się wtedy PREOIa. Skupcie się w tym czasie na dobijaniu zadanek w rankingu stałym, a za tydzień spotkamy się już normalnie :)

General: Kółko 29.12

Public message

... jest oczywiście odwołane ;) Cieszcie się świętami :D

General: Odwołane kółko

Public message

Hej wszystkim! Ze względu na okres świąteczny jutrzejszego kółeczka nie będzie :) Nie daję też zadań na święta. Jeśli ktoś bardzo potrzebuje zadań do robienia, to macie już wystarczająco dużo na całego sylwestra ;) A wam wszystkim życzę wesołych świąt, żebyście porządnie odpoczęli i odzyskali siły na nowy rok!

General: Wymagania na przyszłe kółko

Public message

Hej wszystkim! Przypominam o ustaleniu, że na przyszłym kółku wymagam od każdego co najmniej jednego zrobionego zadania! Róbcie zadania, wyjdzie wam to na dobre :)

General: Następne kółko

Public message

Cześć wszystkim! Jak kategoria podpowiada, następne kółko będzie z teorii gier! Jest to jedna z moich ulubionych dziedzin, więc zapinajcie pasy i szykujcie się na rollercoaster najróżniejszych rozgrywek! Zapraszam!!!

General: Zadania na dziś

Public message

Hej wszystkim! Dziś mamy kółko i mam nadzieję że walka z zadaniami idzie dobrze :) Tutaj zostawiam ankietę, uzupełnijcie proszę PRZED rozpoczęciem kółka co udało wam się wymyślić https://forms.gle/9WNDxrswSFcSteECA Do zobaczenia dzisiaj!

General: Wnioski po kółku

Public message

Cześć! Podsumowując dzisiejsze kółko, przerobiliśmy tylko 3 zadania (Szybka Dijkstra, NP-Hard Problem i Rak), a także teorię do grafów warstwowych. Jeśli ktoś szuka sposobu na sprawdzenie wiedzy z grafów warstwowych, to polecam zadanie Dookoła Świata (w wersji n, m <= 1000, wzorcówka jest niestety znacznie trudniejsza), oraz dokończyć zadanie Morskie Opowieści. Za tydzień kontynuujemy omawianie zadań. Z tej okazji jeszcze raz podkreślam jak ważne jest, żebyście nad zadaniami pomyśleli. Wiele z nich jest w waszym zasięgu, nawet jeśli wymagają poświęcenia 15-30 minut na myślenie. A omawianie zadań nad którymi nie myśleliście jest dużą stratą potencjału, najwięcej uczy się człowiek gdy wymyśli samemu, lub gdy mu się po długiej walce nie uda i wtedy poda mu się odpowiedź. Także przypominam, że trudność gwiazdkowa jest subiektywna - nie bójcie się przeczytać treści zadania "trudniejszego" i pomyśleć nad nią chociaż chwilę - a nuż będzie prostsze niż mi się wydawało... Do zobaczenia za tydzień!

General: Wspomniane algorytmy - odnośniki

Public message

Na kółku wspomniałem o paru algorytmach, których omawiać nie będę. Załączam zatem linki do dodatkowych informacji o nich, jakby ktoś był ciekaw. Test Millera-Rabina: https://pl.wikipedia.org/wiki/Test_Millera-Rabina Funkcja mobiusa: https://codeforces.com/blog/entry/53925 Jakby ktoś chciał miejsce gdzie może sprawdzić się z algorytmem rho-pollarda, to ja znam takie zadanie (o treści "sfaktoryzuj liczbę"): https://www.spoj.com/problems/FACT1/ Jeśli zaś ktoś jest ciekaw dowodu twierdzenia fermata, to można taki znaleźć tu: (osobiście polecam kombinatoryczny i z teorii grup) https://pl.wikipedia.org/wiki/Ma%C5%82e_twierdzenie_Fermata PS: pojawiły się (wreszcie) zadanka!

General: Następne kółko

Public message

Hej! Niestety na ostatnim kółku nie wyrobiłem się z dwoma zagadnieniami: - Liniowym sitem - Chińskim twierdzeniem o resztach. Postaram się szybko te dwa zagadnienia nadrobić za tydzień. Zgodnie z obietnicą za tydzień jest kółko zadaniowe z grafów. Zadania zaraz pojawią się w plikach! WAŻNE: Szczególnie zależy mi na zadaniu Hydra, dlatego każda osoba która wymyśli i zgłosi mi rozwiązanie (bądź omówi) dostanie czekoladę/wybraną inną nagrodę :) Naszła mnie myśl, że bez sensu nagrywać kółko, gdy jedyne co widać to gadający ja. W związku z tym od następnych zajęć będę udostępniać tablicę :) Możecie korzystać z tego widoku, lub nadal śledzić ją u siebie!

General: Dzisiejsze kółko

Public message

Hej wszystkim! Zgodnie z obietnicą dziś odsapniemy sobie od dynamików i zanurzymy się w grafy! Porozmawiamy sobie o dwuspójnych i dominatorach! Zapraszam!

General: Ogłoszenia parafialne

Public message

1) Za tydzień znów kółko! Tematem następnego kółka również będą dynamiki. Tym razem jednak dla odmiany porozmawiamy o różnych sztuczkach i nietypowych podejściach do problemów, bez których wielu zadań nie da się rozwiązać. 2) Pojawiły się zadania! Zachęcam do rozwiązywania :) Do rozwiązania nie wybrałem zadań już omówionych, wychodząc z założenia że w większości takich zadań to pomysł jest najważniejszy, a implementacja nie jest na tyle ciekawa żeby dać to zadanie. NIE oznacza to, że nie zadane zostały zadania na podobne pomysły ;) Dzięki temu będziecie mieli szansę przećwiczyć implementacje takich rozwiązań 3) Usunięte wiadomości Sio mnie nie lubi i usunęło parę moich ogłoszeń. Nie zmienia to faktu że zadania z dynamików dalej dostępne są w plikach, a nagrody za zadanie 5* i wklepanie pozostałych 4* dalej są aktualne :) 4) Nagrywanie kółka Na ostatnim kółku postanowiliśmy że będziemy nagrywać nasze spotkania. Nie planuję wrzucać nigdzie nagrań, ale jeśli ktoś przegapił kółko i potrzebuje zobaczyć, to przy dobrej argumentacji mogę się podzielić :)

General: Zadania dodatkowe i nagrody

Public message

Przypominam o zadaniach z nagrodami! Do zrobienia: - dowolne zadanie z 4 lub 5 gwiazdkami które nie zostało jeszcze omówione - optymalizacja złożoności w zadaniu "Graph coloring" Chętnych proszę o pisanie wiadomości z zadaniem i szkicem rozwiązania :)

General: Następne kółko

Public message

Hej wszystkim! Na następnym kółku opowiem wam trochę o dynamikach na drzewach i o sposobach podchodzenia do takich zadań. Spróbujemy też omówić sobie parę ciekawszych zadanek. Do zobaczenia jutro!

General: Skrypt

Public message

Przesyłam link do skryptu do którego odwoływałem się w trakcie kółka. https://kubin.w.staszic.waw.pl/esoterica/sqrt.html

General: Link do spotkania

Public message

Z przyczyn organizacyjnych zaczniemy od spotkania na meecie, gdyż ma on niższy próg wstępu. Tam postaramy się skonfigurować odpowiednie dostępy do MS Teams i jeśli wszystko pójdzie dobrze, to na tej drugiej platformie będziemy kontynuowali zajęcia. Link do spotkania: meet.google.com/hhq-asyi-wag

General: Pierwsze kółko

Public message

Hej wszystkim! Przypominam że jutro pierwsze kółko! Żeby wszystko przebiegło sprawnie, proszę wszystkich o punktualność! Wtedy pierwsze 15 minut poświęcimy na dobre konfigurowanie kont i ustawień, a potem płynnie będziemy mogli przejść do części organizacyjnych :) Z tego względu też możliwe, że na początku spotkamy się w innym miejscu niż teamsy, szczegóły podam krótko przed rozpoczęciem. Do zobaczenia!

General: Termin kółka

Public message

Kółko będzie odbywać się we wtorki 17:00. Będziemy się spotykać na MS Teamsach. Zapraszam wszystkich na pierwsze kółko, odbędzie się ono w ten wtorek. Zaczniemy od części organizacyjnej, a później (na ile czas mi pozwoli), poprowadzę kółko, gdzie będziemy starali się rozwiązywać zadania w złożoności pierwiastkowej. Dokładne szczegóły podam bliżej wtorku!

General: Ankiety

Public message

Cześć wszystkim! Prosiłbym was o wypełnienie ankiety odnośnie formy prowadzenia kółka! https://docs.google.com/forms/d/e/1FAIpQLSczGexDjOcW15eN5DatvdNznMq0hxGwsPuY_qyv-M-M-ru_dA/viewform?usp=sf_link Dzięki!