18402. Generator liczb prawie pseudolosowych -OPTYMALIZACJA

Tutaj możesz podyskutować na tematy nie kwalifikujące się do żadnego z pozostałych forów

18402. Generator liczb prawie pseudolosowych -OPTYMALIZACJA

Postautor: narbej » 19 lut 2014, 23:03

Jeżeli zerkniesz na mój wynik do tego zadania na spoj'u i pomyślisz, że znałem/odgadłem/ukradłem odpowiedzi na wszystkie/część testów lub, że je dostałem po znajomości od autora, to nic z tych rzeczy. Tym bardziej, że wtedy miałbym prawdopodobnie wynik 0.00, a przecież do tego na razie mi jeszcze trochę brakuje. ;-)
To jest pierwsza podpowiedź - mój wynik - mówiący, że można to zadanie zrobić szybciej, więc jak ja potrafiłem coś wymyśleć, to czemu nie mógłbyś i ty?
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: 18402. Generator liczb prawie pseudolosowych -OPTYMALIZA

Postautor: kokosek » 26 lut 2014, 23:32

Ale super! Pewnie jakiś sprytne spostrzeżenie, że nie trzeba obliczać wszystkich elementów ciągu.
Gratulacje. :-)
kokosek
Koordynator AlgoLigi
 
Posty: 107
Rejestracja: 20 wrz 2012, 16:04

Re: 18402. Generator liczb prawie pseudolosowych -OPTYMALIZA

Postautor: narbej » 25 sty 2015, 13:04

Tak kokosku to prawda, ale podstawą jest zrobienie tego zadania - AC, a dopiero potem myślenie o optymazlizacji. Zadanie, jak je ugryźć, jest opisane przez autora: viewtopic.php?f=9&t=54,
Moje rozwiązanie, [znane autorowi] opiera się na wyszukiwaniu lidera!

Pierwsza optymalizacja: maksymalnie możliwie optymalne generowanie kolejnych elementów generowanego ciągu. ;-)

Druga optymalizacja, zgodnie z obietnicą, już za tydzień.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: 18402. Generator liczb prawie pseudolosowych -OPTYMALIZA

Postautor: narbej » 27 sty 2015, 15:18

Trochę złamię obietnicę i już dzisiaj tu opiszę parę spostrzeżeń, a i tak pewnie wcześniej, nawet pies z kulawą nogą tu nie zaglądnie.
Powodem jest także to, że chcę spłodzić [wyskrobać] parę tekstów*/ i w nawale skrobanek, mógłbym zapomnieć i nie dotrzymać w/w obietnicy.
Na początek, chciałbym zaznaczyć, że "stworzenie" dobrego zadania nie jest wcale takie łatwe, a te zadanie jest wprost super i jak widać autor się postarał i do tej pory nikt nie zgadł i nie złamał zagadki. Ja też dopiero teraz domyślam się, i wiem dużo więcej niż wtedy, gdy rozwiązywałem zadanie ale raczej nie wykorzystam swojej wiedzy do ulepszenia rozwiązania, bo to może trochę nie fer w stosunku do autora? ;-) Z drugiej strony, autor już dość czasu śmiał się i wodził wszystkich, którzy przymierzyli się do zadania, za nos

  1. Słusznie zauważył Arek, że czasami dane - parametry generatora, mogą być niewielkie, więc jak liczysz na typie long long, to czasami warto też na mniejszym - dwie albo trzy wersje generatora, a najlepiej generator zrobić jako szablon - template i móc używać go do dowolnych typów.
  2. Generator, jak już pisałem, musi być jak najbardziej optymalnie napisany, - należy bardzo dokładnie przyjrzeć się wzorowi i maksymalnie uprościć ten wzór.
  3. Warto podrukować sobie generowane ciągi liczb, dla różnych ustawień parametrów g
  4. Słusznie zauważył kokosek, że czasami można skrócić sprawdzanie.
  5. Pomyśl, co to jest generator liczb pseudolosowych
  6. Pomyśl, jaki jest dobry generator, liczb pseudo losowych
  7. Przeczytaj jeszcze raz dokładnie, podpowiedź autora
  8. Czy taka, zaproponowana w zadaniu, metoda sprawdzania "jakości" generatora ma jakikolwiek sens?
  9. A teraz odwróć zadanie. To nie wyszukiwanie lidera jest narzędziem sprawdzania jakości generatora, tylko na odwrót to generator jest narzędziem, a zadaniem jest algorytm lidera. Dlaczego ciąg jest tak tworzony/generowany, przeczytaj w podpowiedzi autora.
  10. Z powyższego wynika, że dla pewnego odpowiednio mniejszego fragmentu ciągu, możnaby już sprawdzić i znaleźć lidera lub jego brak. Nie trzeba sprawdzać ani generować całego ciągu.
  11. Pewnie możnaby to też policzyć/ustalić na podstawie parametrów generatora - ale czy napewno tego nie wiem.
  12. Autor pewnie się zabezpieczył w jakiś sposób, którego się domyślam, przed pkt. 9, wyżej, ale dalej to już może samodzielnie?...
Tu jeszcze raz gratuluję Witoldowi super pomysłu i dzięki za całokształt ;-)
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51


Wróć do Forum ogólne

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 5 gości

cron