https://strawpoll.com/e2naXR4awyB

Chętnie poznam inne rozwy

Jeżeli ktoś ma wbite 10 ternary searchem to coś nie halo, bo ternary search nie działa. Oczywiście mówię o wersji gdzie patrzymy na co druga wartość tzn dla prefiksów o długości t, t+2, t+4, ....
Kontrprzykład to n=5, t=1, wartości 1, 0.99, 0.99, 0.99, 0.99.
Ale głowy nie daje że jakoś kolanem się go nie da dopchać właśnie znajdując jakiś "w miarę dobry wynik" a potem szukając naokoło czy coś

Ja liczę dynamika dp[n][k] = prawdopodobieństwo uzyskania dokładnie k punktów biorąc n najbardziej pewnych pytań do strategii, i obliczam wartości tylko dla najwęższego przedziału k który zawiera wszystkie dp[n][k] > 2e-11 = 4 * 10^6 * 50000
Eksperymentalnie wychodzi, że ten przedział ma długość L rzędu ~1000, co daje solve w o(n * L), co już wystarcza :)

Z czego co rozumiem to rozwiązanie mieści się w "Korzystanie z Czebyszewa czy innego ograniczenia"