Wyniki konkursu
===============

Konkurs został ogłoszony tu: http://pastebin.com/SbEzsxtG

Za pomocą programu opisanego powyżej wygenerowałem 10000 plików z danymi.
W plikach wystąpiły wszystkie możliwe wartości N, czyli od 1 do 1000.

Nadesłane funkcje były testowane za pomocą programu http://pastebin.com/Gr546BH6
który był uruchamiany (w większości przypadków) w pętli:

	for i in $(seq -w 10000); do ./a.out < /home/wiechu/konkurs/B/00data/$i; done | grep Trafiony | wc -l

Nadesłano jedenaście rozwiązań, nie nadesłano jednego. Oto rozwiązania:

Kategoria: hakerskie
====================

Program p01 – http://pastebin.com/m9UgFjW4
------------------------------------------
Autor próbował następującej sztuczki: dostać się przez stos do zmiennych z
main() i w ostatnim wywołaniu ustawić real_max i your_max na tę samą wartość.
Nie wiem tylko, dlaczego uparł się ustawiać je na ostanią wartość x, skoro znał
już wartość największą. Oszustwo niemal doskonałe, ale nie działa przy
kompilacji z flagą -O3, więc skuteczność 0%.

Program p02 – http://pastebin.com/P5dX4Pg9
------------------------------------------
Gdyby ktoś był ciekaw, jak dowiedzieć się, z jakimi parametrami został wywołany
program pod linuksem, to na pewno zainteresuje się tym rozwiązaniem. Program
testowy jednak wywoływany był bez parametrów, więc skuteczność 0%.

Program p03 – http://pastebin.com/XAcbFQzr
------------------------------------------
Kolejnym pomysłem było przysłonięcie funkcji fopen(). Niestety, mój kompilator
odmawiał dalszej pracy przy linijce z funkcją fopen_s(). Skuteczność0%.

Program p04 – https://gist.github.com/vesim987/1c0df8d01e3018e74d9a9218353b9aef
-------------------------------------------------------------------------------
Program jest tak hakerski, że nie odważę się go komentować, ale niestety
również bazuje na założeniu, że dane będą w otwartym pliku. Poprosiłem autora
o komentarz i możecie je podziwiać powyżej jak i tu: http://pastebin.com/arG3S9BL
Skuteczność 0%


Kategoria: siłowe
=================

Program p05 – http://pastebin.com/A2eTwchd
------------------------------------------
Pomysł autora odczytuję następująco: jeśli odgadniemy ziarno, które powoduje
wylosowanie liczby N, to będziemy też znali kolejne losowane liczby i w ten
sposób znajdziemy (bez odgadywania) największą. Niestety, daną liczbę N <1,1000>
otrzymamy dla około dwóch milionów przypadków, więc… Program trafił 84 z 10000
przypadków, a wynik jest tak dobry tylko dlatego, że napędzają go pliki z N=1,
N=2, N=3.

Program p06 – http://pastebin.com/0sDfTrYE
Program p07 – http://pastebin.com/0GJ7JN29
-----------------

Dwaj kolejni autorzy kombinowali jak autor programu p05, ale dodatkowo
sprawdzali, czy dane ziarno spowoduje nie tylko wygenerowanie N, ale też
pierwszej liczby x. Oczywiście, żadnego z nich nie uruchomiłem dla 10000 danych
testowych, gdyż zależało mi, by wyniki konkursu ogłosić jeszcze w tym roku.

Uruchomiłem któryś z nich dla pierwszego zestawu danych (N=771) i działał na
moim laptopie około pół godziny i trafił. Uruchomiłem go dla N=1 i wtedy też
trafił (sic!), ale działał przez godzinę.

Wygląda na to, że mamy programy, które na 100% trafiają, ale tylko w dane
wygenerowane moim przykładowym programem. Przypomina mi to niezwykle skuteczną
maszynę, którą  wymyślił Dijkstra. Maszyna ta znajdowała największy wspólny
podzielnik liczb 111 i 259. Urządzenie Dijkstry składało się z dwóch tekturek,
ale ja je uproszczę do jednej tekturki. Na jednej stronie piszemy
„NWP(111,259)”, a na drugiej 37. I teraz ilekroć chcemy poznać NWP(111,259)
odwracamy tekturkę i odczytujemy wynik. Podobieństwo widzę w tym, że tak jak
tej maszyny Dijkstry, tak i tych programów trudno użyć do czegoś innego niż
rozwiązywanie ograniczonego zestawu danych. Gdybym w generatorze napisał "%f"
zamiast "%.15f"… no ale nie napisałem.

To jest czyste marudzenie. Był określony zestaw danych, są rozwiązania.
Czy jednak zawsze te programy zadziałają? Niestety nie. Skompilowane
kompilatorem (na przykład pod windows – warunki konkursu mówiły, w jakim
systemie będą generowane dane, a nie w jakim będą testowane konkursowe
programy) linkującym do innej funkcji rand() nie zadziałają na pewno.
(Na szczęście nikt nie wpadł na to, by źródła funkcji rand() z libc zamieścić w pliku
guess_max_fn.c)

Tak więc mamy:
	Linux circa 100%
	Windows circa 0%

Średnio: 50%


Kategoria: całkiem nieźle, czyli one-linery
===========================================

Program p08
-----------
	int guess_max(double x, int N, int count)
	{
		return ((double)(N - count)*(double)(1 - x))<0.5;
	}

Całkiem niezła funkcja, która im bliżej końca, zadawala się coraz mniejszym x.
Skuteczność też niezła: 5296 trafień, czyli ~53%. A najlepsze jest to, że
będzie działać równie skutecznie pod dowolnym systemem operacyjnym i dla
dowolnie wygenerowanych danych – tym generatorem, innym, kostką lub monetą!

Program p09 – http://pastebin.com/YLejtg2g
------------------------------------------
Autor zawarł dwa w jednym. Zacznijmy od – jak to nazwał – naginania rzeczywistości.
Rzeczywistość jest taka, że u mnie kompilacja się kładzie w linii i może bym nawet
dociągnął ten nieszczęsny stropts.h, ale z kodu widzę, że to jakieś kombinacje z macaniem
po pliku FILE *f, a to już przerabialiśmy i skutki były mizerne.

Ciekawsze jest drugie rozwiązanie, które da się sprowadzić znów do one-linera:
	return ( x >= 1.0-1.0/(N-(count-1)) );

Skuteczność nieco porównywalna z p08: 5311 czyli ~53%. Komplementów, które
napisałem przy programie p08 nie będę powtarzał.

Może kiedyś przeprowadzę więcej prób, albo spróbuję znaleźć teoretyczne uzasadnienie,
która funkcja jest lepsza i dlaczego, ale już nie dziś.



Przerywnik – historia zadania
=============================

Ponad 30 lat temu do naszego pokoju w akademiku zajrzał Lechu i powiedział:
„Dostałem fajne zadanie na laborkę. W czytniku znajduje sie N kart
perforowanych z liczbami od 0 do 1. Mój program ma je czytać i zatrzymać się na
największej. Lecę programować”.

Zdziwiłem się: „Co on tam chce programować? Wystarczy sprawdzić, czy
prawdopodobieństwo, że wśród pozostałych liczb wszystkie będą mniejsze od x, jest
większe od zdarzenia przeciwnego” i dodałem „Dwa karo”, bo akurat graliśmy w
brydża.

Robert spojrzał w swoje karty, zastanowił się, potem popatrzył na mnie i
powiedział: „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ć”.

Lechu, Robert i ja studiowaliśmy na wydziale elektroniki i choć żaden z nas nie
był wtedy studentem informatyki, to trafiały nam się ciekawe zadania.


Kategoria: probabilistyczna
===========================

Program p10
-----------
One-liner, więc dam tu:
	#include <math.h>

	int guess_max(double x, int N, int count)
	{
		return (1.0 - pow((double)(x), (double)(N - count))) < 0.5;
	}

To jest właśnie to, o czym mówiłem. Prawdopodobieństwo p, że wśród m liczb
wszystkie będą mniejsze od x (dla x <0,1>)
	p = x^m
i jednocześnie
	p > (1-p)
co daje:
	x^m > 0.5

Autorem zapisał to nieco inaczej, ale w sumie to na jedno wychodzi.


Skuteczność? 5455 trafień, czyli ~55%.

Program p11 – http://pastebin.com/wvTGPkc4
------------------------------------------
Identyczne z p10 rozwiązanie, tyle że autor nie wykorzystał funkcji pow(),
a zaimplementował ją samodzielnie. Skuteczność identyczna: 5455 trafień, czyli ~55%.

Dyskusyjne jest tylko użycie relacji >= 0.5 w miejscu > 0.5, bo intuicyjnie
lepiej stawiać na to, czego prawdopodobieństwo jest większe, ale jak jest naprawdę?

Rozważmy wybór dla N=1 i naturalnego x z przedzialu <0,10>. Niech pierwsza
liczba x=5. Program p10 nie postawi na tę liczbę, program p11 ją wybierze.
Prawdopodobieństwo, że drugą liczbą będzie [0,1,2,3,4] jest równe
prawdopodobieństwu, że będzie to liczba [6,7,8,9,10], więc tak naprawdę, oba
trafią lub oba zawiodą. Oczywiście, jest jeszcze przypadek, że druga liczba
również będzie równa 5 i wtedy p11 trafił już wcześniej, a p10 wybierze przy
drugim wywołaniu.


Kategoria: programy nienadesłane
================================

Program p12
-----------
	#include <math.h>

	int guess_max(double x, int N, int count) {
		static double prev_max = 0;
		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ć */
			return 0;
		prev_max = x;

		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 */
	}

A jego skuteczność: 5843, czyli ~58%


Gawędy teoretyczne
==================

Jaką maksymalną skuteczność można osiągnąć?

Dla N=1 mamy 100% trafności.

Dla N=2 stawiamy na pierwszą liczbę, jeśli jest większa od 0,5. Trafność wynosi
75%, co pokazałem na rysunku http://imgur.com/sZfjeI8

Dla N=3… tu już jest trudniej, bo zaczyna działać warunek Roberta, więc
obliczenia zostawiam P.T. Czytelnikom jako zadanie domowe. Podpowiem tylko,
że w 100 tysiacach plików z N=3 programy p10 i p11 trafiły ~68%.

Dla N=4… szkoda mi czasu na kolejne testy, ale ufunduję nagrodę temu,
kto przyśle mi wzór na probabilistyczną skuteczność dla dowolnego N.


Werdykt
=======
Najlepsze wyniki daje program p12, ale nikt go nie nadesłał.

Nie pozostaje mi nic innego, jak nie przyznanie pierwszej nagrody.

Postanowiłem jednak ufundować dwie nagrody pocieszenia dla autorów
programów p10 i p11. Autorami są mrx1 i google13.

Nagrodą pocieszenia jest książka napisana przez
Gospodarza konkursu, którą ufundowałem zwycięzcy w
http://ksiegarnia.pwn.pl/Zrozumiec-programowanie,114589762,p.html


Pozdrawiam wszystkich – tych którzy nadesłali rozwiązania i tych którzy ich nie nadesłali.

--
Wiechu