{{ message }}

Instantly share code, notes, and snippets.

# caioaao/kc.cpp

Last active Feb 10, 2017
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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include 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 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 handle = async(launch::async, calc_round, 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; }

### caioaao commented Feb 3, 2017

 ``````g++ --std=c++11 kc.cpp -o kc && time ./kc 246.208./kc 0.21s user 0.02s system 238% cpu 0.096 total ``````

### caioaao commented Feb 10, 2017

 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 ``````