Mar 2017
11 / 40
Oct 2017
Nov 2021
narbej
Jun '17

Dostałem na PW poniższy list i pozwoliłem sobie, zacytować go w całości:

Cześć Ci Narbej,

Właśnie rozwiązałem zadanie z czarodziejskim lusterkiem i jestem w lekkim szoku.
Wpierw
użyłem stringa, żeby wrzucić do niego liczbę w postaci dwójkowej i
później od końca obliczałem nowo powstałą liczbę i się udało.
Później
wpadłem na pomysł, aby zrezygnować ze stringa i od razu w rekurencji
wyliczać nową liczbę. Też ten sposób zaliczył, ale z opóźnieniem od
starszego o około 8%. Kilka razy próbowałem zmienić co nieco, ale z
coraz gorszym skutkiem.
Patrzyłem na oba rozwiązania i byłem w 100%
pewny, że rezygnacja ze stringa jest szybszym rozwiązaniem i prawdę
mówiąc się zbulwersowałem.
Nie ufałem sędziemu, więc sprawdziłem na
kompie szybkość obu przypadków przy wariancie pesymistycznym. Okazało
się, że drugie rozwiązanie jest o około 30% szybsze.
W sumie to jest sztuka dla sztuki, ale chciałbym wiedzieć czemu tak się stało.

Wybacz, że do Ciebie piszę z tym kłopotem, ale nie chciałem uderzać z
tym kłopotem na forum, żeby innym nie popsuć przyjemności z
rozwiązywania. Jeśli nie będzie miał chęci odpowiadać to za jakiś czas
zgłoszę się z problemem na forum.

Dziękuję za jakąkolwiek odpowiedź.

Pozdrawiam
Konrad

Trochę Ci ułatwię. Jesteś już na forum :wink:

  1. Różnica czasu rzędu +- 0.02 jest, przy "dłuższych" czasach czasami nie pomierzalna - tak działa sędzia i taką ma dokładność [tolerancję] pomiaru czasu. Więc np twoje dwa wyniki: 0,12 i 0.13 mogłyby równie dobrze pomierzone jako 0.14 i 0.11 [trochę przejaskrawiam, bo nie jest to takie proste]
  2. Aby optymalizować kod, trzeba wiedzieć więcej, niż tylko umieć napisać w miarę poprawny kod. Powinno się wiedzieć co to jest "wąskie gardło" w optymalizowanym kodzie i to te miejsca w pierwszej kolejności optymalizować. W przeciwnym wypoadku, strzelanie, że "TO" będzie lepsze i poprawi na 100% wydajność, mogą faktycznie przynieść niewielką poprawę wydajności , ale równie dobrze sowodować odwrotny skutek. Na SPOJu często wąskim gardłem jest i/o [input, output]
  3. Jeżeli tak [pkt 2], to testowanie u siebie, zapewne na mniejszych testach i na innym sprzęcie może dawać zupełnie inny wynik [np u Ciebie poprawa wydajności o 30%].
  4. Twoje kody różnią się bardzo od mojej wzorcówki i są [w moim odczuciu] brzydkie :wink: Tu rekurencja nie jest potrzebna, a jej użycie [zamiast iteracji] spowalnia program. Mój negatywny stosunek do zmiennych globalnych jest stały i nie zmienny.Ale u Ciebie, może wszystkie zmienne, zaczniesz przekazywać jako zmienne globalne? :wink: W pamięci komputera liczby już są zapisane i pamiętane w formie bitowej, więc można i warto z teko skorzystać.
  5. ..... nie pamiętam, co jeszcze miałem napisać? :wink: ...
    .....
3 months later
narbej
Oct '17
3
i6g7g6y5

Milczenie jest złotem, a czytanie?
Na temat tego zadania są dwa wątki: http://discuss.spoj.com/search?q=czarodziejskie%20lusterko%20category%3A52
Ale jak już się dokleiłeś do któregoś, to przynajmniej ten kontynuowany należało dokładnie przeczytać. Są w nim już dużo wcześniej, podane przez @mariusz193, dwa testy, z których twój program jednego nie przechodzi. Testy w większości zadań to niezbędne minimum, ale często nie gwarantują AC - należy dokładnie [i despacito] czytać treść zadania, specyfikacje wejścia i wyciągać wnioski [myśleć].

PS
Jako autor zadania, powinienem podkręcić “lekko” limit czasu, aby takie rozwiązania na stringach dostawały “z automatu” TLE, ale co z tymi wszystkimi biednymi rozwiązaczami w javie, pythonie, haskelu[!? :wink: ] i wszystkich innych wolniejszych językach? No i po prostu nie chce mi się, trudno jeżeli początkujący koderzy [rozwiązywacze] są tacy jak każdy widzi, to przecież to wina koderów a nie autorów zadań, nieprawdaż?. Może kiedyś się nauczą? :wink:

tarpauwatratar
Oct '17

Wolne języki mają problem :wink:

j4rooo
Oct '17

Moim zdaniem jeżeli zadanie ma prawidłową złożoność i daje poprawne odpowiedzi powinno być akceptowane. Chyba, że w zamyśle autor chce żeby użytkownik użył takiej a nie innej struktury (albo języka).

i6g7g6y5
Oct '17
narbej

Po pierwsze zanim sam zaczniesz coś komentować to sprawdź źródło. Widziałem, że są 2 takie wątki, a w rzeczywistości 1 - dlaczego? Sprawdź sam swój link.
Po drugie - gdy dokleiłem się do tego to czytałem wcześniejsze testy i wychodziło, że jest dobrze (widocznie źle sprawdziłem ten drugi test), teraz dostałem od Mariusza jeszcze jeden test, który pozwolił mi na znalezienie błędu.
Zadanie - AC.
Nie mam więcej pytań.

mariusz193
Oct '17

to usuń link do kodu, bo zbyt bliski prawidłowego rozwiązania (choć nie popieram metody działania na stringach, bo można szybciej i bardziej elegancko)

tarpauwatratar
Oct '17

Z punktu widzenia osoby rozwiazujacej zadanie jedynym kryterium oceny poprawnosci rozwiazania jest AC. Estetyka kodu, styl rozwiazania a nawet jego wywalanie sie dla danych innych niz w testach autora (tak zwane slabe testy) nie moga byc omowione na forum ani nigdzie indziej.

Temu uwazam ze wstawiony kod powinien z automatu dostac TLE jako rozwiazanie algorytmicznie bezmyslne - to zwykly brut i tyle.

Ale to i tak nic w porownaniu z tym co przechodzi obecnie w zadaniu dotyczacym generowania liczb pierwszych.

mariusz193
Oct '17

tyle, że brut w Czarodziejskie lusterko jest praktycznie nieodróżnialny w kryterium czasowym od poprawnego rozwiązania - większość czasu to operacje wejścia/wyjścia

W zadaniu na liczby pierwsze można by wymusić poprawne rozwiązanie, ale oczywiście kosztem ograniczenia rozwiązań jedynie do C/C++

narbej
Oct '17
1
tarpauwatratar

Że nie są, nie znaczy że nie mogą. A szkoda. Kiedyś, często, przy podpowiadaniu, przy okazji komentowałem też błędy “stylistyczne” w kodzie pytającego, ale że do tanga trzeba dwojga, więc zaprzestałem. Szkoda mi mojego czasu i zdrowia, bo czasami zamiast wdzięczności było tylko obrażanie się, za taką [przecież konstruktywną, a nie złośliwą?] krytykę. Więc chyba masz rację, że większość osób [na pewno nie wszystkie] interesuje tylko uzyskanie AC i: “nie mam więcej pytań” :wink:

PS
W tym zadaniu 2x long to o jeden bit za mało. Należy koniecznie użyć unsigned.

5 months later
narbej
Mar '18
linux/python
>>> bin(4294967296)
'0b100000000000000000000000000000000'
>>> bin(4294967297)
'0b100000000000000000000000000000001'
>>> bin(18446744073709551615)
'0b1111111111111111111111111111111111111111111111111111111111111111'
>>> bin(18446744073709551616)
'0b10000000000000000000000000000000000000000000000000000000000000000'
>>>
redysz
Mar '18

Test:

69788180
19192237

Twój out:

21117088
23803464

Poprawny out:

21117089
23803465
anon41185149
Mar '18
3

Po zmianie wyjścia na double program przechodzi powyższy test. Jeśli chodzi o wejście to 2^64-1 powinno się mieścić w zakresie unsigned long long int. Niestety pokazuje WA.

narbej
Mar '18

No i się mieści :wink:
Do tego zadania wystarczy w zupełności ten typ, a stosowanie typu zmiennoprzecinkowego [float, double] jest niekonieczne, a nawet jest to błąd. Także string jest tu zupełnie zbędny.

Może przyda Ci się ten link, --> C++ kruczki i sztuczki, sorry, został “nieco” zaśmiecony, więc więcej sztuczek pewnie tam już nie będzie.

narbej
Mar '18

To:

if(k1==18446744073709551615) cout << "18446744073709551616" << endl;

oczywiście jest błędne, zobacz na mój wcześniejszy post.

Funkcja pow, jest typu double i działa na takiego typu liczbach, co może powodować i powoduje błędy zaokrągleń - pisałem, że typy zmiennoprzecinkowe nie są tu dobre.

Napisz więc swoją własną funkcję pow2(), typu unsigned long long lub stablicuj wszystkie [tylko 64] wartości potęgi 2
[0] = 1
[1] = 2
[2] = 4
…
[31] = 214748364
…
[64] = ? :wink: