3 ms·
For #14, some of us went a little nuts optimizing the dynamic programming solution down from months/OOM to milliseconds, and going past the original suggested p
by gwern 3y ago
For #14, some of us went a little nuts optimizing the dynamic programming solution down from months/OOM to milliseconds, and going past the original suggested problem size of a few hundred to a maximum problem size of 133 million: https://gwern.net/problem-14 https://gwern.net/problem-14
- joek1301 3y agoI clicked your link, saw DP, and tabbed away to try and solve it myself first. (I also forgot to sample without replacement and wound up with $2.86.) Delightful read!
- gwern 3y agoPleased to hear that - I felt dumb when I made that mistake! But now I know I'm not alone.
- totetsu 3y agois this a related problem to the how many times to flip a coin with a chance to increase your wealth by 50% ? https://www.jasoncollins.blog/posts/ergodicity-economics-a-primer https://www.jasoncollins.blog/posts/ergodicity-economics-a-p...
- qsort 3y agoNo because it's not a random walk. Cards in this problem are not put back in the deck after they are drawn, therefore the probability of going +1/-1 depends on how many cards of each color were drawn so far. It's still markovian though, which means it's straightforward to find a solution (unless you want to go crazy with optimizations as OP suggests).