All messages

General: Addendum (Niestandardowe skróty)

Public message

- Zadań w tej chwili jeszcze nie ma, ale postaram się, żeby się pojawiły przed następnym kółkiem. Będą nastawione na napisanie różnych wariacji hashy i testowanie nowych podejść. - Do kwestii teorioliczbowych związanych z hashami jeszcze wrócimy (mnożenie modulo i modulo przez pierwsze Mersenne'a) na kółku o bardziej matematycznej tematyce. - Hash śladami macierzy tworzymy losując dla każdego znaku macierz 2 x 2 - hashem jest ślad iloczynu macierzy kolejnych znaków ciągu. Ponieważ tr(AB) = tr(BA), hash rotacji cyklicznych ciągu pozostaje taki sam. Można go napisać tak, aby liczyć hash podsłowa w O(1) (należy policzyć iloczyny prefiksowe i ich odwrotności). Aby uniknąć liczb rzeczywistych, można użyć modulo - np. 2^64 (trochę trzeba się pobawić :) - trzeba poszukać informacji o macierzach odwrotnych i wyznacznikach). Alternatywnie, łatwo można użyć drzewa przedziałowego, co daje czas logarytmiczny.

General: Addendum (Randomizowane)

Public message

- Aby policzyć pi, należy losować punkty w kwadracie ze wpisaną ćwiartką koła o środku w rogu kwadratu. - Zadanie z zapytaniami o prefiks: biblioteczka zna ukryty ciąg (otoczony atmosferą grozy i pożogi) złożony z liter ACTG i długości n. Zadajemy pytania, czy dany ciąg jest prefiksem ukrytego ciągu. Należy wykonać średnio ~2.25n zapytań. - Zadanie z prostą: mamy n punktów. Szukamy prostej, która przechodzi przez jak najwięcej punktów na płaszczyźnie. Mamy gwarancję, że wynik to co najmniej n/4. Kartka jest dosyć obszerna, a do randomizowanych jeszcze wrócimy :)

General: Addendum (Wyszukiwania)

Public message

- Na kółku trochę powspominaliśmy o zmiennoprzecinkowości. * Typy w C++: float, double, long double, __float128. Posortowane wielkością, precyzją i czasem działania (wszystko rosnąco). W praktyce: zawsze double, w razie problemów z precyzją long double, gdy jesteśmy zdesperowani pod względem wydajności float. * Typ zmiennoprzecinkowy (ustandaryzowany pewnym IEEE, więc tak też jest np. w Pythonie) zapisuje liczbę rzeczywistą jako m * 2^e * (-1)^s: zapis składa się z mantysy m, wykładnika e i znaku s. * Dodawanie liczb zmiennoprzecinkowych nie jest łączne i inne kurioza. http://www.walkingrandomly.com/?p=5380 * Jeżeli ktoś jest zaciekawiony tematem to dobrym źródłem jest What Every Computer Scientist Should Know About Floating-Point Arithmetic: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html - Zadanie Meteory z kółka to tak na prawdę uproszczona wersja prawdziwego zadania Meteory z OIa. Dlatego zmieniłem jego nazwę na kartce na Meteoryty :P - Trik „mniejszy-większy” (jeszcze kiedyś do niego wrócimy i dostanie własne miejsce na dowód): Umiemy dodać zbiór wielkości a do zbioru wielkości b w czasie O(a). Mamy n rozłącznych jednoelementowych zbiorów. Jeżeli mamy wykonywać operacje łączenia dwóch dowolnych zbiorów, to możemy je wykonać w amortyzowanym czasie O(n log n). Rozwiązanie: wystarczy zawsze dodawać mniejszy zbiór do większego. * Jeżeli dodajemy w trochę innym czasie (np. O(a log b)), to możemy przyjąć że O(log b) to stała rzędu O(log n) – otrzymujemy O(n log^2 n). - Zadanie z geometrii pochodziło z AMPPZ 2018: http://www.amppz.ii.uni.wroc.pl/files/amppz_problemset_pl.pdf (A: Aparat na dronie)

General: [Spoiler!] Hinty (Drzewo Fenwicka)

Public message

Humanista: - Wystarczy wykorzystać operator xora i napisać zwykłego Fenwicka. Do zamieniania można wykorzystać xor-swap. Niestrzeżone Antyki: - Da się przejść między dwoma polami jeżeli otacza je dokładnie taki sam zbiór płotów. - Należy wykorzystać hashe, oznaczające zbiór płotów otaczających dane pole. - Możemy np. xorować prostokąt albo dodawać na nim jakąś losową wartość, gdy ustawiamy/zdejmujemy płot. Sumowanie prostokątów: - Trzeba się postarać i napisać dobrze dodawanie 2D, w sposób z kółka/pracy naukowej z addendum. Uwaga: w pracy naukowej jest bląd we wzorkach, ale dosyć łatwo go znaleźć.

General: Addendum (Pierwiastki)

Public message

- Drzewo pierwiastkowe (o wysokości O(log log n)). Można np. dopisać aktualizacje w pierwiastku, i coś podobnego do aktualizacji na przedziale. Opisane jest tutaj: https://cp-algorithms.com/data_structures/sqrt-tree.html - Mergesort Tree to drzewo przedziałowe, które w każdym wierzchołku przechowuje posortowany ciąg z tego poddrzewa. Możemy je wykorzystać w „dynamicznych” inwersjach, ale wtedy musimy wykorzystać też specjalną strukturę zbioru. Jest to przykład sytuacji, gdy za pomocą pierwiastków dostajemy elementarne rozwiązanie z małą stałą, choć gorszą złożonością - O(n sqrt(n) log(n)) zamiast O(n log^2(n)). Dorzuciłem wam zadanko implementacyjne (do Pierwszej Krucjaty) na parsowanie (parsing), warto zapoznać się z tematem, bo jest to całkiem przyjemne :) Będą jeszcze zadania z Pierwiastków, ale muszę zdobyć paczki. Na razie macie dwie gwiazdki (Bajkę o dzielnikach i Kontenery), Pawiana i „Dynamiczne inwersje” do zaklepania (warto tutaj użyć STLa – lower_bound, upper_bound, find – żeby uprościć implementację).

General: Addendum (Drzewo Fenwicka)

Public message

Alternatywna nazwa drzewa Fenwicka to drzewo potęgowe, a po angielsku Binary Indexed Tree (BIT). Praca naukowa o operacjach przedział-przedział na dodawaniu z Fenwickiem (lub dowolną strukturą przedział-punkt): https://arxiv.org/abs/1311.6093 Nie ma tego na kartce, więc jak ktoś jest ciekawy to zachęcam do przeczytania. Poza tym, zauważcie, że wyprowadzając tę metodę i licząc to dla 2D, wcale nie trzeba rozpatrywać 4 przypadków. Tak jak zaczynałem robiąc przypadek jednowymiarowy wystarczy opracować, jak zmienia się get_prefix(i) przy dodawaniu na jakimś sufiksie [a, n]. Wtedy [a, b] otrzymujemy dodając +x na [a, n] oraz -x na [b+1, n]. Analogicznie, w 2D wystarczy opisać wzorki dla [x1, y1] : [n, n] (czyli to co rozpisałem na tablicy), a [x1, y1] : [x2, y2] wychodzi z zasady włączeń i wyłączeń (tak jak sumy prefiksowe 2D). Oczywiście otrzymane w ten sposób wzory są mniej efektywne – rozpatrując 4 przypadki niektóre współczynniki się zerują, więc w efekcie wykonamy mniej operacji na Fenwicku. Za pomocą Fenwicka łatwo będzie robić hashe dynamicznego ciągu, ale hashe dopiero będą, więc o tym nie wspominałem. Nie wspominałem też o tym, że robiąc Fenwicka 2D zamiast Fenwicka Fenwicków można np. robić Fenwicki specjalnych zbiorów (PBDS tree z order statistics) – powiemy jeszcze o nich w przyszłości. A po co komu Fenwick? Podsumujmy: + mniejsze zużycie pamięci + średnio szybszy + łatwiejszy i krótszy do zaklepania + elegancki (punkty stylu) + dużo prostszy i szybszy wariant wielowymiarowy - wszystko, co można osiągnąć Fenwickiem, można osiągnąć drzewem przedziałowym w takiej samej złożoności. A w praktyce gdzie zrobi się Fenwicka? Może w jakiejś implementacji prostej bazy danych, gdzie pozwalałby np. na efektywne zapytania o to, ile jest krotek których wartości są w podanych przedziałach (dla wielowymiarowego drzewa).

Skierowany graf acykliczny (dag): Limity czasu

Public message

Zwiększyłem limity czasu, bo jednak da się dostatecznie zwiększyć limity pamięci na SIO, aby rozwiązanie z bitsetami wchodziło. Teraz takie rozwiązanie wchodzi na więcej punktów niż 50, jeżeli jest dobrze napisane. Polecam jednak spróbować zrobić to zadanie bez bitsetów i kwadratowego zużycia pamięci – taki program jest nawet trzykrotnie szybszy (na SIO). W końcu i tak bitsety są techniką służącą do zmniejszania stałej, więc możecie i pokminić nad rozwiązaniem z jeszcze mniejszą stałą :)

Skierowany graf acykliczny (dag): Heura

Public message

Public service announcement: w DAGach między daną parą wierzchołków może istnieć więcej niż jedna ścieżka. Słabo złożyłem testy do tego zadania, bo nie paczkowałem, ale będę odejmować punkty za heurę (było już takich parę), która zdaje się to ignorować. Edit: od teraz testy są paczkowane, więc przyszłe heury dostaną 0 punktów.

Kolekcjoner Bajtemonów (kol): Limity czasu

Public message

Paczka ze Szkopule miała źle ustawione limity czasowe, więc trochę je zmieniałem. Doszło jednak do kuriozum, że jedno z rozwiązań wzorcowych (korzystające z systemu dwójkowego, nawiasem mówiąc) dostaje na mniejszych paczkach częściowe limity czasu. Zamiast tego zmieniłem, że częściowe limity czasu są tylko na największych paczkach, żebyście mieli motywację, aby znaleźć rozwiązanie szybsze (da się przyspieszyć kilkukrotnie).

General: [Spoiler!] Hinty (Operacje bitowe)

Public message

Skierowany graf acykliczny: - Wystarczy skupić się na odpowiednio małym podzbiorze wierzchołków, i policzyć wyniki biorąc tylko nie pod uwagę jako wierzchołki osiągalne. Kolekcjoner Bajtemonów: - Jak sprawdzić, jaka jest oczekiwana liczebność kart. Gdy już to masz, „niespójność” wyniknie w podobny sposób jak w uproszczonym zadaniu z dwukrotnymi powtórzeniami (patrz na bity). - Aby przyspieszyć: Czy musimy trzymać się systemu dwójkowego? Krasnale: - Zadanie na dynamika na podzbiorach (łatwe, jeżeli się takie wcześniej robiło) - Spróbuj zrobić dynamika zliczającego odpowiednie permutacje zawierające dany podzbiór elementów (krasnali).

General: [Spoiler!] Hinty (Tabela potęgowa i drzewo redukcyjne)

Public message

Zliczanie: - Weźmy jakieś x i y < x. Licząc gcd(x, y) otrzymamy albo x, albo wartość mniejszą, ale przy tym gcd(x, y) | x. Zauważmy, że mając gcd(x, y) | x oraz gcd(x, y) < x musi być gcd(x, y) <= x/2. Wynika to z tego, że musiał nam „ubyć” z NWD jakiś czynnik pierwszy, a czynników pierwszych w liczbie rzędu n jest O(log n). - Na podstawie tego można zrobić bardzo chamskie rozwiązanie z tabelą potęgową gcd, albo znacznie krótsze, ale może lekko trudniejsze koncepcyjnie. Optymizm: - To zadanie na drzewo redukcyjne: musimy wymyślić odpowiednią operację i strukturę do tej operacji, która będzie liczyć wynik. - Mając dwie sąsiednie podtablice, gdzie może pojawić się spójny podciąg o maksymalnej sumie? [ Lewa podtablica ] [ Prawa podtablica ] !! - Dla danej podtablicy ważne są: suma, sufiks, prefiks, najlepszy wynik w przedziale. Jak aktualizować te wartości łącząc podtablice?

General: Addendum (Operacje bitowe)

Public message

Rzeczy, których nie znajdziecie na kartce, a o których powiedziałem lub nie. Zachęcam do zobaczenia kartki, niestety dzisiaj brakło trochę czasu, nie zdążyłem powiedzieć o: - Przeglądaniu wszystkich podzbiorów zbioru z danej bitmaski (przydatne przy brutach i optymalizacjach). - Zliczaniu unikatowych wartości w zbiorze (zarówno zbiór i wartości są bardzo małe - przydaje się to czasem). - Upraszczaniu ifologii za pomocą bitmask (przykład sprawdzania czy litera jest samogłoską). Rzeczy: - Two's complement, czyli jak reprezentować liczby ujemne w systemie binarnym, tak, żeby działał dokładnie ten sam algorytm dodawania. Tutaj komentarz na temat tego że liczby ujemne w systemie binarnym mogą mieć nieoczekiwaną postać. Zachęcam do spojrzenia na Wikipedii. Bitowe zadanka (jak chcecie, to możecie zadać pytanie, czy dobrze rozwiązaliście - patrzcie na to jako na ćwiczenia czy sprawnie używacie operacji bitowych, są tutaj łatwiejsze i trudniejsze): - Policz negację liczby w two's complement za pomocą operacji bitowych i arytmetycznych (ale bez odejmowania...) - Mamy bitmaski A i B złożone z m bitów. W pierwszym rzędzie zapisujemy kolejne bity A, a zaraz pod nimi odpowiednie bity B. Stwierdź (za pomocą operacji bitowych), czy istnieje kwadrat 2 x 2 składający się wyłącznie z 0 albo 1? Na przykład tutaj istnieje taki kwadrat: A 1010[11]01 B 0110[11]00 - Posortuj 3 liczby w zmiennych a, b, c (potrzeba min, max, i xora) - jest to (raczej) szybsze niż bubblesort z 3 wyjątkami. - Wyizoluj najmniej znaczący bit liczby - to kiedyś się przyda, gdy będziemy omawiać pewną strukturę. Na przykład: 0101 0110 -> 0000 0010 - Odwróć kolejność bitów liczby 32-bitowej. Gdyby liczba była 4-bitowa, to z 1010 zrobimy 0101. - Mamy dany bardzo długi ciąg złożony z 64-bitowych liczb. Każda wartość występuje dokładnie dwa razy, poza jedną, która występuje dokładnie raz. Znajdź wartość występującą raz w stałym zużyciu pamięci i jednym przejrzeniu całego ciągu. Utrudnieniem tego zadania jest Kolekcjoner Bajtemonów.

General: Addendum (Tabela potęgowa i drzewo redukcyjne)

Public message

(Addendum przeniesione z dashboarda) Krótkie addendum, czyli (w miarę) ważne rzeczy które zapomniałem powiedzieć na kółku. * Tabela potęgowa może się przydać, gdy reszta rozwiązania i tak ma złożoność co najmniej O(n log n), więc dorzucenie konstrukcji tabeli nie zrobi większej różnicy. Na przykład, rozwiązując Klubowiczów 2 za pomocą wyszukiwania binarnego i tak spytamy o wartość na przedziale O(n log n) razy, więc konstrukcja tabeli nie szkodzi złożoności. * Teoretycznie drzewo redukcyjne robi to samo co tabela potęgowa, a nawet więcej (wystarczy operacja łączna). Jednakże może być trochę trudniejsze do napisania i wymyślenia. Poza tym, jest o wiele mniej znane. * Nazwa „drzewo redukcyjne” pochodzi od tego, że wierzchołek drzewa albo zna odpowiedź na zapytanie, albo redukuje problem do odpowiadania na zapytanie na połowie ciągu. * Drzewo redukcyjne należy do rodziny ciekawych struktur optymalizowanych operacjami bitowymi. W przyszłości mogą się takie jeszcze pojawić.