All messages

Śliwki (sli): Re: Pusta skrzynka

Public message

W treści jest "znajdź liczbę skrzynek w przedziale [l,r] (1<=l<=r<=n), w których liczba śliwek jestpodzielna przez k (1<=k<=5)." Cała reszta to historyjka, która nie koniecznie musi być zgodna z problemem zadania.

General: Re: Zadania

Public message

1) Z LOW nie ma zadanek bo Krzysiek nie znalazł żadnych ciekawych 2) Z Preprocessingu nie ma zadanek bo temat polegał na tym, żeby wiedzieć, że można preprocesować, a nic więcej kreatywnego w tym zwykle nie ma, więc zadania raczej byłyby nudne, bo cały ich sęk jest w tym, żeby wpaść na to, żeby zpreprocesować. 3) Wrzuciłem z zeszłego roku. Też nie są jakieś ekstra, ale no... są.

General: Dodatkowe informacje do dzisiejszego tematu

Public message

- strona z dowodem algorytmu znajdowania dwóch najdalszych wierzchołków: https://www-users.mat.umk.pl/~stencel/acm/algorytmika_praktyczna.pdf#page=118&zoom=auto,-265,536 (Nic lepszego nie udało mi się znaleźć.) - dlaczego w algorytmie znajdowania dwóch najmniej oddalonych wierzchołków jest 7, czyli maksymalne możliwe rozłożenie: "W kwadracie o boku d mogą znaleźć się co najwyżej cztery punkty odległe do siebie o nie mniej niż d (są wtedy ustawione w narożnikach). Jeżeli z kwadratu usuniemy jeden bok, to zmieszczą się w nim tylko 3 takie punkty."

Malarz (mal): Re: Skalowanie przedziałów

Public message

Rzeczywiście, ta część nie jest jasna. Idea jest taka, że jak masz zakres jakiś <0,10^9> albo <0,10^18> to nie możesz go dać jako baza drzewa przedziałowego, oczywiście, bo jest za duży. Od teraz ten zakres będę nazywał R. Można jednak zauważyć, że zapytań z zadania będzie około 10^5-10^6. Te zapytania to pewnie pojedyncze lub podwójne indeksy (pary indeksów), więc łącznie różnych indeksów jest maksymalnie rzędu 10^6. Niech Q będzie zbiorem tych indeksów. Chcemy teraz wziąć każdy indeks z Q i przetłumaczyć ich wartości z R w zakres D = <0,~10^6>, żeby można je było zmieścić w drzewie przedziałowym. W tym celu sortujemy elementy Q (po wczytaniu wszystkich zapytań) i najmniejszemu przypisujemy 0, drugiemu najmniejszemu przypisujemy 1 itd. aż największemu indeksowi z Q przypiszemy liczbę rzędu 10^6 lub mniejszą. Stworzyliśmy tłumaczenie z R w D. Możemy je zapisać np. w std::map<> albo std::unordered_map<> Teraz, obsługujemy zapytania w oryginalnej kolejności. Gdy pojawia się jakiś indeks n, to zerkamy do słownika i wyłuskujemy jego odpowiednik w D. To jest tak jakbyśmy każdemu indeksowi z wejścia przypisali numerek z przedziału, który nam odpowiada w celu dalszej obsługi. Często konieczne będzie stworzenie tłumaczenia w drugą stronę. Tzn. w momencie gdy tworzymy tłumaczenie z R w D, to za każdym razem, gdy przypisujemy jakiemuś elementowi w R jakiś element w D, to tworzymy również przypisanie odwrotne, z D w R, w drugiej mapie, hashmapie, lub tym razem tablicy. To jest szczególnie przydatne gdy w zadaniu gra rolę długość przedziału. Nie możemy wówczas korzystać z róznicy indeksów wierzchołków w drzewie przedziałowym, tylko musimy korzystać z róznic oryginalnych wartości. Lub gdy musimy zwrócić indeks wierzchołka, dla którego osiągane jest np. maksimum -- wówczas indeks w drzewie przedziałowym nie będzie jego "prawdziwym", by tak rzec, indeksem. Możliwość utworzenia tłumaczenia odwrotnego wynika stąd, że tłumaczenie pierwotne jest różnowartościowe. Mam nadzieję, że rozjaśniłem sprawę. :3

General: Jutrzejsze (25.02) kółko

Public message

Cześć. Jutrzejsze kółko wyjątkowo odbędzie się o godzinie 20:00.

Przecięcia odcinków (odc): Odp: czasy

Public message

> Jak wzorcówce udaje się osiągać takie czasy? Nie udaje :) Zwiększyłem czasy dwukrotnie i zrobiłem rejudge'a, sprawdźcie wyniki, bo pewnie już rozwiązania wchodzą.

Faktoryzacja wielu liczb (czy): Paczka była popsuta...

Public message

i nadal jest i nie udało mi się dociec dlaczego jest popsuta, ale okazuje się, że dwa testy na żadnym konteście nie działają i na każdym konteście są dezaktywowane, więc na tym też dezaktywowałem. Przepraszam za stres spowodowany brakiem setek. Poprawne rozwiązania już powinny dostawać maksa. P.S. Dlaczego nikt mi nie wypomniał, że prawidłowe rozwiązania nie wchodzą? Musiałem sam się doszukać... naprawdę co za szczeście macie, że sprawdziłem z kilkudniowym opóźnieniem, a nie wcale

General: Re: Omówienia

Public message

> Czy są omówienia zadań z MST? Już są! Znaleźć je można w Archiwum.

General: Omówienie zadań z KMP

Public message

Link do wideo z omówieniem zadań z KMP. https://www.youtube.com/watch?v=7fRnYxVAyyg

General: Nowe zadanie

Public message

Dodałem do zadań z KMP Szablon; jest to trudniejsze zadanie od pozostałych, polecam spróbować je zrobić. Też omówię to zadanie na omówieniu.

Malarz (mal): Re: Skalowanie Przedziałów

Public message

Jest! W zakładce "Zadania" (Problems) przy zadaniu Malarz pojawił sie jakiś czas temu link do omówienia. Ostatni akapit dotyczy skalowania drzew.

General: Kod do KMP + informacja

Public message

Tutaj macie kod do KMP który pokazywałem na zajęciach: https://csacademy.com/code/0uTdcWyW/ Trudniejsze zadanie z KMP (zadanie z gwiazdką dla ambitnych): https://szkopul.edu.pl/problemset/problem/IaAZEJBiGLgNgDlpgNMn94WE/site/?key=statement Omówienia do zadań tradycyjnie wstawię za tydzień.

General: Zadania z toposorta i SSS

Public message

Wrzuciłem już zadania z poprzedniego kółka. Przepraszam was najmocniej za opóźnienie.

General: Omówienie zadań

Public message

Tu jest link do omówienia: https://www.youtube.com/watch?v=v1v-GgA9TLU

Co ma babcia Bajtazara do darmowego kebaba? (com): Rejudge na poprawionych limitach pamięciowych

Public message

Jak mogliście zauważyć były złe limity pamięciowe. Poprawiłem je i puściłem rejudga, więc macie teraz więcej punktów.

General: Omówienia zadań

Public message

Omówienia zadań są już dostępne jako nagrania w archiwum pod adresem tym co wcześniej był ogłaszany na Teamsach: https://drive.google.com/drive/folders/17Mn-vC4vARwUbQISn5pD-P3NGesqrCLW?usp=sharing

Morskie opowieści (mor): Limity czasowe zostały zwiększone

Public message

W zadaniu były za małe limity czasowe (w szczególności wzorcówka nie dostawała maksa), więc zwiększyłem odpowiednio limity dla większych testów. Wszystkie rozwiązania zostały sprawdzone ponownie, wyniki mogły się zmienić.

General: Omówienia zadań i skalowania

Public message

Pojawiły się pierwsze omówienia zadań, możecie je znaleźć w zadaniach (przy zadaniu macie link "omówienie"), brakujące pojawią się jutro. W niektórych omówieniach zadań z drzew przedział-przedział będę odwoływał się do czegoś takiego jak skalowanie - z racji że jest to część wspólna, zamiast się dublować nagram omówienie tego osobno. Przy okazji wykorzystam to do zrobienia tego właśnie w innej formie - o ile wydaje mi się, że omówienia tych zadań w wersji tekstowej da się całkiem sensownie przygotować, tak do wytłumaczenia skalowania myślę, że przyda mi się możliwość zaprezentowania tego z rysunkami. Trudno mi ocenić na ile te omówienia są zrozumiałe, także będę wdzięczny za wszelkie uwagi do nich, w razie potrzeby będą one aktualizowane (poinformuję wtedy o tym w ogłoszeniu).

Tetris (trudniejszy) (tet): Tetris

Public message

Przez pomyłkę wrzuciłem złą paczkę do zadania Tetris - wrzuciłem taką z większymi limitami, która wymaga jeszcze obejścia jednego dodatkowego problemu. Jak już jest to zostawiam, ale wrzuciłem także to, co planowałem na początku. Wersja z większymi limitami ma w nazwie "trudniejszy", żebyście po nazwie wiedzieli które to które. Wersja z mniejszymi limitami jest zauważalnie prostsza, więc zachęcam do wbicie jej jako pierwszej.

General: Omówienie zadań z drzew przedziałowych

Public message

Wstawiam omówienie zadań z drzew przedziałowych: https://www.youtube.com/watch?v=2TQ7eDJKxTc