Korzystając z okazji, że jest tu sporo doświadczonych osób w rywalizacji w programowaniu chciałbym dopytać się o kwestię pisania własnych bibliotek na potrzeby konkursów. Sam nigdy nie uczestniczyłem w żadnych zawodach i jestem zielony w tym temacie. Dotknęło mnie to wczoraj przy implementowaniu bieda-arytmetyki na stringach w zadaniu Walizki :<

Czy dobrze rozumiem, że większość z Was ma przygotowane repozytorium z własnoręcznie napisanymi implementacjami użytecznych algorytmów i klas? I wtedy na większości(?) konkursów jest możliowść zabrania takiej bazy kodu ze sobą i wklejania/importowania w razie potrzeby użycia przy rozwiązywaniu jakiegoś zadania?

Byłbym wdzięczny za przybliżenie tematu :>

Ja kopiuje z cp-algorithms.com bo mi sie nie chce pisac biblioteczki

Właśnie zupełnie nie chce mi sie pisać niczego dużego na przyszłe potrzeby, ale wychodziłem założenia, że trzeba używać w pełni własnego kodu

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.

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.

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.

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

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

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.

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).

W jaki sposób implementacja dodawania ułamków w pythonie skraca wynikowy licznik i mianownik? Robiłem w c++ i tu poległem.

Do skracania ułamków najwygodniej jest policzyć GCD licznika i mianownika.
Jakkolwiek, w zadaniu z walizkami w ogóle nie trzeba było dodawać ułamków, można było zrobić je w całości na liczbach całkowitych.
W pierwszym ruchu można założyć, że długość cyklu (czyli liczby walizek po których system się zresetuje) jest równa liczbie wyjść z pierwszej platformy. Następnie dla każdej kolejnej platformy policzyć liczbę walizek przychodzących na tę platformę w ciągu cyklu. Jeśli ta liczba jest niepodzielna przez liczbę pasów wychodzących z platformy, to obliczam NWW liczby walizek przychodzących i liczby wyjść i aktualizuję wartość cyklu i wszystkich policzonych dotąd wejść przez otrzymany mnożnik. Rozwiązanie co prawda kwadratowe, ale dla 100 platform wystarczająco szybkie, na żadnym teście nie przekroczyło 0.01s.

Ja w WAL policzyłem iloczyn stopni wychodzących i wynik to jest dzielnik tej liczby. Puszczam właśnie tyle walizek i patrzę jakie jest gcd liczby walizek które poszły każdym pasem i przez to dzielę. Nawet nie wiem jak tu można ułamki wcisnąć xd

@skracanie ułamków. trochę na boku. Jeśli już licznik i mianownik sa duże, warto chwycić "binarny" GCD. Liczba "duzych" operacji arytmetycznych" podobną (O(n), n=liczba bitów liczby), ale zamiast dzielenia (brania modulo), ktore sa kosztowne dla duzych liczb, mamy tylko operacje "liniowe" (dodawanie/odejmowanie, dzielenie przez 2).

Ale jak poprzednicy powiedzieli, dało się ułamków (a nawet mnozenia/dzielenia duzych liczb przez siebie) pozbyć, odpowiednio dobierając trzymane parametry (i, przynajmniej u mnie, majac kwadratową zależność czasu od liczby węzłow, ułamki _chyba_ pozwalały tego uniknać).

@Michał Miodek #89810 dzięki za przypomnienie, że liczy się, że spędziłem czas na trenowaniu umiejętności, a nie go przetraciłem. Co prawda mój czas na dostanie się na OI i ACMki już minął, ale uwielbiam algorytmikę i jednocześnie ćwiczę coś choć trochę użytecznego w pracy i na rozmowach kwalifikacyjnych

@Bartłomiej Szczygieł #89815 nom, nie pisałem całej biblioteki ze wszytkimi działaniami arytmetycznymi i bitowymi - zrobiłem (trochę nieefektywnie) jedynie big+big, big*big, połączone <big/big, big%big> oraz big-big (na potrzeby dzielenia). Wciąż z moimi skillami wywalało się na po jednym przypadku z sześciu grup testowych i dostawałem 4/10 : <