English
Temat: Feedback do każdego zadania
W nawiasie mój czas wymyślenia rozwiązania.
[1C] Kto wygrał?
Świetne zadanie na ten slot. Bardzo lubię, gdy łatwe zadania mają naturalną treść i użycie zasad danego konkursu jest dobrym przykładem. Może warto zawsze w treści 1C dodać zdanie/przypis, że należy odsłonić swój wynik po wysłaniu zgłoszenia? Ja chyba o tym zapomniałem.
[1B] Liderzy
Dobra trudność i zadanie, słaba treść. Jakieś straszne podciągi w tak łatwym zadaniu. Pracujesz w sklepie i masz N cukierków o smakach a[i]. Podziel je na mieszanki, każda musi być określona dominującym smakiem czy coś. Swoją drogą, najpierw źle przeczytałem treść i chciałem dzielić na przedziały, nie umiałem.
[1A] Modernizacja Bajtocji (5-10m z kartką)
Super, bardzo podobało mi się rozwiązanie. Ze smutkiem przyznam, że pewnie 1A powinno być łatwiejsze, by zostawić miejsce na rosnącą trudność w ciągu tygodnia. Trudna decyzja: przystępne zadanie dla większego grona czy od razu jakaś zabawa dla czołówki.
[2C] Znaczki pocztowe
Za trudne, ogromny skok trudności z 1C. I wydaje mi się, że znowu rozdawanie cukierków dałoby lepszą treść, jak w 1B.
[2B] Alchemik Bajtazar (kilka sekund)
Mi nie sprawiło przyjemności, bo natychmiastowo widziałem jak zrobić. Ale zadanie ok, właśnie taka powinna być dywizja B. To zadanie mogłoby też iść jako 5C. Byłoby za trudne na taki slot, ale bardziej robialne niż obecne tam zadania.
[2A] Grupa permutacji (nie umiałem w 1 dzień)
Najtrudniejsze 2A ever. Szybko wymyśliłem O(K*N^2) i próbowałem przyśpieszać. Długo też analizowałem jak cykle się ze sobą łączą, by może je utrzymywać lub liczyć LCM czy GCD. Pokonało mnie to zadanie. Fajne rozwiązanie, zaskakujące. Słabo, że trudno jest zrozumieć poprawność. Dostałem aż 6 punktów za bruta - trochę sporo, ale pewnie tak ma być skoro łatwe zadanie.
[3C] Obrazy (2m z kartką)
Ok, dobre na ten slot.
[3B] Żelki (30s)
Ok. Trudno mi ocenić trudność, bo od razu umiałem przez znajomość podobnych zadań. Bardzo lubię następujące: "Wsiadasz na parterze do windy, która ma trzy przyciski: jedź w górę o +A, +B lub +C pięter. Ile z N pięter budynku jest osiągalnych? A,B,C <= 1e6, N <= 1e18."
[3A] Splatanie ciągów (1 dzień, niedokończone)
Dobre trudne zadanie na eliminacje potyczek. Wydaje się na początku absurdalnie trudne, ale robienie przykładów na kartce szybko sugeruje do policzenia f(A,B) potrzebna jest tylko długość B, który prawdopodobnie jest tym krótszym ciągiem. Napisanie bruta to potwierdziło. Następnie wkopałem się w niepotrzebnie skomplikowane rozwiązanie: K-tą liczbę wyniku liczę w O((N/K)^2) z (jak się potem okazało) niepotrzebnymi funkcjami liniowymi i kwadratowymi, a małe K chciałem robić z FFT, ale zakopałem się tam z odejmowaniem źle policzonych przedziałów wewnątrz jednego monotonicznego kawałka. Celowałem w O(N^1.5 * log(N)), a lepiej było skupić się na jakimś D&C+FFT i mieć pewnie O(N*log^2(N)). Ja unikałem D&C, bo w połączeniu z pierwiastkiem byłby to bardzo wolny rozw. Nie wiem czemu nie połączyłem kropek pomiędzy moimi rozwiązaniami, by robić O(N/K * polylog). Dostałem 6 punktów za moje O(suma po (N/K)^2).
[4C] Łamigłówka 3 (kilka sekund)
Wydaje mi się bardzo standardowe i nie zdziwię się, jeśli gdzieś kiedyś było. To jest taki rodzaj zadania (w kontraście do np. 3C), że jest trywialne dla kogoś doświadczonego i może być trudne dla początkującego. Nie ma w tym nic złego, zadania z dywizji C mają być dopasowane do początkujących.
[4B] Desant 3 (nie umiałem w 1 dzień)
Kolejne zadanie po 2A, które mnie pokonało. Trochę głupio, bo zdarzyło mi się w przeszłości wymaksować rundy 1-4. Bardzo kusiło tutaj robić zadanie od tyłu, iterując najpierw końcowy przedział jedynek. Nic z tego nie wyszło. Symulacja od przodu też mi nie poszła, no cóż. Zadanie pewnie za trudne na swój slot, ale bardziej jednak odczuwam swój skill issue.
[4A] Kolorowy las (skip)
Zadanie nie wygląda na ciekawe. Trzeba pewnie użyć kilku standardowych trudnych rzeczy i jakoś pójdzie. W tym roku nie mogę jechać na finał przez kolizję terminów, więc z zadowoleniem skipnąłem to zadanie.
[5C] Bardzo Ulubiony Ciąg (10-15m w głowie)
Świetne ale zdecydowanie za trudne. Dla koksów byłoby łatwiejsze, gdyby zmniejszyć wartości a[i] do ~100 i pozwolić na dynamika dp[i][suma][stanZaczętychPrzedziałów] w O(N*(N*ai)), ale nie byłoby to dużo gorsze zadanie. Bardzo podoba mi się właściwe rozwiązanie - byłem zadowolony z wpadnięcia na nie i warto było jeszcze kilka minut poświęcić na planowanie implementacji.
[5C] Żarówki (20m na kartce)
Zdecydowanie za trudne. Typowe zadanie ICPC, gdzie można długo nie wpaść na wymagany warunek. Nawet nie próbowałem udowadniać, tylko zaimplementowałem i wysłałem, skoro mamy odsłanianie wyniku. Nie jest tu dużym problemem wymagania znajomości jak policzyć dwumian newtona modulo, bo najpierw trzeba wymyślić rozwiązanie.
[5B] Dzielniki (2h na kartce i bez, potem 2-3h eksperymentowania z kodem)
Fajne, dobrze się bawiłem. Długo myślałem o podzielności przez małe liczby pierwsze i w końcu satysfakcjonujące było wpaść na pomysł badania potęg liczby 4. Super jest, by było z jedno takie zadanie na pracę z kodem, najlepiej właśnie w rundzie weekendowej.
[5B] Kraniki (nie umiałem w 1 dzień)
Długo walczyłem. Myślałem o zamiataniu z góry i z dołu - w obie strony miało to sens i zachowywało się to inaczej. Myślałem o D&C i jump pointerach. Nie wymyśliłem nic lepszego niż log^2 z D&C, więc zamiast tego napisałem pewnie równie szybkie bitsety w O(N^2 / 32). Starczyło na 5/10 punktów, chyba powinno być mniej.
[5A] Monety (1h + niepotrzebne kilka godzin na szukanie szybszego rozwiązania + 2-3h żyłowania)
Najłatwiejsze 5A ever. Już w trakcie konkursu zgadywałem, że organizatorzy nie przewidzieli tak łatwego rozwiązania. Znałem hackenbusha i od razu było dla mnie oczywiste, że możemy robić dynamika po bitach. Dla każdego K niezależnie liczę dp[bit][i][sumaUłamkowa][sumaCałkowita][zaczęteLiczby] w O(M^2 * N^4) czyli razem O(M^2 * N^5) z bardzo małą stałą. Niepotrzebnie myślałem nad lepszą złożonością zamiast od razu zaimplementować. Szkoda, że nie dało się wymusić trudnego rozwiązania z wielomianami, bo użycie ich też przeszło mi przez głowę.
[5A] Autostrada 2 (prawie skip)
Wyglądało absurdalnie trudne. Próbowałem tylko przez chwilę, priorytetyzowałem Kraniki. Super, że było jedno nierobialne zadanie, by nikt przypadkiem nie skończył w sobotę z niedosytem.
Olbrzymie podziękowania dla organizatorów, w szczególności za 50+ stron rozwiązań od razu po konkursie. Najbardziej podobały mi się zadania, których nie udało mi się rozwiązać, bo zazwyczaj miały przecież proste rozwiązanie. Propsy dla autorów, nie propsy dla przypisujących trudności (2A).
[1C] Kto wygrał?
Świetne zadanie na ten slot. Bardzo lubię, gdy łatwe zadania mają naturalną treść i użycie zasad danego konkursu jest dobrym przykładem. Może warto zawsze w treści 1C dodać zdanie/przypis, że należy odsłonić swój wynik po wysłaniu zgłoszenia? Ja chyba o tym zapomniałem.
[1B] Liderzy
Dobra trudność i zadanie, słaba treść. Jakieś straszne podciągi w tak łatwym zadaniu. Pracujesz w sklepie i masz N cukierków o smakach a[i]. Podziel je na mieszanki, każda musi być określona dominującym smakiem czy coś. Swoją drogą, najpierw źle przeczytałem treść i chciałem dzielić na przedziały, nie umiałem.
[1A] Modernizacja Bajtocji (5-10m z kartką)
Super, bardzo podobało mi się rozwiązanie. Ze smutkiem przyznam, że pewnie 1A powinno być łatwiejsze, by zostawić miejsce na rosnącą trudność w ciągu tygodnia. Trudna decyzja: przystępne zadanie dla większego grona czy od razu jakaś zabawa dla czołówki.
[2C] Znaczki pocztowe
Za trudne, ogromny skok trudności z 1C. I wydaje mi się, że znowu rozdawanie cukierków dałoby lepszą treść, jak w 1B.
[2B] Alchemik Bajtazar (kilka sekund)
Mi nie sprawiło przyjemności, bo natychmiastowo widziałem jak zrobić. Ale zadanie ok, właśnie taka powinna być dywizja B. To zadanie mogłoby też iść jako 5C. Byłoby za trudne na taki slot, ale bardziej robialne niż obecne tam zadania.
[2A] Grupa permutacji (nie umiałem w 1 dzień)
Najtrudniejsze 2A ever. Szybko wymyśliłem O(K*N^2) i próbowałem przyśpieszać. Długo też analizowałem jak cykle się ze sobą łączą, by może je utrzymywać lub liczyć LCM czy GCD. Pokonało mnie to zadanie. Fajne rozwiązanie, zaskakujące. Słabo, że trudno jest zrozumieć poprawność. Dostałem aż 6 punktów za bruta - trochę sporo, ale pewnie tak ma być skoro łatwe zadanie.
[3C] Obrazy (2m z kartką)
Ok, dobre na ten slot.
[3B] Żelki (30s)
Ok. Trudno mi ocenić trudność, bo od razu umiałem przez znajomość podobnych zadań. Bardzo lubię następujące: "Wsiadasz na parterze do windy, która ma trzy przyciski: jedź w górę o +A, +B lub +C pięter. Ile z N pięter budynku jest osiągalnych? A,B,C <= 1e6, N <= 1e18."
[3A] Splatanie ciągów (1 dzień, niedokończone)
Dobre trudne zadanie na eliminacje potyczek. Wydaje się na początku absurdalnie trudne, ale robienie przykładów na kartce szybko sugeruje do policzenia f(A,B) potrzebna jest tylko długość B, który prawdopodobnie jest tym krótszym ciągiem. Napisanie bruta to potwierdziło. Następnie wkopałem się w niepotrzebnie skomplikowane rozwiązanie: K-tą liczbę wyniku liczę w O((N/K)^2) z (jak się potem okazało) niepotrzebnymi funkcjami liniowymi i kwadratowymi, a małe K chciałem robić z FFT, ale zakopałem się tam z odejmowaniem źle policzonych przedziałów wewnątrz jednego monotonicznego kawałka. Celowałem w O(N^1.5 * log(N)), a lepiej było skupić się na jakimś D&C+FFT i mieć pewnie O(N*log^2(N)). Ja unikałem D&C, bo w połączeniu z pierwiastkiem byłby to bardzo wolny rozw. Nie wiem czemu nie połączyłem kropek pomiędzy moimi rozwiązaniami, by robić O(N/K * polylog). Dostałem 6 punktów za moje O(suma po (N/K)^2).
[4C] Łamigłówka 3 (kilka sekund)
Wydaje mi się bardzo standardowe i nie zdziwię się, jeśli gdzieś kiedyś było. To jest taki rodzaj zadania (w kontraście do np. 3C), że jest trywialne dla kogoś doświadczonego i może być trudne dla początkującego. Nie ma w tym nic złego, zadania z dywizji C mają być dopasowane do początkujących.
[4B] Desant 3 (nie umiałem w 1 dzień)
Kolejne zadanie po 2A, które mnie pokonało. Trochę głupio, bo zdarzyło mi się w przeszłości wymaksować rundy 1-4. Bardzo kusiło tutaj robić zadanie od tyłu, iterując najpierw końcowy przedział jedynek. Nic z tego nie wyszło. Symulacja od przodu też mi nie poszła, no cóż. Zadanie pewnie za trudne na swój slot, ale bardziej jednak odczuwam swój skill issue.
[4A] Kolorowy las (skip)
Zadanie nie wygląda na ciekawe. Trzeba pewnie użyć kilku standardowych trudnych rzeczy i jakoś pójdzie. W tym roku nie mogę jechać na finał przez kolizję terminów, więc z zadowoleniem skipnąłem to zadanie.
[5C] Bardzo Ulubiony Ciąg (10-15m w głowie)
Świetne ale zdecydowanie za trudne. Dla koksów byłoby łatwiejsze, gdyby zmniejszyć wartości a[i] do ~100 i pozwolić na dynamika dp[i][suma][stanZaczętychPrzedziałów] w O(N*(N*ai)), ale nie byłoby to dużo gorsze zadanie. Bardzo podoba mi się właściwe rozwiązanie - byłem zadowolony z wpadnięcia na nie i warto było jeszcze kilka minut poświęcić na planowanie implementacji.
[5C] Żarówki (20m na kartce)
Zdecydowanie za trudne. Typowe zadanie ICPC, gdzie można długo nie wpaść na wymagany warunek. Nawet nie próbowałem udowadniać, tylko zaimplementowałem i wysłałem, skoro mamy odsłanianie wyniku. Nie jest tu dużym problemem wymagania znajomości jak policzyć dwumian newtona modulo, bo najpierw trzeba wymyślić rozwiązanie.
[5B] Dzielniki (2h na kartce i bez, potem 2-3h eksperymentowania z kodem)
Fajne, dobrze się bawiłem. Długo myślałem o podzielności przez małe liczby pierwsze i w końcu satysfakcjonujące było wpaść na pomysł badania potęg liczby 4. Super jest, by było z jedno takie zadanie na pracę z kodem, najlepiej właśnie w rundzie weekendowej.
[5B] Kraniki (nie umiałem w 1 dzień)
Długo walczyłem. Myślałem o zamiataniu z góry i z dołu - w obie strony miało to sens i zachowywało się to inaczej. Myślałem o D&C i jump pointerach. Nie wymyśliłem nic lepszego niż log^2 z D&C, więc zamiast tego napisałem pewnie równie szybkie bitsety w O(N^2 / 32). Starczyło na 5/10 punktów, chyba powinno być mniej.
[5A] Monety (1h + niepotrzebne kilka godzin na szukanie szybszego rozwiązania + 2-3h żyłowania)
Najłatwiejsze 5A ever. Już w trakcie konkursu zgadywałem, że organizatorzy nie przewidzieli tak łatwego rozwiązania. Znałem hackenbusha i od razu było dla mnie oczywiste, że możemy robić dynamika po bitach. Dla każdego K niezależnie liczę dp[bit][i][sumaUłamkowa][sumaCałkowita][zaczęteLiczby] w O(M^2 * N^4) czyli razem O(M^2 * N^5) z bardzo małą stałą. Niepotrzebnie myślałem nad lepszą złożonością zamiast od razu zaimplementować. Szkoda, że nie dało się wymusić trudnego rozwiązania z wielomianami, bo użycie ich też przeszło mi przez głowę.
[5A] Autostrada 2 (prawie skip)
Wyglądało absurdalnie trudne. Próbowałem tylko przez chwilę, priorytetyzowałem Kraniki. Super, że było jedno nierobialne zadanie, by nikt przypadkiem nie skończył w sobotę z niedosytem.
Olbrzymie podziękowania dla organizatorów, w szczególności za 50+ stron rozwiązań od razu po konkursie. Najbardziej podobały mi się zadania, których nie udało mi się rozwiązać, bo zazwyczaj miały przecież proste rozwiązanie. Propsy dla autorów, nie propsy dla przypisujących trudności (2A).
Poznałem zastosowania bitsetów w zeszłym roku dzięki Twojemu filmowi na YT. Udało mi się dzięki temu wyrwać 3/10 za Kraniki : ) Po ujawnieniu rozwiązań zajrzę do Twojego kodu by zobaczyć jak wygląda ta znacznie szybsza implementacja
@Hubert: Przykro mi to mówić, ale wątpię aby bitsety Ci tu cokolwiek dały. Brut w n^2 dostawał już 3/10 xd. Może nie zrobiłeś tego możliwie najlepiej, bo rzeczywiście raczej słyszałem o dostawaniu 5pkt za nie
@Wojtek: Czyli wychodzi na to, że miałem tragiczny algorytm brutowania. Patrząc na czasy to zmiana na bitsety wciąż dała mi całe dwa punkty (max 0.26s w g2 i 1.47s w g3) : D
Ja dostałem 6/10 w Kranikach za n/64 bez bitsetów - po prostu dla każdego zbioru 64 wierzchołków oddzielnie liczyłem wyniki. Generalnie problem jest nie z czasem, tylko z pamięcią. Podzieliłem dodatkowo przez 2 przez processowanie sufiksów po toposorcie. Więcej nie udało mi się podzielić.
w 5C niewielka zmiana w dół zakresu powodowałaby, że wchodziłoby szybkie FFT, które było pewnie z 4 razy za wolne?
w 5C niewielka zmiana w dół zakresu powodowałaby, że wchodziłoby szybkie FFT, które było pewnie z 4 razy za wolne?