<< problem 231 - The prime factorisation of binomial coefficients | Semidivisible numbers - problem 234 >> |

# Problem 232: The Race

(see projecteuler.net/problem=232)

Two players share an unbiased coin and take it in turns to play "The Race".

On Player 1's turn, he tosses the coin once: if it comes up Heads, he scores one point; if it comes up Tails, he scores nothing.

On Player 2's turn, she chooses a positive integer T and tosses the coin T times: if it comes up all Heads, she scores 2^{T-1} points; otherwise, she scores nothing.

Player 1 goes first. The winner is the first to 100 or more points.

On each turn Player 2 selects the number, T, of coin tosses that maximises the probability of her winning.

What is the probability that Player 2 wins?

Give your answer rounded to eight decimal places in the form 0.abcdefgh .

# My Algorithm

My solution follows the standard Dynamic Programming pattern:

the solution is found recursively with aggressive caching of partial results.

The function `twoWins`

considers only player 2's move. Its parameter is the number of remaining points:

- if zero points left for player 2, then player 2 won

- if zero points left for player 1, then player 1 won

- in any other case, all possible moves of player 2 are analyzed and the best is chosen

Each "round" consists of one turn of player 2 followed by one turn of player 1.

There are four cases:

1. player 2 has all heads up, player 1 has heads up as well

2. player 2 has all heads up, player 1 has tails

3. player 2 has tosses tails at least once, player 1 has heads up

4. both players toss tails

The probabilities of cases 1 to 3 are well defined (`win1`

and `win2`

).

The only "tricky" case is case 4 where basically nothing changes.

Since `twoWins`

focuses on player 2, I have to manually play the first turn of player 1 in `main`

and

add the probabilities for both (equally likely) outcomes of player 1's first turn.

## Note

I was sure to have a correct solution but was rejected by the Project Euler website.

A simple Monte-Carlo simulation told me that my result should be okay, too (considering a certain error margin).

It took me quite some time to figure out that I have to switch the order of the first lines in `twoWins`

:

check first whether player 2 won, only then check player 1. That was a nasty mistake.

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <iostream>
#include <iomanip>
#include <vector>
// the first player with 100 points wins

unsigned int maxScore = 100;
// fixed probabilities of player one

const double win1 = 0.5;
const double lose1 = 1 - win1; // = 0.5
// return chance of winning for player 2 when it's his/her turn

double twoWins(unsigned int needPointsOne, unsigned int needPointsTwo)
{
// player two won
if (needPointsTwo == 0)
return 1;
// player one won
if (needPointsOne == 0)
return 0;
// memoize
const double Unknown = -1;
static std::vector<double> cache(maxScore * maxScore, Unknown);
auto id = (needPointsOne - 1) * maxScore + needPointsTwo - 1;
if (cache[id] != Unknown)
return cache[id];
// find highest chance of winning
double best = 0;
// current bet (observation: betting more than 2^3 = 8 never seems profitable)
unsigned int bet = 1;
while (true)
{
// probabilities
auto win2 = 0.5 / bet; // 2^(bet-1)
auto lose2 = 1 - win2;
// in case player two scores he shall not exceed the maximum score
auto nextPointsTwo = (needPointsTwo < bet) ? 0 : needPointsTwo - bet;
// at least one player scored a point
auto current = win1 * win2 * twoWins(needPointsOne - 1, nextPointsTwo) +
lose1 * win2 * twoWins(needPointsOne, nextPointsTwo) +
win1 * lose2 * twoWins(needPointsOne - 1, needPointsTwo);
// both players lost, stay in same state
current /= 1 - lose1 * lose2;
// better than before ?
if (best < current)
best = current;
// no use in further increasing the risk of player 2 ?
if (nextPointsTwo == 0)
break;
// twice the risk, twice the reward ...
bet *= 2;
}
cache[id] = best;
return best;
}
int main()
{
std::cin >> maxScore;
// player one moves first
// two options: he/she score one point or not
// => add both states (multiplied by their probability)
auto result = win1 * twoWins(maxScore - 1, maxScore) +
lose1 * twoWins(maxScore, maxScore);
std::cout << std::fixed << std::setprecision(8)
<< result << std::endl;
return 0;
}

This solution contains 16 empty lines, 18 comments and 3 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo 10 | ./232`

Output:

*Note:* the original problem's input `100`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in less than 0.01 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

July 21, 2017 submitted solution

July 21, 2017 added comments

# Difficulty

Project Euler ranks this problem at **65%** (out of 100%).

# Links

projecteuler.net/thread=232 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |

276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |

301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |

326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |

351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |

376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |

401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |

426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |

451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |

476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |

501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |

526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# Copyright

I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.

All of my solutions can be used for any purpose and I am in no way liable for any damages caused.

You can even remove my name and claim it's yours. But then you shall burn in hell.

The problems and most of the problems' images were created by Project Euler.

Thanks for all their endless effort.

<< problem 231 - The prime factorisation of binomial coefficients | Semidivisible numbers - problem 234 >> |