Zadanie "Skrzaty" z VI OIG

Racja takie wynik sa na maszynie 64 bitowej, a raczyłes sprawdzić jakie sa wyniki dla maszyny 32 bitowej? Bo to jest DUZA roznica, btw, nie rob sobie juz jaj i pomyśl, a nie probojesz wbijc zadanie jakimis brutami. Może w "prawdziwym życiu" przydaje się takie kompitowanie (nie wiem), ale na OI i innych konkursach tego typu nie zajedziesz daleko takim rozumowaniem.

Btw, i tak jestem pod wrazeniem, że wbiłes bruta na 80 pkt.

@withelm
Raczyłem, to była maszyna wirtualna Ubuntu 32bit w VMware.
Na 64bit takie pomiary byłyby oczywiście bez sensu.
Jeśli nadal upiera się pan przy swoim mogę przedstawić zestawienie ilości cykli procesora dla obu metod i pokazać wyższość 64bit.
BTW: test na main.edu.pl potwierdza te wyniki.
@Admixior
Moje zdrowie jest w jak najlepszym porządku, dziękuję za troskę.
Nie wiem, czy na tym forum kwestionowanie słów admina jest karalne, ale co tam:
Pana omówienia mojego kodu nie rozumiem zupełnie, ale zadam jedno pytanie: o której pętli pan mówi?
Wrzuciłem log z valgrinda z annotate z cyklami procesora:
a więc inline jest ok.
Przypominam, że kompiluję tym samym co oni.
Jak rozumiem w 3-krokowym rozwiązaniu chodziło o mniej-więcej taki kod:
Jest od wolniejszy i na 60pkt.
Jeśli nadal pan nie wierzy mogę sprawdzić valgrindem, ale w skrócie:
1 operacja binarna < 64 dostępy do tablicy.
Oszczędzanie pamięci w ten sposób byłoby bez sensu a jaki pisałem moje zdrowie jest w jak najlepszym porządku, dziękuję za troskę.

Jaki jest sens w żyłowaniu bruta na trochę więcej pkt? To, że brut po tego typu optymalizacjach dostaje więcej niż 40 pkt to tylko dzięki temu, że ktoś kto układał zadanie ustawił dużo większe limity czasowe (lub odpowiednio mniejsze testy).

Rozumiem.
W takim razie jak to zrobić inaczej?

Trzy uwagi:
1. Jeżeli możesz używać tablic o stałym rozmiarze to je używaj. Rezerwowanie elementów TRWA wywoływanie konstruktorów dla wektorów trwa(może w tym przypadku nie wybitnie długo ale trwa.

2. jeżeli to możliwe to zrób wszystko i stań na głowie, aby tablice były domyślnie "wyfalsowane" i zarezerwowane globalnie (nie wykonujesz memset(wykonywany podczas replace w wektorze) co skraca działanie szczególnie dla duzej liczby obiektów), napisz algorytm tak żeby stan początkowy był osiągnięty jak najmniejszym nakładem czasu.

3. Zmniejsz złożoność programu. Jak spojrzysz na pętlę to zobaczysz że masz złożoność "liczba godzin" * "liczba skrzatów" do kwadratu. Fakt że to zadanie ma złożoność do kwadratu oznacza że jest coś źle. Można to zrobić znacznie szybciej.

Półrozwiązanie:
Tworzysz tablice bool dla każdego(max) (false - nie odwiedzone).
pobierasz ilość skrzatów itp.

Klucz:
Zauważ że

[...] oznaczająca liczbę obserwowanych stanowisk oraz  uporządkowanych rosnąco liczb całkowitych ze zbioru  oznaczających numery obserwowanych stanowisk.

 Więc wystarczy porównywać aktualnie przetwarzanego skrzata (a przetwarzasz je co każde okrążenie pętli) czy czasem nie patrzy na niego smok, jak nie to zaznaczasz że tam skrzat już dotarł (true do tablicy).
Jeżeli się patrzy to go pomijasz(nie oznaczasz ani true ani też false bo już wcześniej mógł być odwiedzony) i pobierasz ze strumienia następnego na kogo się patrzy (chyba że ta grupa na kogo się patrzy się skończyła to oznaczasz wszystkich do końca że są odwiedzeni)

Co każde przetworzenie grupy sprawdzasz czy w tablicy jest już dany element oznaczony jako true(tam gdzie ma dotrzeć). Jeśli jest to koniec wypisujesz wynik a pozostałe dane wejściowe pomijasz jeżeli nie to kolejna pętla.

Jeśli sen smoka się zaczął to koniec i tyle potrzeba.
KONIEC :)

Złożoność pamięciowa 1MB (tyle ile skrzatów * bool)
Złożoność obliczeniowa (max): k1+k2+k3+...+km <= 2mln, więc (liniówka zależna od ilości godzin "aktywności" smoka razy ilość skrzatów): O(m*n)

Ogłoszenie parafialne: "Proszę szanować się nawzajem i nie pisać słów, których sami nie chcielibyśmy czytać.".

Chyba nikt nie czyta tego co piszę.
Analiza logu z valgrinda:
Łączna ilośc cykli:

Z CZEGO:
main:
scanf:
memset:
Inne: ~500,000,000

ANALIZA MAIN
Alokacja tablicy:

Serio dynamiczna wielkość jest taka zła?

Pętla główna:

Odtąd złożoność jest liniowa dla czasDoSnu.

Tworzenie i falsyfikacja tablic safeT:




Łącznie prawie 10% programu, ale co poradzić, testy wykazały że jest to najoptymalniejsze rozwiązanie.

Praktycznie cała reszta czasu jest spędzana wewnątrz pętli

Od tego momentu złożoność jest teoretycznie proporcjonalna do czasDoSnu*iloscSkrzatow/64
No i nasz najzasobożerniejszy element:



No i mamy wspomniane ^2.
Ale, ale:

Jak łatwo zauważyć ilość cykli pętli  i  są praktycznie równe: ilości cykli to odpowiednio 1,500,585,401 i 1,496,114,690.
Oznacza to, że w praktyce złożoność nie jest kwadratowa, a liniowa.
OPŁACA SIĘ CZYTAĆ TO CO SIĘ KOMENTUJE.
Pisałem też, że TO SAMO rozwiązanie na wektorach było kilkukrotnie wolniejsze...

Bo z vectora trzeba umieć korzystać. Wystarczyłoby zrobić:
i masz taką samą wydajność jak dynamiczna alokacja tablicy.