SHARE
TWEET

Untitled

a guest Jul 10th, 2016 2,606 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Wyniki konkursu
  2. ===============
  3.  
  4. Konkurs został ogłoszony tu: http://pastebin.com/SbEzsxtG
  5.  
  6. Za pomocą programu opisanego powyżej wygenerowałem 10000 plików z danymi.
  7. W plikach wystąpiły wszystkie możliwe wartości N, czyli od 1 do 1000.
  8.  
  9. Nadesłane funkcje były testowane za pomocą programu http://pastebin.com/Gr546BH6
  10. który był uruchamiany (w większości przypadków) w pętli:
  11.  
  12.     for i in $(seq -w 10000); do ./a.out < /home/wiechu/konkurs/B/00data/$i; done | grep Trafiony | wc -l
  13.  
  14. Nadesłano jedenaście rozwiązań, nie nadesłano jednego. Oto rozwiązania:
  15.  
  16. Kategoria: hakerskie
  17. ====================
  18.  
  19. Program p01 – http://pastebin.com/m9UgFjW4
  20. ------------------------------------------
  21. Autor próbował następującej sztuczki: dostać się przez stos do zmiennych z
  22. main() i w ostatnim wywołaniu ustawić real_max i your_max na tę samą wartość.
  23. Nie wiem tylko, dlaczego uparł się ustawiać je na ostanią wartość x, skoro znał
  24. już wartość największą. Oszustwo niemal doskonałe, ale nie działa przy
  25. kompilacji z flagą -O3, więc skuteczność 0%.
  26.  
  27. Program p02 – http://pastebin.com/P5dX4Pg9
  28. ------------------------------------------
  29. Gdyby ktoś był ciekaw, jak dowiedzieć się, z jakimi parametrami został wywołany
  30. program pod linuksem, to na pewno zainteresuje się tym rozwiązaniem. Program
  31. testowy jednak wywoływany był bez parametrów, więc skuteczność 0%.
  32.  
  33. Program p03 – http://pastebin.com/XAcbFQzr
  34. ------------------------------------------
  35. Kolejnym pomysłem było przysłonięcie funkcji fopen(). Niestety, mój kompilator
  36. odmawiał dalszej pracy przy linijce z funkcją fopen_s(). Skuteczność0%.
  37.  
  38. Program p04 – https://gist.github.com/vesim987/1c0df8d01e3018e74d9a9218353b9aef
  39. -------------------------------------------------------------------------------
  40. Program jest tak hakerski, że nie odważę się go komentować, ale niestety
  41. również bazuje na założeniu, że dane będą w otwartym pliku. Poprosiłem autora
  42. o komentarz i możecie je podziwiać powyżej jak i tu: http://pastebin.com/arG3S9BL
  43. Skuteczność 0%
  44.  
  45.  
  46. Kategoria: siłowe
  47. =================
  48.  
  49. Program p05 – http://pastebin.com/A2eTwchd
  50. ------------------------------------------
  51. Pomysł autora odczytuję następująco: jeśli odgadniemy ziarno, które powoduje
  52. wylosowanie liczby N, to będziemy też znali kolejne losowane liczby i w ten
  53. sposób znajdziemy (bez odgadywania) największą. Niestety, daną liczbę N <1,1000>
  54. otrzymamy dla około dwóch milionów przypadków, więc… Program trafił 84 z 10000
  55. przypadków, a wynik jest tak dobry tylko dlatego, że napędzają go pliki z N=1,
  56. N=2, N=3.
  57.  
  58. Program p06 – http://pastebin.com/0sDfTrYE
  59. Program p07 – http://pastebin.com/0GJ7JN29
  60. -----------------
  61.  
  62. Dwaj kolejni autorzy kombinowali jak autor programu p05, ale dodatkowo
  63. sprawdzali, czy dane ziarno spowoduje nie tylko wygenerowanie N, ale też
  64. pierwszej liczby x. Oczywiście, żadnego z nich nie uruchomiłem dla 10000 danych
  65. testowych, gdyż zależało mi, by wyniki konkursu ogłosić jeszcze w tym roku.
  66.  
  67. Uruchomiłem któryś z nich dla pierwszego zestawu danych (N=771) i działał na
  68. moim laptopie około pół godziny i trafił. Uruchomiłem go dla N=1 i wtedy też
  69. trafił (sic!), ale działał przez godzinę.
  70.  
  71. Wygląda na to, że mamy programy, które na 100% trafiają, ale tylko w dane
  72. wygenerowane moim przykładowym programem. Przypomina mi to niezwykle skuteczną
  73. maszynę, którą  wymyślił Dijkstra. Maszyna ta znajdowała największy wspólny
  74. podzielnik liczb 111 i 259. Urządzenie Dijkstry składało się z dwóch tekturek,
  75. ale ja je uproszczę do jednej tekturki. Na jednej stronie piszemy
  76. „NWP(111,259)”, a na drugiej 37. I teraz ilekroć chcemy poznać NWP(111,259)
  77. odwracamy tekturkę i odczytujemy wynik. Podobieństwo widzę w tym, że tak jak
  78. tej maszyny Dijkstry, tak i tych programów trudno użyć do czegoś innego niż
  79. rozwiązywanie ograniczonego zestawu danych. Gdybym w generatorze napisał "%f"
  80. zamiast "%.15f"… no ale nie napisałem.
  81.  
  82. To jest czyste marudzenie. Był określony zestaw danych, są rozwiązania.
  83. Czy jednak zawsze te programy zadziałają? Niestety nie. Skompilowane
  84. kompilatorem (na przykład pod windows – warunki konkursu mówiły, w jakim
  85. systemie będą generowane dane, a nie w jakim będą testowane konkursowe
  86. programy) linkującym do innej funkcji rand() nie zadziałają na pewno.
  87. (Na szczęście nikt nie wpadł na to, by źródła funkcji rand() z libc zamieścić w pliku
  88. guess_max_fn.c)
  89.  
  90. Tak więc mamy:
  91.     Linux circa 100%
  92.     Windows circa 0%
  93.  
  94. Średnio: 50%
  95.  
  96.  
  97. Kategoria: całkiem nieźle, czyli one-linery
  98. ===========================================
  99.  
  100. Program p08
  101. -----------
  102.     int guess_max(double x, int N, int count)
  103.     {
  104.         return ((double)(N - count)*(double)(1 - x))<0.5;
  105.     }
  106.  
  107. Całkiem niezła funkcja, która im bliżej końca, zadawala się coraz mniejszym x.
  108. Skuteczność też niezła: 5296 trafień, czyli ~53%. A najlepsze jest to, że
  109. będzie działać równie skutecznie pod dowolnym systemem operacyjnym i dla
  110. dowolnie wygenerowanych danych – tym generatorem, innym, kostką lub monetą!
  111.  
  112. Program p09 – http://pastebin.com/YLejtg2g
  113. ------------------------------------------
  114. Autor zawarł dwa w jednym. Zacznijmy od – jak to nazwał – naginania rzeczywistości.
  115. Rzeczywistość jest taka, że u mnie kompilacja się kładzie w linii i może bym nawet
  116. dociągnął ten nieszczęsny stropts.h, ale z kodu widzę, że to jakieś kombinacje z macaniem
  117. po pliku FILE *f, a to już przerabialiśmy i skutki były mizerne.
  118.  
  119. Ciekawsze jest drugie rozwiązanie, które da się sprowadzić znów do one-linera:
  120.     return ( x >= 1.0-1.0/(N-(count-1)) );
  121.  
  122. Skuteczność nieco porównywalna z p08: 5311 czyli ~53%. Komplementów, które
  123. napisałem przy programie p08 nie będę powtarzał.
  124.  
  125. Może kiedyś przeprowadzę więcej prób, albo spróbuję znaleźć teoretyczne uzasadnienie,
  126. która funkcja jest lepsza i dlaczego, ale już nie dziś.
  127.  
  128.  
  129.  
  130. Przerywnik – historia zadania
  131. =============================
  132.  
  133. Ponad 30 lat temu do naszego pokoju w akademiku zajrzał Lechu i powiedział:
  134. „Dostałem fajne zadanie na laborkę. W czytniku znajduje sie N kart
  135. perforowanych z liczbami od 0 do 1. Mój program ma je czytać i zatrzymać się na
  136. największej. Lecę programować”.
  137.  
  138. Zdziwiłem się: „Co on tam chce programować? Wystarczy sprawdzić, czy
  139. prawdopodobieństwo, że wśród pozostałych liczb wszystkie będą mniejsze od x, jest
  140. większe od zdarzenia przeciwnego” i dodałem „Dwa karo”, bo akurat graliśmy w
  141. brydża.
  142.  
  143. Robert spojrzał w swoje karty, zastanowił się, potem popatrzył na mnie i
  144. powiedział: „Warto też pamiętać, jaka największa już była, bo jeśli teraz mamy
  145. mniejszą od niej, to nie ma co na nią stawiać”.
  146.  
  147. Lechu, Robert i ja studiowaliśmy na wydziale elektroniki i choć żaden z nas nie
  148. był wtedy studentem informatyki, to trafiały nam się ciekawe zadania.
  149.  
  150.  
  151. Kategoria: probabilistyczna
  152. ===========================
  153.  
  154. Program p10
  155. -----------
  156. One-liner, więc dam tu:
  157.     #include <math.h>
  158.  
  159.     int guess_max(double x, int N, int count)
  160.     {
  161.         return (1.0 - pow((double)(x), (double)(N - count))) < 0.5;
  162.     }
  163.  
  164. To jest właśnie to, o czym mówiłem. Prawdopodobieństwo p, że wśród m liczb
  165. wszystkie będą mniejsze od x (dla x <0,1>)
  166.     p = x^m
  167. i jednocześnie
  168.     p > (1-p)
  169. co daje:
  170.     x^m > 0.5
  171.  
  172. Autorem zapisał to nieco inaczej, ale w sumie to na jedno wychodzi.
  173.  
  174.  
  175. Skuteczność? 5455 trafień, czyli ~55%.
  176.  
  177. Program p11 – http://pastebin.com/wvTGPkc4
  178. ------------------------------------------
  179. Identyczne z p10 rozwiązanie, tyle że autor nie wykorzystał funkcji pow(),
  180. a zaimplementował ją samodzielnie. Skuteczność identyczna: 5455 trafień, czyli ~55%.
  181.  
  182. Dyskusyjne jest tylko użycie relacji >= 0.5 w miejscu > 0.5, bo intuicyjnie
  183. lepiej stawiać na to, czego prawdopodobieństwo jest większe, ale jak jest naprawdę?
  184.  
  185. Rozważmy wybór dla N=1 i naturalnego x z przedzialu <0,10>. Niech pierwsza
  186. liczba x=5. Program p10 nie postawi na tę liczbę, program p11 ją wybierze.
  187. Prawdopodobieństwo, że drugą liczbą będzie [0,1,2,3,4] jest równe
  188. prawdopodobieństwu, że będzie to liczba [6,7,8,9,10], więc tak naprawdę, oba
  189. trafią lub oba zawiodą. Oczywiście, jest jeszcze przypadek, że druga liczba
  190. również będzie równa 5 i wtedy p11 trafił już wcześniej, a p10 wybierze przy
  191. drugim wywołaniu.
  192.  
  193.  
  194. Kategoria: programy nienadesłane
  195. ================================
  196.  
  197. Program p12
  198. -----------
  199.     #include <math.h>
  200.  
  201.     int guess_max(double x, int N, int count) {
  202.         static double prev_max = 0;
  203.         if ( x < prev_max ) /* Warto też pamiętać, jaka największa już była, bo jeśli teraz mamy mniejszą od niej, to nie ma co na nią stawiać */
  204.             return 0;
  205.         prev_max = x;
  206.  
  207.         return pow(x, N-count) > 0.5; /* Wystarczy sprawdzić, czy prawdopodobieństwo, że wśród pozostałych wszystkie będą mniejsze od x jest większe od zdarzenia przeciwnego */
  208.     }
  209.  
  210. A jego skuteczność: 5843, czyli ~58%
  211.  
  212.  
  213. Gawędy teoretyczne
  214. ==================
  215.  
  216. Jaką maksymalną skuteczność można osiągnąć?
  217.  
  218. Dla N=1 mamy 100% trafności.
  219.  
  220. Dla N=2 stawiamy na pierwszą liczbę, jeśli jest większa od 0,5. Trafność wynosi
  221. 75%, co pokazałem na rysunku http://imgur.com/sZfjeI8
  222.  
  223. Dla N=3… tu już jest trudniej, bo zaczyna działać warunek Roberta, więc
  224. obliczenia zostawiam P.T. Czytelnikom jako zadanie domowe. Podpowiem tylko,
  225. że w 100 tysiacach plików z N=3 programy p10 i p11 trafiły ~68%.
  226.  
  227. Dla N=4… szkoda mi czasu na kolejne testy, ale ufunduję nagrodę temu,
  228. kto przyśle mi wzór na probabilistyczną skuteczność dla dowolnego N.
  229.  
  230.  
  231. Werdykt
  232. =======
  233. Najlepsze wyniki daje program p12, ale nikt go nie nadesłał.
  234.  
  235. Nie pozostaje mi nic innego, jak nie przyznanie pierwszej nagrody.
  236.  
  237. Postanowiłem jednak ufundować dwie nagrody pocieszenia dla autorów
  238. programów p10 i p11. Autorami są mrx1 i google13.
  239.  
  240. Nagrodą pocieszenia jest książka napisana przez
  241. Gospodarza konkursu, którą ufundowałem zwycięzcy w
  242. http://ksiegarnia.pwn.pl/Zrozumiec-programowanie,114589762,p.html
  243.  
  244.  
  245. Pozdrawiam wszystkich – tych którzy nadesłali rozwiązania i tych którzy ich nie nadesłali.
  246.  
  247. --
  248. Wiechu
RAW Paste Data
Top