Skip to content

Instantly share code, notes, and snippets.

KC exact solution (https://www.gwern.net/Coin-flip)
#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;
}
@caioaao
Copy link
Author

caioaao commented on 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
Copy link
Author

caioaao commented on 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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment