Nawet nie trzeba było pisać pełnej biblioteczki. Wystarczyło big*int, big/int, big+big, big%int (i ten ostatni zwraca int, pozostałe bignum).

Czy tylko mi się wydaje, że autorzy zadań trochę przegięli z trudnością w C? Z założenia jest to grupa dla początkujących w konkursach, zadania 1-3 były fajne i w miarę łatwe, natomiast od rundy czwartej to jakaś strasznie ostra jazda... Dla kontekstu, opiszę skrótowo swoje rozwiązania

4C - zbijamy ciągi operacji tak żeby był cykl (dół, prawo, góra, lewo), okazuje się że jak zaaplikujemy coś takiego to "kształt" figury się nie zmieni, tylko pola się przepermutują jakoś, no to znajdujemy tę permutację i podnosimy do K-tej potęgi, na końcu dopychając pozostałe brutem.. Łącznie ~300 linii kodu, ogólnie bardzo fajne zadanko tylko trochę.. trudne no.

5C [walizki] - niby rozwiązanie jest proste, ale i tak na codeforces to zadanko by miało jakieś 2600..

5C [gierka] - tutaj to już w ogóle brzmi jak ostra jazda z łańcuchami Markowa żeby to zrozumieć... nie za bardzo rozumiem czemu moje rozwiązanie działa ale chyba to nie jest wymagane żeby mieć punkty.. Od razu widać że parzystość jest wymagana, a wynik okazuje się być liczbą możliwych do wykonania ruchów z tego stanu (proste do policzenia), podzieloną przez sumę liczb ruchów możliwych do wykonania we wszystkich stanach osiągalnych (tzn o tej samej parzystości) (solidnie trudne do policzenia dla początkującego, ja mam dwa czterowymiarowe dynamiki po bitmaskach). Znowu fajne zadanie, ale jakbym miał tym zachęcić osobę początkującą w konkursach algorytmicznych to by mi się chyba nie udało :P

Ja miałem O(n log^2 n). Ofc też mam parametric searcha. Kluczowym problemem u mnie było jak odpowiadać na zapytania "ile jest poprawnych nawiasowań na przedziale od i do j?". Na takie zapytania można odpowiadać w czasie stałym po preprocessingu O(n log n). Gdyby mieć zapytania na samym poczatku programu, to można by to zrobić poprzez D&C. Trzeba się trochę zastanowić jakie info trzeba mergować z lewej i prawej połówki, ale się da. A jak zapytań nie znamy, to trik jest taki, aby te wszystkie informacje zapamiętać na przyszłość (w szczególności jest n log n pamięci).

Jak już to mam i mam parametric searcha to muszę sobie liczyć jakoś tego dpka. Obserwacja jest taka, że jak mam dwie pozycje x<y i rozwazam z nich przejscia do jakiegos t, to x będzie lepsze na prefiksie, a y na sufiksie. Mogę sobie taki moment zmiany zbinsearchować. Przy takiej obserwacji utrzymuję dwukierunkową listę sensownych kandydatów i dla każdej sąsiedniej pary na tej liście znam moment kiedy ten wcześniejszy stanie się gorszy. Wynik zawsze idzie z pierwszego nieusuniętego elementu na liście.

Ja mam O(n log n) bez myślenia o drzewku, aczkolwiek implementację zrobiłem O(n log^2 n), bo sobie binsearchowałem w otoczkach (czego da się uniknąć). Robimy parametric search, a potem by wyliczać dynamik szybko trzymamy sobie stos convex hulli. Kolejne otoczki na stosie odpowiadają kolejnym niedomkniętym blokom nawiasów. Query na otoczce na szczycie stosu ma nam dawać wynik dla OPT punktu podziału leżącego w tym niedomniętym bloku. Jak napotykamy nowy nawias otwierający "(" to pushujemy nowy pusty hull. Jak napotykamy zamykający ")" to ściągamy ostatnią otoczkę, i do niższej pushujemy jedną funkcję otrzymaną z bloku co domknęliśmy.

Hubert, ja też nie pomyślałem o Pythonie, też napisałem swoją arytmetykę w C++. Różnica jest taka, że robiłem to już ze 20 raz w życiu. Wierz mi, że w pierwszych próbach też się męczyłem godzinami. Nie traktuj tego jako czas stracony. To się zwróci kolejnym razem.

Łatwe O(n^3) to przyłożyć twierdzeniem Kirchhoffa (https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem).
Też chętnie posłucham jak komuś się udało coś mądrzejszego wymyśleć.

Huh, to ja mam parametric search + jakiś trick z trzymaniem deque kolejnych kandydatów na optymalny punkt podziału, co daje O(n log^2 n) zapytań o koszt przedziału (a każde takie zapytanie robię jakimiś jump pointerami po takim drzewku jak ty opisałeś). Czyli w sumie podobny zbiór koncepcji, tylko bez CHT, i gorzej poskładany w całość xd Poza tym wyniki liczę w kolejności indeksów od lewej do prawej, a nie po drzewku (które mam osobno tylko po to żeby odpowiadać na zapytania o koszty), i to pewnie komplikuje sprawę.

Ja mam O(n log n), które korzysta z parametric search (<- nie potrafię wykazać że zachodzi ta fajna nierówność, które pozwala tego użyć) dla oraz CHT. Zamieniamy sobie nawiasowanie na drzewo gdzie wierzchołki odpowiadają poprawnym nawiasowaniom, a krawędź jest pomiędzy tymi wierzchołkami, które odpowiadają zagałęzionym nawiasom np. (()()()) to 1-2, 1-3, 1-4. Rozwiązanie O(n^2*k) robimy w taki sposób, że dla każdego wierzchołka liczymy dp[i][j], gdzie i to numer syna, a j to liczba operacji które użyliśmy dla tych synów, które przyspieszyć przy pomocy convex hull trick i zbić złożoność do O(n*k). Aby dojść do O(n log n) należy użyć parametric search, gdzie koszt nakładamy na każdą operację. Wtedy w synach liczymy po prostu jednowymiarowe dp[], które liczy się chyba podobnie. Sorry, że tak chaotycznie, ale nie chce mi się zbytnio tego rozpisywać, jak coś niejasne to mogę wyjaśnić.

Ktoś ma jakieś szybkie rozwiązanie? Ja wysłałem O(n log^3 n), które było trochę wolne, dopychałem je kolanem i nie wiem czy się udało, ale strzelam że da się szybciej...

Edit: jest 10/10, ale jakim kosztem

Jak ktos sie chce pochwalic, to jestem bardzo ciekawy rozwiazania do drzew rozpinajacych.

Bosze, czemu nie pomyślałem o Pythonie, tylko przez kilka godzin szukałem buga w napisanej arytmetyce :< Tak się zafixowałem na C++

Na potyczkach, zgodnie ze słowami Jury, "Można korzystać ze wszystkiego co pojawiło się w internecie przed rozpoczęciem danej rundy."
Także w przyszłych edycjach kopiuj bez obaw

Ja mam swoje kody które kopiuję, ale dużo osób używa jakichś open sourcowych (które pewnie ci podlinkują).

Ale akurat Walizki to napisałem w Pythonie, było szybko i przyjemnie. Szczególnie pomocna była klasa Fraction która implementuje (dokładne) ułamki, nawet nie trzeba się bawić w skracanie ich ręcznie.

Nie wiem jak ze wszystkimi zawodami, ale głównie konkursy zespołowe pozwalają na posiadanie własnej wydrukowanej biblioteczki (i innych materiałów). Czasem może się przydać, gdy pojawi się coś nieoczywistego do zaimplementowania. Większość drużyn jakieś tam materiały ze sobą nosi, a jak często korzystają to kwestia indywidualna, mi się to zdarza raczej rzadko. A odnośnie zadania z walizkami, to wystarczyło je zrobić w Pythonie :P.

W tej edycji konkursu kwestię bigint rozwiązał Python...
Ale faktycznie mam własną implementację big integerów w C++. Mam też AVL tree, ale nie wykorzystałem w tym roku.