Last active
February 10, 2017 23:14
-
-
Save caioaao/84f174c03b8ab1d804bc3243bb95bdd4 to your computer and use it in GitHub Desktop.
KC exact solution (https://www.gwern.net/Coin-flip)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <map> | |
#include <set> | |
#include <bitset> | |
#include <list> | |
#include <stack> | |
#include <queue> | |
#include <deque> | |
#include <string> | |
#include <sstream> | |
#include <algorithm> | |
#include <cstdio> | |
#include <cstring> | |
#include <future> | |
#include <ctime> | |
using namespace std; | |
const int MAX_ROUND = 300; | |
const int MAX_WEALTH = 25000; | |
const int BETS_DELTA = 1; | |
double memo[MAX_WEALTH + 1][2]; | |
inline double vWin(int wealth, int bet, int roundIdx) { | |
if(wealth + bet < MAX_WEALTH) { | |
return memo[wealth + bet][!roundIdx]; | |
} | |
else { | |
return MAX_WEALTH; | |
} | |
} | |
inline double vLoose(int wealth, int bet, int roundIdx) { | |
if (wealth - bet == 0) { | |
return 0; | |
} | |
else { | |
return memo[wealth - bet][!roundIdx]; | |
} | |
} | |
inline double v(int wealth, int bet, int roundIdx) { | |
return .6 * vWin(wealth, bet, roundIdx) + .4 * vLoose(wealth, bet, roundIdx); | |
} | |
template<typename RAIter> | |
void calc_round(RAIter beg, RAIter end, int roundIdx){ | |
int len = distance(beg, end); | |
if(len < 1000) { | |
for(RAIter p = beg; p != end; ++p) { | |
int wealth = distance(memo, p); | |
(*p)[roundIdx] = v(wealth, wealth, roundIdx); | |
for (int bet = 0; bet < wealth; bet += BETS_DELTA) { | |
memo[wealth][roundIdx] = max(memo[wealth][roundIdx], v(wealth, bet, roundIdx)); | |
} | |
} | |
} | |
else { | |
RAIter mid = beg + len/2; | |
future<void> handle = async(launch::async, calc_round<RAIter>, mid, end, roundIdx); | |
calc_round(beg, mid, roundIdx); | |
} | |
} | |
double calc_table() { | |
bool roundIdx = 0; | |
for(int i = 0; i <= MAX_WEALTH ; ++i) { | |
memo[i][!roundIdx] = i; | |
} | |
for(int round = MAX_ROUND - 1; round >= 0; --round) { | |
calc_round(memo, memo + MAX_WEALTH, roundIdx); | |
roundIdx ^= 1; | |
} | |
return memo[2500][!roundIdx] / 100.; | |
} | |
int main() { | |
ios_base::sync_with_stdio(0); | |
cin.tie(0); | |
clock_t begin = clock(); | |
double res = calc_table(); | |
clock_t end = clock(); | |
cout << "result: " << res << "(elapsed: " << (double(end - begin) / CLOCKS_PER_SEC) << ")" << endl; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
first version:
Second version: