SUMPRO - SPOJ - time limit exceeded

pytanie zadane 5 września 2017 w C i C++ przez J0ker Pasjonat (15,400 p.)
zamknięte 27 sierpnia 2020 przez J0ker

Dzień dobry, mam problem z zadaniem SUMPRO z serwisu SPOJ. Oto link do niego.

http://www.spoj.com/problems/SUMPRO/

Stworzyłem już w języku C swój program rozwiązujący to zadanie i dający poprawne wyniki dla każdego N z zakresu podanego w zadaniu, niestety czas wykonania jest zbyt długi.

Skróciłem już ilość wykonywanych działan o 33% zauważając,że N/k=1 dla k>N/2 i dzięki temu najpierw w pętli dopóki k<=N/2 dodaję do sumy w pętli for k*(N/k), zaś następnie od k do k<=N dodaję po prostu samo k do sumy, bo N/k=1; Zatem zamiast 3 operacji wykonuję jedną dla k>N/2 czyli wykonuję 66% operacji jakie wykonywałem na początku, ale i tak jest za długo bo time limit exceeded.

Nie chcę wstawiać kodu, gdyż regulamin ostro to krytykuje. Czy ktoś ma jakiś pomysł?

komentarz zamknięcia: jest odpowiedź

komentarz 5 września 2017 przez niezalogowany

Jeżeli zaznaczysz, że wchodzi się na własną odpowiedzialność, a zadanie ze spoja nie jest częścią jakiegoś bieżącego konkursu to możesz zamieścić kod i nikt nie będzie miał problemu. Zobacz większość pytań w kategorii SPOJ. Bez kodu trudno cokolwiek pomóc.

komentarz 5 września 2017 przez J0ker Pasjonat (15,400 p.)

Oto mój kod: Wchodzicie na własną odpowiedzialność. Jeśli chcesz zrobić to zadanie sam, nie otwieraj linku.

https://gist.github.com/anonymous/0693c205d3e13ddb17d96eb8a6808687

Tylko proszę się nie czepiać wcięć i nazw zmiennych, bo już 1000000 razy to słyszałem, w tak małym programie nie ma to znaczenia. Jak robię coś większego to dbam o wcięcia i nazwy. Proszę się skupić na działaniu.

2 odpowiedzi

odpowiedź 5 września 2017 przez j23 Mędrzec (194,920 p.)
edycja 6 września 2017 przez j23

Po co ta druga pętla? Jeśli w pierwszej pętli liczysz pierwszą połowę zakresu N, to przecież możesz za jednym zamachem obliczyć drugą. Dodatkowo w warunku pętli miałeś dzielenie przez stałą, co niewątpliwie miało (negatywny) wpływ na czas wykonania algorytmu. Tak to widzę:

...
unsigned long long  N2 = N / 2;

for (k = 1; k <= N2; k++)
	Sum += ((N / k) * k) + (N2 + k);

if(N & 1) Sum += N;

Sum %= 1000000007;

w tak małym programie nie ma to znaczenia.

Ma znaczenie, dlatego będziesz słyszał uwagi o formatowaniu następne 1000000 razy,

komentarz 6 września 2017 przez J0ker Pasjonat (15,400 p.)

Dziękuję za zwrócenie uwagi na N2=N/2 - to z pewnością cenna uwaga.

Niestety Pana fragment nie będzie działać prawidłowo, bo źle jest dodawane.

Nawet ze swoim dotychczasowym dodawaniem, które działało poprawnie, zmieniłem N/2 na N2(przypisane przed pętlą), ale i tak time limit exceeded....

Aktualnie to wygląda tak, ale nadal time limit exceeded

https://gist.github.com/anonymous/5de75b392483b2475df0782725c4edff

komentarz 6 września 2017 przez j23 Mędrzec (194,920 p.)
edycja 6 września 2017 przez j23

OK, poprawiłem kod. Sama pętla pomijała jedną iterację, jeśli N była liczbą nieparzystą, stąd ten błąd. Teraz powinno być dobrze.

--- dodane ---

Pomierzyłem czasy. Okazało się, że przy optymalizacji -O3 Twój kod jest nieco szybszy. Trochę mnie to zdziwiło, więc musiałem sprawdzić, o co chodzi. I co się okazało. Kompilator elegancko zwektoryzował drugą pętlę. Kodu jest znacznie więcej, ale jest szybszy. To taka ciekawostka...

Wbrew pozorom to zadanie nie jest takie proste. To znaczy proste jest napisanie algorytmu, który zwróci poprawne wartości, ale napisanie takiego, który zrobi to bardzo szybko - już nie. W komentarzach jest mowa o rozwiązaniu o złożoności O(sqrt(N)). Myślę, że w tym kierunku powinieneś pójść i poszukać jakichś informacji.

komentarz 6 września 2017 przez J0ker Pasjonat (15,400 p.)

Serdecznie dziękuję za odpowiedź. Poszukam więcej informacji na temat algorytmu.

komentarz 7 września 2017 przez J0ker Pasjonat (15,400 p.)

Mogę z ciekawości spytać, jak Pan sprawdził tą szybkość?

komentarz 7 września 2017 przez j23 Mędrzec (194,920 p.)

Normalnie. Wsadziłem obie wersje liczące N do oddzielnych funkcji i mierzyłem czasy ich wykonania timerem std::chrono::high_resolution_clock. Oczywiście nie mierzyłem czasów pojedynczego wywołania funkcji, tylko np. 1000.

Jeśli piszesz w C, możesz użyć funkcji clock().

odpowiedź 7 września 2017 przez mokrowski Mędrzec (155,460 p.)

Będzie Ci trudno zaliczyć to zadanie. Algorytm jest niewydajny. Podpowiem:

1. Iloraz N przez dowolną liczbę mniejszą niż N i większą od 1 jest mniejszy niż pierwiastek kwadratowy z N.

2. Ilorazy które sumujesz, powtarzają się.

PS.

Usłyszysz to 1000002 raz. Formatuj zawsze poprawnie kod. To pomaga w analizie kodu tak własnego (po pewnym czasie) jak i jest wyrazem pewnego szacunku dla tych którzy mają Ci pomóc.

komentarz 7 września 2017 przez J0ker Pasjonat (15,400 p.)

1. Nieprawda. pierwiastek z 6 to w przyblizeniu 2,44.

Natomiast 6/2=3 zaś 3>2.44 więc iloraz jest większy a ne mniejszy.

2. Nie sumuję ilorazów tylko iloczyny k*(n/k) czyli iloczyn k oraz ilorazu N/k. I nic się nie powtarza.