Ale krótkie te rozwiązania piszecie! Może jeszcze trzeba wziąć pod uwagę średnią długość linijek? ;)

Moje:

29 ZAB
40 ELE
44 SAM
48 WYB
59 RAN
62 KOL
64 CUK
70 LIC
70 DAG
76 MAL
80 BST
111 WYC
121 TRZ *
154 SEN
200 TEK
220 OGR *
295 MIN
341 BAL
599 PRO *

No spoko, ale akurat Bajta i Bajcia nie brzmią jak kompilujące się imiona. I zapewnie rzadko ktoś użyje postaci królowej Bajtoliny, bo historycznie częściej był król.

Jak kiedyś robiłem dużo zadań na konkursy, to przeważnie używałem niedźwiedzia o imieniu Limak i był w 90% moich zadań. Pewnie większość osób chętniej tworzy postać, z którą jakoś się utożsamia, więc jest więcej męskich bohaterów zadań bo przeważnie autorzy są tej płci.

I absolutnie nie widzę potrzeby używania imion, które brzmią niepolsko. Przecież nie będziemy od Francuzów wymagali, by używali Bajtazara w swoich zadaniach.

W rozwiązaniu trójkowym liczba węzłów też jest niemalejąca. Dla k = 10^9 wychodzi chyba dokładnie 59.

Ale co ciekawe, dla większych k drabinka trójkowa daje mniej węzłów.

Dla k = 10^18 mamy 116 węzłów w drabince trójkowej i 120 w binarnej.
Dla k = 10^100 mamy już 629 węzłów w trójkowej i 668 w binarnej.

To dowód wyższości liczby 3 nad 2 ;)

Dzięki za dobrą zabawę, moim faworytem również jest DAG (choć OGR też było super, mimo że nie zrobiłem xD)

Podoba mi się taki scenariusz. Tylko ograniczyłbym się wtedy do jednej rundy (jednego tygodnia). I koniecznie zastosowałbym ujawnianie wyniku, bo czekać tydzień w niepewności to dość przykre.

Bardziej szedłbym w scenariusz gdzie runda polega na tym, że masz ~tydzień na zrobienie ~5 zadań. I tak np. 3-4 tygodnie pod rząd.
Problem z krótką rundą jest taki, że
A. trudno znaleźć taki czas, by wszystkim termin pasował. Natomiast w ciągu tygodniu, jest większe prawdopodobieństwo że wiekszości uda się sumarycznie wygospodarować powiedzmy te +20h na aktywne lub pasywne kminienie.
B. większość z nas potrzebuje więcej czasu by zrobić jakieś nowe ciekawe zadanie. Więc i tak zadanka z mojej perspektywy by się marnowały, albo trudność zadań musiałaby spaść - a tego raczej nikt nie chce ;-)

Potwierdzam.

Trochę dziwnie się czuję, gdy w zadaniach spotykam głównie (albo wyłącznie) bohaterów męskich. Może by czasem zamiast króla Bajtura pojawiła się królowa Bajtolina, zamiast Bajtka i Bajtusia - Bajta i Bajcia? Nie trzeba by tu się ograniczać do imion polskich: w Bajtocji mogłaby zagościć Francuzka Baitoise czy Brytyjka Elisabit.

Standardowe zadania na zwykłych rundach też mogą być fajne i mieć wartość edukacyjną - zwłaszcza, że nie wszyscy ludzie rozwiązują wszystkie konkursy z ostatnich X lat i mają różne "triki" w małym palcu albo mają bibliotekę wszystkich możliwych algorytmów pod ręką :-)

Co więcej zadanie LIC ma fajny potencjał w postaci prostego bruta za 3 pkt, ktoś mógł w stan wrzucić pełną bitmaskę 9 cyfr, czyli 512, i dostać ~8pkt. A można było zauważyć że wystarczy trzymać liczbę różnych LCM'ów, który jest 48(?), i dopiero wtedy np. dostać maksa. Ogólnie jednak zauważyłem tendencje do oceniania zdań ACM'owo, gdzie albo dostajesz 10pkt albo coś bliskiego zeru - a szkoda, bo bardziej zróżnicowana punktacja mogłaby dodać pikanterii.

P.S. Dla mnie LIC i MAL nie różnią się w swojej standardowości. MAL to też zwykły dynamik na zliczanie, gdzie głowna trudność to zdefiniowanie "stanu", zliczanie "negacji" plus jakaś tam "symetria".


Być może warto było zrobić LIC [Easy] i LIC [Hard] na próbnej, i jedynie zmienić ograniczenia. Wtedy zadanie już by tak nie odstraszało nowicjuszy ;-)

Może zostawić tylko rundę 5. jako całodobową (całoweekendową), a resztę rund ograniczyć do jakiegoś krótkiego slotu, na przykład 12÷15?

Dzięki za kolejną serię super zadań w tym roku. W moim osobistym rankingu wygrywa DAG (swoją drogą, czy ktoś wie, czy rozwiązanie z Fibbonaccim jest optymalne / optymalne w granicy k -> inf?).

Zgadzam się też z opinią, że B było trudniejsze w tym roku (niż '18, '19); próg na koszulkę pewnie wyniesie < 75 = całe C + 1B + prosty brut albo dwa.
Myślę, że nieco prostsze zadania, lepiej różnicujące >150 uczestników, którzy w tym roku dostaną 70 - 85 mogłyby być dla nich lepszą zabawą. Imo optymalny próg na koszulkę byłby ok. 90, tj. C + B/2.

Dowód poprawności rozw. przez programowanie dynamiczne.

Niech X to zbiór szukanych (nazwijmy je właściwymi) podzbiorów zbioru A.
Zał, że dokładamy element p do A gdzie p >= max(A), i chcemy zaktualizować X. W zaktualizowanym zbiorze X będą te zbiory co wcześniej i dodatkowo pewne podzbiory A z dodanym elementem p.

Jeżeli B jest podzbiorem A i sum(B) <= p - 2 to wart. p - 1 nie da się utworzyć przez dodanie p, czyli nie da się utworzyć szukanego zbioru ze zbioru B.
Dalej zał, że sum(B) >= p - 1.

Dołożenie p do właściwego podzbioru B zbioru A spowoduje utworzenie szukanego zbioru, jeżeli sum(B) >= p - 1 - każda z liczb z przedziału [p + 1, sum(B) + p] zostanie utworzona poprzez dodanie do p pewnego podzbioru B, a liczby z przedziału [1, p - 1] są utworzone przez podzbiory B bo sum(B) >= p - 1.

Dołożenie p do niewłaściwego podzbioru B zbioru A nigdy nie spowoduje utworzenia szukanego zbioru.

Lemat. Niech B = {b_1, b_2, ..., b_k}, b_1 <= b_2 <= ... <= b_k.
Jeżeli każdą z sum z przedziału [1, b_k] da się utworzyć przy pomocy podzbiorow B to każdą sumę z [1, sum(B)] też da się utworzyć.
Dowod lematu. Każdą sumę z przedziału [1, b_k] da się utworzyć => każdą sumę z przedziału [1, b_l] da się utworzyć przy pomocy {b_1, b_2, ..., b_l} dla 1 <= l < k.
Wtedy dla każdego 1 <= l <= k każdą sumę z przedziału [b_k + b_(k-1) + ... b_(l+1), b_k + b_(k-1) + ... b_(l+1) + b_l - 1] też da się utworzyć po dodaniu do b_k + b_(k-1) + ... b_(l+1) liczby z przedziału [1, b_l] czyli pewnego podzbioru {b_1, b_2, ..., b_l}.

Z lematu wynika, że dla niewłaściwego zbioru B istnieje liczba z przedziału [1, b_k - 1], której nie da się utworzyć, ale b_k <= p, czyli nie da się jej utworzyć też po dodaniu p do B.

Programowane dynamiczne pisałem podobne jak wyżej, przetwarzam liczby z A w kolejności rosnącej. W dp[i] trzymam ilość sposobów utworzenia poprawnego ciągu dającego sumę i (tablica ma rozmiar 5000). Dodatkowo trzymam zmienną przechowującą liczbę wszystkich szukanych zbiorów.

Startując jako student w latach 2005-2010 pamiętam, że rundy zdalne to był istny maraton - dosłownie 24h/dobę przez prawie tydzień - niemniej jednak wspaniała zabawa i warto było wyrywać tydzień z życia. Obecnie niewiele się zmieniło w intesywności zawodów jednak już nie wiodę życia beztroskiego studenta, który może się na tydzień zamknąć przed komputerem. Na "szczęście" w tym roku potyczki nałożyły się z moim urlopem i jakoś "wywalczyłem" u rodziny trochę czasu na B+C. Przyznam, że pomimo upływu lat nadal świetnie się bawię kminiąc zadanka. Wielkie brawa dla organizatorów za to! Dziękuję!

W tym miejscu pytanie, czy nie dałoby się dostosować formuły zawodów do ludzi z mniejszą ilością wolnego czasu? Bo jednak trochę szkoda, że nawet nie miałem okazji porządnie wczytać się w TEK oraz TRZ. Bez urlopu to już przy MIN musiałbym odpuścić. Rozumiem, że intensywność to w pewnym sensie wizytówka tych zawodów. Z drugiej strony duże marnotractwo świetnych zadań, bo rozwiązywanie zadań "po zawodach" to jednak nie to samo odczucie. Przede wszystkim brak tej motywacji by cisnąć.

W takim razie rzadka drabinka binarna wygrywa, daje najwięcej 60 (od 2^28+2^29=805306368 do 2^30=1073741824). Ma tą jeszcze zaletę że ilość węzłów jest niemalejąca przy rosnącym k.

Ciekaw jestem jeszcze jaki był najgorszy przypadek dla rozwiązania trójkowego Michała Miodka.

Chociaż poprzednia odpowiedź mówi o tych konkretnie zadaniach, to nie odnosi się do, powiedzmy, całości. Czasem konieczne/wygodne jest napisanie 200+ linijek kodu i nie jest to wcale nic strasznego :) Pewnie często da się kod skrócić, ale nie zawsze jest to łatwe, a z reguły również niepotrzebne. Ale bardzo długie zadania nie pojawiają się bardzo często ;)