Jak ktoś chce to na chińskich stronkach już można wysyłać

https://qoj.ac/problems?page=54
https://qoj.ac/problems?page=53

@Sebastian: Jak się jest w kategorii "wyjadacza" z setkami zadań rozwiązanych to trudno naprawdę coś zupełnie nowego znaleźć. Nie twierdzę też, że jakoś zadania C wzniosły moją wiedzę na nie wiadomo jaki nowy level - wszystkie koniec końców rozwiązałem. Jednak nawet dla mnie widzę rzeczy z wartością edukacyjną które przeoczyłem.

WIE -> trochę kminy o błądzeniu losowym i wyostrzeniu sobie intuicji co się dzieje w nieskończoności. Fajne było też to, że można było zliczać liczbę krawędzi łopatologicznie lub pomyśleć dwa razy i wyprowadzić prosty wzorek -- poraz kolejny wpadłem w tą pułapkę, że zamiast pomyśleć zacząłem klepać coś oczywistego.

WAL -> bardzo ciekawe zadanie symulacyjno-optymalizacyjne typu: spróbuj czegoś, stwierdz czemu nie działa, popraw dane wejściowe i spróbuj ponownie. Trochę mi zajeło się przekonanie, żeby skierować moje myśli w tym kierunku. Na początku na siłę szukałem jakiegoś układu równań modulo.

LAM -> Kilka fajnych obserwacji prowadzących do standardowego rozwiązania. Pierwsza to, że kształty w rogach zawsze będą takie same. Druga, że klocek z tego samego pola zawsze trafi na to samo pole, czyli tworzymy sobie graf gdzie wierzchołkami są pojedyńcze pola na planszy. Trzecia obserwacja, że każdy wierzchołek w tym grafie ma stopień dwa to znaczy że mamy zbiór rozłącznych cykli, inaczej graf permutacji. Skąd dochodzimy do standardowego problemu potęgowania permutacji.

Fajne było też to, że jeśli nawet nie znało się tych trików z rozbiciem cyklowym i permutacjami to odrabiając zadanie domowe z FOT można było zrobić LAM, nie robiąc FOT.

FOT -> wariacja standardowego problemu sortowania z niestandardową operacją dokonywania swap'ów. Jak ktoś nie zna można dodać do portfolio bardzo przydatny trick, że dowolne przesunięcie cykliczne da się uzyskać za pomocą operacji "inverse" ciągu (dość często wykorzystywany trik przy takich zadniach)

MUZ- > niby zachłanny algorytm bez historii. Ale sam przegapiłem ten ciekawy fakt ze szkicu rozwiązań:

"...Dla ciekawskich pozostawiamy również udowodnienie następującej własności: każde optymalne rozwiązanie zawiera prefiks dodatnich liczb całkowitych poza jedną..."

PUN -> bez historii.

PAL -> niby próbne, ale trochę czasu mi zeszło by to zrobić. Równie dobrze mogło by być pewnie na równi z 3B.

@Wladyslaw: nie zgodzę się z pierwszą częścią, wszystkie koncepcje do zadań C (poza WIE) widziałem już wcześniej w jakichś zadaniach, a i tak musiałem spędzić dłuższą chwilę na odkryciu i zaimplementowaniu ich rozwiązań na nowo. Ja to bym chciał zobaczyć w dywizji C więcej zadań opartych na wykombinowaniu jakiegoś dowodu, tak jak w 1A - konkretny dowód pewnej własności jakiegoś obiektu nie jest często spotykany, natomiast idea która za nim stoi może się generalizować na inne zadania i przydać się w przyszłości. Inną sprawą jest możliwość konstrukcji takich zadań.

Również dziękuję wszystkim organizatorom!

Wspaniała zabawa pomimo wyjętego tygodnia z życia! ;-)

Zgadzam się, że zadania w C były dość trudne tylko ja uważam to za duży plus. Zadania na przeczytaj, naklep, zapomnij są stratą czasu gdyż niczego nowego nie nauczą. Najfajniejsze są zadania które albo zostaną rozwiązane dużym nakładem sił albo nie zostaną rozwiązane, lecz po zakończeniu poznanie rozwiązania wnosi coś ciekawego na "przyszłość".

Może rozwiązaniem dla początkujących jest osobny ranking dla początkujących?

Np. Przy rejestracji dodajemy osobny select box z pytaniem jak obiektywnie oceniasz swój skillset? Np. "aktywny wyjadacz", "wyjadacz na emeryturze", "aktywny zawodnik średniego szczebla", "emerytowany zawodnik średniego szczebla", "początkujący z mniej niż 50 zadaniami w życiu". Następnie dodajemy filtr na rankingu po kategoriach i każdy może się porównać do ludzi o podobnym skillu. Pewnie będzie mniej boleć, że się nie rozwiązało jakiś zadań. A wręcz może motywować do ciułania punktów brutami. Sam się łapie często na tym, że jeśli nie jestem wstanie napisać poprawnego rozwiązania to nawet bruta nie piszę za 1-3 punkty.

Przyłączam się do prośby i nieśmiało chciałem zauważyć, że zadań z zeszłorocznych OI i OIJ również nie ma na szkopule (ktoś dba o ten serwis, czy może potrzebne jest więcej rąk do pracy?).

Dołączam się do pytania. Zadania na Szkopule są potrzebne :)

Czy zadania beda dostepne na testerce? W serwisie Szkopul brakuje rowniez zadan z potyczek z zeszlego roku.

I jeszcze raz dziekuje za konkurs i za swietne zadania.

Stara strona spadła z rowerka i na razie jeszcze nie odbyły się próby resuscytacji. Kiedyś wróci, ale niestety nie ma to jakoś bardzo wysokiego priorytetu.

@Hubert Banaszewski tak. Wczoraj, jak Wojtek podeł wzór, nadal myślałem, że mimo jego prostoty to było coś bardziej skomplikowanego. A dziś przeglądając pdfa i widząc tak oczywisty sposob liczenia, uznałem, że mi łeb wapnieje;-)

Jak dla mnie to 4C może i było implementacyjne, ale mój kod ma 130 niezbyt skompresowanych linii (w tym jakieś 25 templatek, obsługi testcasow itd.), więc wydaje mi się, że warto było pomyśleć jak to napisać.


Edit: Może są trochę skompresowane :)

https://potyczki.mimuw.edu.pl/archiwum/

Zgłaszam, że większość linków, a w szczególności tych do rankingów przed 2014 rokiem (czyli przed sio2), nie działa.

Mam taką samą sytuację jak przedmówca - obecnie Potyczki to obecnie praktycznie jedyne zawody algorytmiczne, w których staram się uczestniczyć. Ciekawe zadania i dużo czasu do namysłu (ale bez przesady, bo to tylko tydzień z życiorysu) to jest to, co mi bardzo odpowiada. Dziękuję organizatorom za kolejną możliwość sprawdzenia swoich umiejętności (które jak zwykle okazały się zbyt niskie :D ).

Czy ma ktos zadania z Distributed Code Jam'ow? Jestem strasznie ciekawy jak wygladaly a nie moglem nigdzie ich znalezc.

Jak uświadomiłem sobie rozwiązanie zadania 4C, to już się zacząłem zastanawiać co organizatorzy szykują na weekend w dywizji C... U mnie wyszło nawet blisko 400 linii. Na weekend takie obszerne w implementacji zadanie byłoby jednak całkiem w porządku, razem z WAL.

Zadanie WIE było po prostu trudne do wymyślenia - przynajmniej dla mnie, prawdopodobnie już zresztą zmęczonego wcześniejszym wysiłkiem umysłowym w trakcie wcześniejszych rund. A co dopiero dla początkujących - w 2020 i 2021 były w dywizji C zadania weekendowe "na pomysł", ale zdecydowanie bardziej przystępne.