polski
Latest posts
Też 9802
Myślałem, że to ze mną jest coś nie tak i za każdym razem klikałem nie to co trzeba
Alternatywne rozwiązanie nie używające diagramów Younga (acz z lekkim wsparciem OEIS)
Klepiemy bruta, z jego pomocą można łatwo zauważyć, że n=a*b - (s+1 choose 2), gdzie s = a+b-1-c. Wrzucenie wyników wprost do OEIS do niczego ciekawego mnie nie doprowadziło.
~~~Case s = 0
Jeżeli zwizualizujemy sobie permutację jako punkty (i, p[i]), a na każdym z nich napiszemy długość najdłuższego ciągu rosnącego zaczynającego się na tej pozycji, to możemy zauważyć że rzutowania tych wartości na osie przypominają coś w stylu wielowymiarowych ciągów catalana, tzn i-te wystąpienie j-tego symbolu musi być przed i-tym wystąpieniem (j-1)-ego symbolu (symbole będę oznaczał jako litery alfabetu). Sugeruje to że wyniki powinny być kwadratami jakiegoś wielowymiarowego uogólnienia liczb catalana, i faktycznie jak spojrzymy na bruta to są kwadratami. Wzięcie pierwiastków i wrzucenie tego w OEIS prowadzi nas do odpowiedniego ciągu oraz wzoru:
https://oeis.org/A060854
T_{n, m} = (m*n)! * 0!..(n-1)! / (m!..(m+n-1)!)
T_{a, b}^2 jest wynikiem w tym przypadku.
~~~Case s > 0
Wyniki bruta nie są w tym przypadku kwadratami, ale ponownie patrząc na rzutowania możemy zgadnąć, że wynik to produkt ilości dwóch następujących obiektów:
O1) czegoś w stylu uogólnienia catalan convolution (https://codeforces.com/blog/entry/87585), gdzie i-tego symbolu (0-indexed) jest s-i mniej, ale udajemy że te brakujące symbole są już na ustalonych pozycjach na początku ciągu
dla np. a=4, b=5, s=2 mamy ustalony początek ciągu AAB, i chcemy odpowiednio dostawić AAA, BBBB, CCCCC, DDDDD tak by warunek z catalana był zachowany. (możliwe że tutaj trzeba odwrócić semantykę a z b etc.)
O2) też jakiś wariant catalana, gdzie usuwamy >pierwszych< s-i kopii i-tego symbolu od końca: dla np. a=4, b=5, s=2 mamy symbole AAAAA,BBBBB,_CCCC,__DDD, przed i-tym B musi być i kopii A, ale przed i-tym C musi być (i+1) kopii B, tak samo dla D.
Jeśli chodzi o weryfikację tych faktów to zadowoliłem się zgodnością z brutem. Te interpretacje są o tyle fajne, że pozwalają na napisanie bruta w złożoności b^a, co pomoże w dalszej części rozwiązania.
~~~
Zauważmy, że T_{n,m} = (n*m choose m,m,m,...,m) / f_n(m)
gdzie f_n(m)=stała*(m+1)^(n-1)..(m+n-1) jest wielomianem od m, stopnia O(n^2), a choose oznacza multinomial coefficient.
Porównując ze zwykłym catalanem, oraz zwykłym catalan convolution możemy zauważyć, że wszystkie te wzorki są postaci
(ilość sposobów na wybranie kolejności elementów bez uważania na ograniczenia) / (jakiś wielomian)
Sugeruje to, że wzór na O1 jest postaci
(n choose b-s,b-s+1,..,b-1,b,b,...,b) / wielomian_{a, s}(b).
Możemy więc próbować interpolować te wielomiany (brut wystarczał do a <= 6). Okazuje się, że istnieją one zarówno dla O1, jak i O2. Rozkładamy je na czynniki i próbujemy znaleźć jakąś prawidłowość. Ze współczynnikiem wiodącym miałem trochę problemów, ale zbiory miejsc zerowych są dość regularne i da się je odgadnąć.
Współczynniki wiodące. Dla s=0 możemy je łatwo wyznaczyć, gdyż w tym przypadku ilość O1 i O2 do T_{n, m}. Okazuje się, że dla s=a-1 współczynnik wiodący jednego z O1/O2 (nie pamiętam już którego) jest taki sam* jak dla s=0, a dla drugiego jest dość podobny (trzeba pomnożyć przez 2^{a choose 2} 0!..(a-1)!).
Wyznaczenie innych współczynników wiodących jest już łatwe - gdy chcemy poznać współczynnik wiodący w wielomianie, znając jego miejsca zerowe, to wystarczy obliczyć wynik dla tylko jednej wartości, a to możemy zrobić dla b=s+1, korzystając z wcześniej obliczonych wartości dla a'=b, b'=a. (zadanie jest symetryczne ze względu na zamianę a z b).
(*wzorki dla tych miejsc zerowych zawierają liczby postaci x/2, więc dla uproszczenia domnażałem je przez jakąś potęgę dwójki by liczby były całkowie, więc możliwe że te współczynnki jednak różnią się o jakąś potęgę dwójki, ale to offtop)
Klepiemy bruta, z jego pomocą można łatwo zauważyć, że n=a*b - (s+1 choose 2), gdzie s = a+b-1-c. Wrzucenie wyników wprost do OEIS do niczego ciekawego mnie nie doprowadziło.
~~~Case s = 0
Jeżeli zwizualizujemy sobie permutację jako punkty (i, p[i]), a na każdym z nich napiszemy długość najdłuższego ciągu rosnącego zaczynającego się na tej pozycji, to możemy zauważyć że rzutowania tych wartości na osie przypominają coś w stylu wielowymiarowych ciągów catalana, tzn i-te wystąpienie j-tego symbolu musi być przed i-tym wystąpieniem (j-1)-ego symbolu (symbole będę oznaczał jako litery alfabetu). Sugeruje to że wyniki powinny być kwadratami jakiegoś wielowymiarowego uogólnienia liczb catalana, i faktycznie jak spojrzymy na bruta to są kwadratami. Wzięcie pierwiastków i wrzucenie tego w OEIS prowadzi nas do odpowiedniego ciągu oraz wzoru:
https://oeis.org/A060854
T_{n, m} = (m*n)! * 0!..(n-1)! / (m!..(m+n-1)!)
T_{a, b}^2 jest wynikiem w tym przypadku.
~~~Case s > 0
Wyniki bruta nie są w tym przypadku kwadratami, ale ponownie patrząc na rzutowania możemy zgadnąć, że wynik to produkt ilości dwóch następujących obiektów:
O1) czegoś w stylu uogólnienia catalan convolution (https://codeforces.com/blog/entry/87585), gdzie i-tego symbolu (0-indexed) jest s-i mniej, ale udajemy że te brakujące symbole są już na ustalonych pozycjach na początku ciągu
dla np. a=4, b=5, s=2 mamy ustalony początek ciągu AAB, i chcemy odpowiednio dostawić AAA, BBBB, CCCCC, DDDDD tak by warunek z catalana był zachowany. (możliwe że tutaj trzeba odwrócić semantykę a z b etc.)
O2) też jakiś wariant catalana, gdzie usuwamy >pierwszych< s-i kopii i-tego symbolu od końca: dla np. a=4, b=5, s=2 mamy symbole AAAAA,BBBBB,_CCCC,__DDD, przed i-tym B musi być i kopii A, ale przed i-tym C musi być (i+1) kopii B, tak samo dla D.
Jeśli chodzi o weryfikację tych faktów to zadowoliłem się zgodnością z brutem. Te interpretacje są o tyle fajne, że pozwalają na napisanie bruta w złożoności b^a, co pomoże w dalszej części rozwiązania.
~~~
Zauważmy, że T_{n,m} = (n*m choose m,m,m,...,m) / f_n(m)
gdzie f_n(m)=stała*(m+1)^(n-1)..(m+n-1) jest wielomianem od m, stopnia O(n^2), a choose oznacza multinomial coefficient.
Porównując ze zwykłym catalanem, oraz zwykłym catalan convolution możemy zauważyć, że wszystkie te wzorki są postaci
(ilość sposobów na wybranie kolejności elementów bez uważania na ograniczenia) / (jakiś wielomian)
Sugeruje to, że wzór na O1 jest postaci
(n choose b-s,b-s+1,..,b-1,b,b,...,b) / wielomian_{a, s}(b).
Możemy więc próbować interpolować te wielomiany (brut wystarczał do a <= 6). Okazuje się, że istnieją one zarówno dla O1, jak i O2. Rozkładamy je na czynniki i próbujemy znaleźć jakąś prawidłowość. Ze współczynnikiem wiodącym miałem trochę problemów, ale zbiory miejsc zerowych są dość regularne i da się je odgadnąć.
Współczynniki wiodące. Dla s=0 możemy je łatwo wyznaczyć, gdyż w tym przypadku ilość O1 i O2 do T_{n, m}. Okazuje się, że dla s=a-1 współczynnik wiodący jednego z O1/O2 (nie pamiętam już którego) jest taki sam* jak dla s=0, a dla drugiego jest dość podobny (trzeba pomnożyć przez 2^{a choose 2} 0!..(a-1)!).
Wyznaczenie innych współczynników wiodących jest już łatwe - gdy chcemy poznać współczynnik wiodący w wielomianie, znając jego miejsca zerowe, to wystarczy obliczyć wynik dla tylko jednej wartości, a to możemy zrobić dla b=s+1, korzystając z wcześniej obliczonych wartości dla a'=b, b'=a. (zadanie jest symetryczne ze względu na zamianę a z b).
(*wzorki dla tych miejsc zerowych zawierają liczby postaci x/2, więc dla uproszczenia domnażałem je przez jakąś potęgę dwójki by liczby były całkowie, więc możliwe że te współczynnki jednak różnią się o jakąś potęgę dwójki, ale to offtop)
Ostatnia puszka energetyka chyba była zbędna. Dlatego, żeby wyszło z tego coś pożytecznego, niech tu będzie feedback do zadań (trochę długi, ale mam nadzieję, że przydatny):
Zadania bardzo mi się podobały, wielkie podziękowania dla organizatorów! Napiszę kilka słów o wybranych zadaniach:
1A – miałem rozwiązanie w O(n³), smutne, że wiele błędnych rozwiązań przeszło wszystkie testy. Nie do końca wiadomo, co z tym zadaniem zrobić – wydaje się, że nie da się odsiać wszystkich błędnych rozwiązań, jednocześnie akceptując poprawne. Mimo to, cieszę się, że udało mi się rozwiązać je w „uczciwej” złożoności – według mnie jedno z najładniejszych zadań w konkursie.
1B – dość oczywiste zadanie (co nie jest złe) z bardzo życiowym warunkiem xd. Może warto byłoby dać nieco mniejsze ograniczenia, bo początkujący mogli mieć problem ze zmieszczeniem się w limicie czasowym.
2B – ciekawe zadanie, moim zdaniem najlepsze z grupy 1-4B.
2A – najbardziej standardowe zadań typu A (miałem rozwiązanie FFT + D&C w O(n log² n)). Główną obawą było to, czy nie pojawią się błędy związane z precyzją. Na szczęście nie było problemów.
3A – najlepsze zadanie konkursu. Wymyślanie zajęło mi >5-6 godzin, a przez pierwsze 3 godziny byłem przekonany, że rozwiązanie wymaga flow xd. Spostrzeżenie, że wystarczy rozważyć tylko 2 możliwości dotyczące pierwszego elementu, jest bardzo eleganckie i nieoczywiste.
3B – dobre zadanie. Cieszę się, że nie zabrało mi zbyt dużo czasu, bo mogłem w pełni skupić się na 3A xd.
4A – interesujące zadanie, moim zdaniem znacznie łatwiejsze niż 3A. Cieszę się, że nie było problemów z TL (widocznie trudno wymyślić test lepszy niż losowy).
4B – zadanie, na które poświęciłem najwięcej czasu na implementację i debugowanie :(. Sama idea jest dobra, ale to zdecydowanie bardziej zadanie implementacyjne. Może warto byłoby rozdzielić 4A i 4B na różne dni, bo oba dotyczą struktur danych. Zgadzam się z Wojtechem, że 5 punktów za brute force to za dużo.
5B – oba zadania były ciekawe, może trochę łatwiejsze, niż powinny być (przynajmniej w porównaniu z zeszłym rokiem).
5A LIS – Z jednej strony fajnie, że jest tak wiele grup, ale z drugiej strony to prowokuje do pisania oddzielnych rozwiązań dla każdej z nich (i nie powiedziałbym, że rozwiązanie dla którejkolwiek grupy poza ostatnią zasługuje na oznaczenie 5A). Wydaje mi się, że w mniejszych ograniczeniach to zadanie mogłoby pojawić się we wcześniejszych rundach (bardziej standardowe, ale też mają swoje miejsce), a w tej rundzie zamiast niego mogłoby być 3A. Ale moje rozwiązanie wciąż się testuje, więc nie będę jeszcze za dużo narzekać xd.
5A GLA – zadanie, z którym przez ostatnie 2 dni przeżyłem całe życie xd. Dość szybko sprowadziłem je do liczenia diagramów Younga, ale potem przez 10 godzin nie zrobiłem żadnego postępu :(. Niestety, nic nie udało się wygooglować (choć na próby poszło >2 godziny), wydaje się, że nikt nie bada sposobów ich liczenia, albo to po prostu skill issue :). Wiedziałem, że odpowiedź będzie miała formułę, ale zupełnie nie rozumiałem, jak ją znaleźć. Jeśli ktoś z uczestników rozwiązał to, znajdując formułę, to może podzielić się, jak ją znalazł?
Uważam, że 3 punkty za c = a + b - 1 to za dużo. Po pierwsze, to dość znany fakt, który niewiele pomaga w rozwiązaniu, a po drugie, odpowiedź można było znaleźć w OEIS. Niemniej jednak, autorskie rozwiązanie jest bardzo piękne (choć nadal nie rozumiem, jak na to wpaść bez wcześniejszej znajomości).
Dodatkowe uwagi
Bardzo dobre treści, wszystko było zrozumiałe nawet bez tłumacza. Osobne podziękowania za szczegółowe wyjaśnienia i rysunek Bajtozaura!
Może warto dodawać więcej opisów grup, jeśli nie ułatwiają znacząco rozwiązania zadania (a może nawet i w takim przypadku).
Nie jestem pewien, czy ograniczenia 5e4 w prawie wszystkich zadaniach to dobry pomysł. Rozumiem, że to ma swoje zalety (nie sugeruje złożoności, zachowuje spójny styl treści), ale w zadaniach 2A i 4A bardziej skłaniało to do próby oddania rozwiązania kwadratowego.
Jeszcze raz dziękuję wszystkim autorom i organizatorom, miałem ogromną frajdę!
Zadania bardzo mi się podobały, wielkie podziękowania dla organizatorów! Napiszę kilka słów o wybranych zadaniach:
1A – miałem rozwiązanie w O(n³), smutne, że wiele błędnych rozwiązań przeszło wszystkie testy. Nie do końca wiadomo, co z tym zadaniem zrobić – wydaje się, że nie da się odsiać wszystkich błędnych rozwiązań, jednocześnie akceptując poprawne. Mimo to, cieszę się, że udało mi się rozwiązać je w „uczciwej” złożoności – według mnie jedno z najładniejszych zadań w konkursie.
1B – dość oczywiste zadanie (co nie jest złe) z bardzo życiowym warunkiem xd. Może warto byłoby dać nieco mniejsze ograniczenia, bo początkujący mogli mieć problem ze zmieszczeniem się w limicie czasowym.
2B – ciekawe zadanie, moim zdaniem najlepsze z grupy 1-4B.
2A – najbardziej standardowe zadań typu A (miałem rozwiązanie FFT + D&C w O(n log² n)). Główną obawą było to, czy nie pojawią się błędy związane z precyzją. Na szczęście nie było problemów.
3A – najlepsze zadanie konkursu. Wymyślanie zajęło mi >5-6 godzin, a przez pierwsze 3 godziny byłem przekonany, że rozwiązanie wymaga flow xd. Spostrzeżenie, że wystarczy rozważyć tylko 2 możliwości dotyczące pierwszego elementu, jest bardzo eleganckie i nieoczywiste.
3B – dobre zadanie. Cieszę się, że nie zabrało mi zbyt dużo czasu, bo mogłem w pełni skupić się na 3A xd.
4A – interesujące zadanie, moim zdaniem znacznie łatwiejsze niż 3A. Cieszę się, że nie było problemów z TL (widocznie trudno wymyślić test lepszy niż losowy).
4B – zadanie, na które poświęciłem najwięcej czasu na implementację i debugowanie :(. Sama idea jest dobra, ale to zdecydowanie bardziej zadanie implementacyjne. Może warto byłoby rozdzielić 4A i 4B na różne dni, bo oba dotyczą struktur danych. Zgadzam się z Wojtechem, że 5 punktów za brute force to za dużo.
5B – oba zadania były ciekawe, może trochę łatwiejsze, niż powinny być (przynajmniej w porównaniu z zeszłym rokiem).
5A LIS – Z jednej strony fajnie, że jest tak wiele grup, ale z drugiej strony to prowokuje do pisania oddzielnych rozwiązań dla każdej z nich (i nie powiedziałbym, że rozwiązanie dla którejkolwiek grupy poza ostatnią zasługuje na oznaczenie 5A). Wydaje mi się, że w mniejszych ograniczeniach to zadanie mogłoby pojawić się we wcześniejszych rundach (bardziej standardowe, ale też mają swoje miejsce), a w tej rundzie zamiast niego mogłoby być 3A. Ale moje rozwiązanie wciąż się testuje, więc nie będę jeszcze za dużo narzekać xd.
5A GLA – zadanie, z którym przez ostatnie 2 dni przeżyłem całe życie xd. Dość szybko sprowadziłem je do liczenia diagramów Younga, ale potem przez 10 godzin nie zrobiłem żadnego postępu :(. Niestety, nic nie udało się wygooglować (choć na próby poszło >2 godziny), wydaje się, że nikt nie bada sposobów ich liczenia, albo to po prostu skill issue :). Wiedziałem, że odpowiedź będzie miała formułę, ale zupełnie nie rozumiałem, jak ją znaleźć. Jeśli ktoś z uczestników rozwiązał to, znajdując formułę, to może podzielić się, jak ją znalazł?
Uważam, że 3 punkty za c = a + b - 1 to za dużo. Po pierwsze, to dość znany fakt, który niewiele pomaga w rozwiązaniu, a po drugie, odpowiedź można było znaleźć w OEIS. Niemniej jednak, autorskie rozwiązanie jest bardzo piękne (choć nadal nie rozumiem, jak na to wpaść bez wcześniejszej znajomości).
Dodatkowe uwagi
Bardzo dobre treści, wszystko było zrozumiałe nawet bez tłumacza. Osobne podziękowania za szczegółowe wyjaśnienia i rysunek Bajtozaura!
Może warto dodawać więcej opisów grup, jeśli nie ułatwiają znacząco rozwiązania zadania (a może nawet i w takim przypadku).
Nie jestem pewien, czy ograniczenia 5e4 w prawie wszystkich zadaniach to dobry pomysł. Rozumiem, że to ma swoje zalety (nie sugeruje złożoności, zachowuje spójny styl treści), ale w zadaniach 2A i 4A bardziej skłaniało to do próby oddania rozwiązania kwadratowego.
Jeszcze raz dziękuję wszystkim autorom i organizatorom, miałem ogromną frajdę!
Ja bym głosował za jawniejszym mówieniem jakie są podzadania, bo to trochę guesswork co koniec końców dostanie punkty, a co nie. W LIS były ładnie rozpisane, ale straciłem dużo czasu na 1) żyłowanie bruta w 4A, 2) zrobienie GLA dla 2<=a<=6 i obie te rzeczy dały finalnie 0 punktów. Gdybym znał zawczasu opisy paczek, to bym wiedział, że nie ma sensu, a raczej było sensownym mieć nadzieję, że oba coś dadzą.
I trochę się sprzeciwię opiniom, że sensowna punktacja za bruty. 0 pkt za O(n^2 log n) w 4A to jakaś pomyłka. 4 czy tam 5 za bruta w 4B też. Ten brut do 4B zajmuje kilka minut, a całe zadanie zajęło mi około 10h roboty. Punktacja powinna jakoś odzorowywać potrzebny wysiłek, a tutaj pierwsze 10 minut dawało 4 pkt, a na zdobycie kolejnych 6 trzeba się niemiłosiernie męczyć wiele godzin?
Oczywiście wielkie dzięki za organizację, bardzo fajne zadania. Szczególnie 3A moje ulubione.
I trochę się sprzeciwię opiniom, że sensowna punktacja za bruty. 0 pkt za O(n^2 log n) w 4A to jakaś pomyłka. 4 czy tam 5 za bruta w 4B też. Ten brut do 4B zajmuje kilka minut, a całe zadanie zajęło mi około 10h roboty. Punktacja powinna jakoś odzorowywać potrzebny wysiłek, a tutaj pierwsze 10 minut dawało 4 pkt, a na zdobycie kolejnych 6 trzeba się niemiłosiernie męczyć wiele godzin?
Oczywiście wielkie dzięki za organizację, bardzo fajne zadania. Szczególnie 3A moje ulubione.
First, whatever translator you used it didn't realise "Young" in "Young Tableaux" is a surname and decided to translate it 😂
But responding to your question: we did know there is this O(ab) solution using an explicit formula, but couldn't prove it so we decided to go with a solution in O(2^a * something) we could, you can find the editorial for this problem in Files section
But responding to your question: we did know there is this O(ab) solution using an explicit formula, but couldn't prove it so we decided to go with a solution in O(2^a * something) we could, you can find the editorial for this problem in Files section
Dla problemu 5A1 znalazłem małą formułę, która może policzyć liczbę obciętych młodych tablic w czasie O(a) z obliczeniami wstępnymi O(ab). Jestem ciekaw rozwiązania autora.
Tak, znaliśmy ten wzorek, zresztą dokładny wariant zadania (znaczy kształt tych diagramów) dobraliśmy głównie patrząc dla jakich kształtów brut wypluwa wyniki mające dużo dzielników pierwszych, niemniej nie umieliśmy ani go udowodnić, ani znaleźć źródła dla ogólnego, więc daliśmy w wersji którą umiemy udowodnić
grzebień miał 9802 ruchów, a ile piramidka?
Meh.
Taka konfiguracja dostaje maxa:
0000000001
1000000011
1100000111
1110001111
1111011111
1111100111
1111000011
1110000001
1100000000
1000000000
0000000001
1000000011
1100000111
1110001111
1111011111
1111100111
1111000011
1110000001
1100000000
1000000000
Świstak, to jest 4C, czemu miałoby być ciekawe dla ciebie 😛
EDIT: a, sorry, porąbało mi się który komentarz jest twój 😅
EDIT: a, sorry, porąbało mi się który komentarz jest twój 😅
W poprzedniej edycji Kamil Dębowski napisał feedback do każdego zadania i bardzo mi się to spodobało, więc postanowiłem również takie coś napisać. Z ogólnych przemyśleń to wydaje mi się, że na pewno seria C była bardzo dobrze wyważona. Zrobienie całej serii na 10 nie sprawiało ogromnego wyzwania, choć trudność poszczególnych zadań wzrastała. Zadania z serii A natomiast w tym roku były bardziej bezlitosne dla (stosunkowo kiepskich) brutów - dwa razy wchodziły na zero.
1C = Finaliści
Zadanie rozgrzewkowe, żeby zachęcić ludzi do startowania i żeby każdy mógł zdobyć jakieś punkty. Podobnie jak co roku, może takie być na 1C.
1B = Praca
Zadanie ogólnie dosyć proste i odpowiedni pomysł przychodzi w zasadzie od razu, jak się w końcu ułoży w głowie, które spotkania można / trzeba / nie da się zrealizować oraz zauważy constraint n <= 8000. Zrozumienie treści zajęło mi dłużej niż odpowiednie obserwacje.
1A = Teleport
Zaskakująco trudne jak na 1A, bardzo łatwo wymyślić bruta i jakieś heury do niego. Próbowałem w miarę różnych podejść i z żadnego nie umiałem wycisnąć złożoności pesymistycznej lepszej niż O(n^4). Koniec końców wrzuciłem bruta z heurami (jeśli dla pary teleportów a,b mamy świadka u,v, że bak ma mieć co najmniej tyle co już w innym rozwiązaniu to early exit ze sprawdzania tej pary a,b + przeglądanie par u,v w kolejności d(u,v) malejąco), który wszedł na 10. Jak dla mnie to dobrze, choć jakiś niedosyt jest że nie udało się wymyślić oficjalnego rozwiązania. Na plus, że zadanie daje wiele otwartych ścieżek do eksploracji i kombinowania. Heury, które ostatecznie wrzuciłem, wymyśliłem stosunkowo na początku, już po kilkunastu minutach kminienia, choć nad samym zadaniem spędziłem łącznie kilka godzin, szukając O(n^3).
2C = Szkoła
Proste zadanie na sort, na 2C może być. Na 3C raczej już by było za łatwe.
2B = Wyliczanka
Do zrobienia jest całkiem przyjemna i w miarę naturalna obserwacja, jak się chce dokładnie poprzeliczać na papierze to idzie ją zrobić w pół godziny. Ja niestety zakopałem się w implementację, która zajęła mi 3+ godzin z powodu przede wszystkim problemów z WSLem na Windowsie, ale też jakichś off-by-one'ów, zbyt dużego skomplikowania implementacji, złego znaku nierówności itd. Dziękuję Krzysztof Potępa za egzostywne testy na forum, bez nich ten proces trwałby chyba jeszcze dłużej XD
2A = Egzamin
Ogólnie spostrzeżenie, że trzeba przechodzić w kolejności malejącej i że znaczenie mają tylko prawdopodobieństwa w t, t + 2, t + 4, … wymyśla się od razu, podobnie jak formułę na sukces dla nich. To już daje z bruta na O(n^2). Ponieważ taki brut nie przechodzi maxtestów, człowiek zaczyna się zastanawiać nad jakimś bucketowaniem, które w połączeniu z FFT daje O(n**1.5 log n). Rozwiązanie trochę przemocowe w porównaniu do innych pomysłów z forum, ale zadanie moim zdaniem łatwiejsze niż 1A, gdyż szło je tak właśnie przepałować stosując standardowe techniki.
3C = Akwarium
Zacząłem od napisania bruta, który szedł po wszystkich trójkach (a, b, h) i sprawdzał, czy a**2 + b**2 + h**2 jest kwadratem (i jeśli tak, to czego -- liczby są na tyle małe, że sqrt ma wystarczającą precyzję). To działało w 37 sekund, a w dodatku cały output miał tylko jakoś 22kB czy coś takiego (printowałem difference array wyników, a nie same wyniki, więc w kodzie jeszcze musiałem zrobić sumę prefixową). Ponieważ wyszło, że stablicowanie wszystkiego wchodzi, to tak zrobiłem. Raczej wiedziałbym jak zrobić to zadanie gdyby limity były do większych n (podobnego typu zadania są całkiem liczne na Project Euler) i może trochę szkoda, że nie zostały zwiększone, żeby jednak takie tablicowanie wyników nie wchodziło na 10, bo tak to trochę się zadanie strywializowało i poniekąd zmarnowało.
3B = Mnożenie cyfr
Sama koncepcja dynamika po prefixie liczby dosyć się tu narzuca, ale ile było zabawy, żeby to jakoś w sensownym czasie działało! Bardzo dobrze się przy tym zadaniu bawiłem, wycinając wektorami mapy / sety gdzie tylko mi się udało. Ostatecznie główna optymalizacja, dająca 10 zamiast 6 polegała na dopisaniu lazy ewaluacji stanów dynamika, co miało zaskakująco duży wpływ na czas działania -- szkoda, że pomyślałem o tym dopiero po kilku godzinach zabawy. Zadanie bardzo mi się spodobało.
3A = Opieka
Zadanie jest bardzo trudne w wymyśleniu jakiegokolwiek bruta, dającego przekonanie, że jest on poprawny. Co więcej, z powodu zabaw z MNO, do tego zadania napisałem tylko na szybko heurę, polegającą na zmultiplikowaniu instancji n/2, n/2+1,...,n razy (wyszło mi na intuicję, że mianownik jest <= n, a nie ma sensu sprawdzać mianownika 2, jeśli będzie się sprawdzać też np 4 -- sprawdzając mianownik 4, wyjdzie nam po prsotu 2 razy większy licznik, jeśli poprawna odpowiedź ma mianownik 2). Każdą taką instancję weryfikuję już całkowitoliczbowo, bez subpodziałów. Niestety brakło czasu, żeby tu coś mądrego wymyślić, a backtracking nie wchodził nawet na 1p :( Zadanie ciekawe, może być, szkoda, że nie umiem takich rozwiązwać.
4C = Wieża
Zadanie na nietrudnego do wymyślenia dynamika, czyli dobre na dywizję C. Warunek, że rozmiary klocków mogą być różne to tylko taki zaciemniacz, żeby analizować stany dynamika blokowo.
4B = Zbieranie klocków
Zadanie fajne, chociaż nie miałem w ten dzień zbytnio dużo czasu, więc niestety nie miałem szansy pomyśleć wystarczająco dużo. Brut z odpalaniem po każdym query od nowa odcinania wchodzi na 4, albo na 5 po usunięciu jak największej liczby map i setów. Myślę, że całkiem uczciwe jak na serię B.
4A = Piracka chciwość
Całkiem szybko narzucał się brut w O(n^2 log n) idący +/- jak w rozwiązaniu znanej wersji zagadki. Ten brut wchodził na 0. Uważam, że to o tyle uczciwe, że na zadaniu 4A brut dostający jakieś punkty powinien jednak reprezentować pewne obserwacje i wysiłek.
5C1 = Migawka
Ja zacząłem od napisania losowania plasz i patrzenia, które dają dobre wyniki, a że akurat patrzyłem na plansze o bardzo małej liczbie wierszy (np tylko 3 wiersze), to szybko trafiłem na wylosowanie takich, które miały na końcu linii w miarę długi ciąg 0 lub 1. I to narzuciło pomysł, żeby napisać takiego wężyka co idzie po kwadracie 99x99. Zadanie bardzo urocze, nie miałem przyjemności skorzystać z wizualizera, więc się nie wypowiadam.
5C2 = Turniej trójek
Binary search w binary searchu daje 10p. -- jak na końcowe zadanie serii C może być, trzeba policzyć jakiś dwumian albo w inny sposób sobie rozpisać wzór.
5B1 = Heavy Metal
Po pierwsze sprawdzamy Dijkstrą, czy to się w ogóle da zrobić. Podejść do znalezienia najdłuższej ścieżki miałem cztery w tym zadaniu, ostatecznie najlepsze okazało się szukanie optymalnej ścieżki od końca + early exit jeśli potencjalna dalsza ścieżka będzie w stanie dać mniej niż aktualny best. Trudno mi powiedzieć, jaki miał być wzorcowy algorytm, bo moje rozwiązanie raczej przypomina przeheurowanie Dijkstry.
5B2 = Podciągi
Znów brut jak w 4B, polegający na sprawdzeniu po każdym query od nowa: zliczamy wszystkie unikalne słowa oraz takie, które są unikalne na tylko jeden sposób i odejmujemy. Wychodzą do wymyślenia dwa przyjemne dynamiki i ogólnie jest frajda rozwiązać nawet taki uproszczony wariant tego zadania. Taki brut wchodzi na 3 i to jest chyba całkiem uczciwe, choć chyba żałuję, że nie próbowałem dodawać jakiegoś cache'owania prefixów, żeby próźniej obliczać tego dynamika tylko od punktu zmiany.
5A1 = Gładkie permutacje, 5A2 = Liście
Nie ruszyłem ostatecznie tych zadań, wyglądają na trudne. Do liści idzie wymyślić bruta, ale spojrzenie na podzadania raczej przekonuje, że wyjdzie 0. Do permutacji trudno nawet o bruta, choć warunek a <= 20 dawał jakiś potencjał.
Ogólnie zadania mi się podobały i reprezentowały tradycyjnie wysoki poziom, choć były nieco łatwiejsze niż rok temu (aż 9 osób z 120p. po 4 dniu!), więc próg będzie pewnie wyższy i do finału trochę punktów zabraknie. Dziękuję uprzejmie Organizatorom za interesujący dobór zadań i kontynuowanie tradycji tego wspaniałego konkursu.
1C = Finaliści
Zadanie rozgrzewkowe, żeby zachęcić ludzi do startowania i żeby każdy mógł zdobyć jakieś punkty. Podobnie jak co roku, może takie być na 1C.
1B = Praca
Zadanie ogólnie dosyć proste i odpowiedni pomysł przychodzi w zasadzie od razu, jak się w końcu ułoży w głowie, które spotkania można / trzeba / nie da się zrealizować oraz zauważy constraint n <= 8000. Zrozumienie treści zajęło mi dłużej niż odpowiednie obserwacje.
1A = Teleport
Zaskakująco trudne jak na 1A, bardzo łatwo wymyślić bruta i jakieś heury do niego. Próbowałem w miarę różnych podejść i z żadnego nie umiałem wycisnąć złożoności pesymistycznej lepszej niż O(n^4). Koniec końców wrzuciłem bruta z heurami (jeśli dla pary teleportów a,b mamy świadka u,v, że bak ma mieć co najmniej tyle co już w innym rozwiązaniu to early exit ze sprawdzania tej pary a,b + przeglądanie par u,v w kolejności d(u,v) malejąco), który wszedł na 10. Jak dla mnie to dobrze, choć jakiś niedosyt jest że nie udało się wymyślić oficjalnego rozwiązania. Na plus, że zadanie daje wiele otwartych ścieżek do eksploracji i kombinowania. Heury, które ostatecznie wrzuciłem, wymyśliłem stosunkowo na początku, już po kilkunastu minutach kminienia, choć nad samym zadaniem spędziłem łącznie kilka godzin, szukając O(n^3).
2C = Szkoła
Proste zadanie na sort, na 2C może być. Na 3C raczej już by było za łatwe.
2B = Wyliczanka
Do zrobienia jest całkiem przyjemna i w miarę naturalna obserwacja, jak się chce dokładnie poprzeliczać na papierze to idzie ją zrobić w pół godziny. Ja niestety zakopałem się w implementację, która zajęła mi 3+ godzin z powodu przede wszystkim problemów z WSLem na Windowsie, ale też jakichś off-by-one'ów, zbyt dużego skomplikowania implementacji, złego znaku nierówności itd. Dziękuję Krzysztof Potępa za egzostywne testy na forum, bez nich ten proces trwałby chyba jeszcze dłużej XD
2A = Egzamin
Ogólnie spostrzeżenie, że trzeba przechodzić w kolejności malejącej i że znaczenie mają tylko prawdopodobieństwa w t, t + 2, t + 4, … wymyśla się od razu, podobnie jak formułę na sukces dla nich. To już daje z bruta na O(n^2). Ponieważ taki brut nie przechodzi maxtestów, człowiek zaczyna się zastanawiać nad jakimś bucketowaniem, które w połączeniu z FFT daje O(n**1.5 log n). Rozwiązanie trochę przemocowe w porównaniu do innych pomysłów z forum, ale zadanie moim zdaniem łatwiejsze niż 1A, gdyż szło je tak właśnie przepałować stosując standardowe techniki.
3C = Akwarium
Zacząłem od napisania bruta, który szedł po wszystkich trójkach (a, b, h) i sprawdzał, czy a**2 + b**2 + h**2 jest kwadratem (i jeśli tak, to czego -- liczby są na tyle małe, że sqrt ma wystarczającą precyzję). To działało w 37 sekund, a w dodatku cały output miał tylko jakoś 22kB czy coś takiego (printowałem difference array wyników, a nie same wyniki, więc w kodzie jeszcze musiałem zrobić sumę prefixową). Ponieważ wyszło, że stablicowanie wszystkiego wchodzi, to tak zrobiłem. Raczej wiedziałbym jak zrobić to zadanie gdyby limity były do większych n (podobnego typu zadania są całkiem liczne na Project Euler) i może trochę szkoda, że nie zostały zwiększone, żeby jednak takie tablicowanie wyników nie wchodziło na 10, bo tak to trochę się zadanie strywializowało i poniekąd zmarnowało.
3B = Mnożenie cyfr
Sama koncepcja dynamika po prefixie liczby dosyć się tu narzuca, ale ile było zabawy, żeby to jakoś w sensownym czasie działało! Bardzo dobrze się przy tym zadaniu bawiłem, wycinając wektorami mapy / sety gdzie tylko mi się udało. Ostatecznie główna optymalizacja, dająca 10 zamiast 6 polegała na dopisaniu lazy ewaluacji stanów dynamika, co miało zaskakująco duży wpływ na czas działania -- szkoda, że pomyślałem o tym dopiero po kilku godzinach zabawy. Zadanie bardzo mi się spodobało.
3A = Opieka
Zadanie jest bardzo trudne w wymyśleniu jakiegokolwiek bruta, dającego przekonanie, że jest on poprawny. Co więcej, z powodu zabaw z MNO, do tego zadania napisałem tylko na szybko heurę, polegającą na zmultiplikowaniu instancji n/2, n/2+1,...,n razy (wyszło mi na intuicję, że mianownik jest <= n, a nie ma sensu sprawdzać mianownika 2, jeśli będzie się sprawdzać też np 4 -- sprawdzając mianownik 4, wyjdzie nam po prsotu 2 razy większy licznik, jeśli poprawna odpowiedź ma mianownik 2). Każdą taką instancję weryfikuję już całkowitoliczbowo, bez subpodziałów. Niestety brakło czasu, żeby tu coś mądrego wymyślić, a backtracking nie wchodził nawet na 1p :( Zadanie ciekawe, może być, szkoda, że nie umiem takich rozwiązwać.
4C = Wieża
Zadanie na nietrudnego do wymyślenia dynamika, czyli dobre na dywizję C. Warunek, że rozmiary klocków mogą być różne to tylko taki zaciemniacz, żeby analizować stany dynamika blokowo.
4B = Zbieranie klocków
Zadanie fajne, chociaż nie miałem w ten dzień zbytnio dużo czasu, więc niestety nie miałem szansy pomyśleć wystarczająco dużo. Brut z odpalaniem po każdym query od nowa odcinania wchodzi na 4, albo na 5 po usunięciu jak największej liczby map i setów. Myślę, że całkiem uczciwe jak na serię B.
4A = Piracka chciwość
Całkiem szybko narzucał się brut w O(n^2 log n) idący +/- jak w rozwiązaniu znanej wersji zagadki. Ten brut wchodził na 0. Uważam, że to o tyle uczciwe, że na zadaniu 4A brut dostający jakieś punkty powinien jednak reprezentować pewne obserwacje i wysiłek.
5C1 = Migawka
Ja zacząłem od napisania losowania plasz i patrzenia, które dają dobre wyniki, a że akurat patrzyłem na plansze o bardzo małej liczbie wierszy (np tylko 3 wiersze), to szybko trafiłem na wylosowanie takich, które miały na końcu linii w miarę długi ciąg 0 lub 1. I to narzuciło pomysł, żeby napisać takiego wężyka co idzie po kwadracie 99x99. Zadanie bardzo urocze, nie miałem przyjemności skorzystać z wizualizera, więc się nie wypowiadam.
5C2 = Turniej trójek
Binary search w binary searchu daje 10p. -- jak na końcowe zadanie serii C może być, trzeba policzyć jakiś dwumian albo w inny sposób sobie rozpisać wzór.
5B1 = Heavy Metal
Po pierwsze sprawdzamy Dijkstrą, czy to się w ogóle da zrobić. Podejść do znalezienia najdłuższej ścieżki miałem cztery w tym zadaniu, ostatecznie najlepsze okazało się szukanie optymalnej ścieżki od końca + early exit jeśli potencjalna dalsza ścieżka będzie w stanie dać mniej niż aktualny best. Trudno mi powiedzieć, jaki miał być wzorcowy algorytm, bo moje rozwiązanie raczej przypomina przeheurowanie Dijkstry.
5B2 = Podciągi
Znów brut jak w 4B, polegający na sprawdzeniu po każdym query od nowa: zliczamy wszystkie unikalne słowa oraz takie, które są unikalne na tylko jeden sposób i odejmujemy. Wychodzą do wymyślenia dwa przyjemne dynamiki i ogólnie jest frajda rozwiązać nawet taki uproszczony wariant tego zadania. Taki brut wchodzi na 3 i to jest chyba całkiem uczciwe, choć chyba żałuję, że nie próbowałem dodawać jakiegoś cache'owania prefixów, żeby próźniej obliczać tego dynamika tylko od punktu zmiany.
5A1 = Gładkie permutacje, 5A2 = Liście
Nie ruszyłem ostatecznie tych zadań, wyglądają na trudne. Do liści idzie wymyślić bruta, ale spojrzenie na podzadania raczej przekonuje, że wyjdzie 0. Do permutacji trudno nawet o bruta, choć warunek a <= 20 dawał jakiś potencjał.
Ogólnie zadania mi się podobały i reprezentowały tradycyjnie wysoki poziom, choć były nieco łatwiejsze niż rok temu (aż 9 osób z 120p. po 4 dniu!), więc próg będzie pewnie wyższy i do finału trochę punktów zabraknie. Dziękuję uprzejmie Organizatorom za interesujący dobór zadań i kontynuowanie tradycji tego wspaniałego konkursu.
Dało się dogooglać do tego trudniejszego diagramu z omówienia i jest na niego wzorek, więc da się całość w O(ab).
Taaaa... Właśnie taką wersję naklepałem i była znacznie trudniejsza, aby potem się zorientować, że ehhhh...