5853. Majątek Billa

[bunker96]

Witam,
Próbuję rozwiązać zadanie z tej strony http://pl.spoj.com/problems/MWP2_2B/. Niby wszystko ładnie pięknie rozwiązuje, jednak sędzia w rezultacie zwraca "błąd wykonania(SIGSEGV)" a w kolumnie mem mam 11M. Czy ten błąd spowodowany jest przekroczeniem pamięci? Jak mogę rozwiązać ten problem?
----------------Zaliczone----------------

[tycjan]

Dla danych testowych niewątpliwie zadziała, ale mowy nie ma, że zadziała dla takich danych 10000000^1000000 mod 9999, A testy mają przedział > d (1 ≤ u, s ≤ 10^6, 1 ≤ d ≤ 10000). Twój algorytm to "naiwnie" szybkie potęgowanie modularne, tu trzeba użyć innego ("ultra") szybkiego potęgowania modularnego. 11 M masz i SIGSEGV bo rekurencja, zawala pamięć szczególnie przy tak dużych danych > 10000000^1000000 mod 9999, zanim policzy co trzeba reszta "wisi" w pamięci.

[bunker96]

Ehh wszystkie algorytmy, które znajduje to ten sam który tutaj zastosowałem z tą różnicą że używane są operatory bitowe. Czy rozbicie liczby na potęgi 2 i potęgowanie tego będzie szybsze?

[tycjan]

Zdecydowanie szybsze jest rozbicie s na postać binarną można zejść nawet do O(log s), jak potęgujesz np. iteracyjnie to musisz wykonać "s" mnożeń, ale zauważ że jak rozłożysz "s" na liczbę binarną to tak naprawde, wykonasz tylko tyle mnożeń ile jest bitów o wartości 1, czyli w praktyce dużo mniej.
Bardziej wyczerpujące źródło na temat szybkiego potęgowania modularnego -> http://www.algorytm.org/algorytmy-arytmetyczne/szybkie-potegowanie-modularne.html

[narbej]

Może źle szukasz? Tak naprawdę, nie chodzi tu o szybkie potęgowanie modularne, tylko o szybkie potęgowanie. Algorytm szybkiego potęgowania jest iteracyjny a nie rekurencyjny. Jak znajdziesz już opis takiego algorytmu [szybkie potęgowanie], to już samodzielnie "włóż" do niego w odpowiednich miejscach działanie modulo. Dostaniesz wtedy właśnie szybkie potęgowanie modularne.

[joniren]

Zaimplementowałem “modularne potęgowanie przez podnoszenie do kwadratu”:
https://pastebin.com/g8GcQ5Zd (link wygaśnie po 24h)

Algorytm jest ok, ale widzę, że byli szybsi , więc zastanawiam się, co zrobić, żeby ich dogonić. Czy implementować Montgomery reduction czy inny który przyspieszy mnożenie potęg, czy w ogóle przerzucić się na inny algorytm. Nie jestem też pewien, czy zoptymalizowałem ten algorytm, który napisałem, więc jeśli macie jakieś uwagi, to rzucajcie nimi we mnie.

[j4rooo]

Niestety szybsze czasy mają cwaniaki, którzy używają szybszych funkcji wczytywania i wypisywania

Albo tak jak ja nie przejmuj się czasem w zadaniu. Tylko bierz się za następne, bo jak masz AC to zrobiłeś je prawidłowo.

Albo musisz sobie przygotować funkcje fast I/O w oparciu o getc_unlocked/putc_unlocked albo inne fready(). Na początek możesz też zobaczyć z scanf i printf.

[narbej]

Int, fast i/o and goole are your best friends

[piokemon]

Autor określił, iż zadanie można napisać w językach programowania: All except: ASM64 GOSU.
Uczę się programowania w języku Python. Najpierw napisałem program z użyciem potęgowania i modulo. Niestety otrzymałem rezultat, iż przekroczono limit czasu. Następnie z użyciem wbudowanej funkcji pow() i znów przekroczyłem limit czasu. Na koniec skorzystałem z napisanej przez kogoś funkcji realizującej szybkie potęgowanie modularne i tak jak się spodziewałem znów przekroczenie liczby czasu.

Przeglądając „wszystkie zgłoszenia” i „najlepsze” zauważyłem, iż zadanie rozwiązali jedynie posługujący się językami z rodziny C. Skoro tylko kompilator C potrafi w tym czasie przetworzyć dane, to czy języki programowania nie powinny być ograniczone jedynie do tych z rodziny C? Po co marnować czas na zadanie którego nie można w innym języku rozwiązać w określonym czasie?

[narbej]

Autor określił, iż zadanie można napisać w językach programowania:

Nic takiego autor nie określił. Po prostu nie zabronił abyś zgłaszał rozwiązanie w którymś z licznej plejady dostępnych języków programowania. Autor już i tak poświęcił wystarczaj ąco dużo czasu na przygotowanie zadania i nie jest w stanie sprawdzić czy rozwiązanie przejdzie w którym kolwiek innym języku niż w użytym przez autora.

Po co marnować czas na zadanie którego nie można w innym języku rozwiązać w określonym czasie?

Jeżeli tak uważasz, to rzeczywiście po co?

Przeglądając „wszystkie zgłoszenia” i „najlepsze” zauważyłem, iż zadanie rozwiązali jedynie posługujący się językami z rodziny C

Słabo przeglądałeś:

POLSKI SPOJ - Status: test your programming skills on-line

POLSKI SPOJ - Status: test your programming skills on-line

POLSKI SPOJ - Status: test your programming skills on-line

POLSKI SPOJ - Status: test your programming skills on-line

[hipcia]

Mnie też boli wyśrubowanie czasów w niektórych zadaniach. Często wymusza to stosowanie fast-io co niekoniecznie jest wygodne i proste. Może udałoby się polepszyć trochę taką sytuację przemnażając maksymalny czas wykonania zadania w danym języku programowania?

P.S. @narbej Czy mógłbyś mi powiedzieć jak taki zwykły szary hipopotam SPOJa może uzyskać dostęp do pełnych statystyk (obecnie widzę tylko 11 stron z najlepszymi wynikami)? Kiedyś o ile dobrze pamiętam można było zobaczyć najlepsze czasy w danym języku. Teraz tego nie widzę ;/

[narbej]

obecnie widzę tylko 11 stron z najlepszymi wynikami)

Też tak mam
Ale można dopisać lang=…
Gdzie, zamiast kropek wstawiasz kod języka. Dla mniej popularnych języków raczej zmieścisz się w 11 stronach. Kody poznasz, klikając w dany język, np na stronie: https://pl.spoj.com/problems/latwe/

Mnie też boli …

Mnie też kiedyś, ale pocieszę Cię, poboli poboli i przestanie.

[narbej]

był jednym z najlepszych

Co to za zadanie, jeśli mogę spytać?