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; | |
} |
first version:
result: 246.606(elapsed: 296.791)
./kc0 266.40s user 30.39s system 632% cpu 46.960 total
Second version:
result: 246.606(elapsed: 136.202)
./kc 134.85s user 1.35s system 651% cpu 20.917 total
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
caioaao commentedon Feb 3, 2017