<< problem 190 - Maximising a weighted product | Squarefree Numbers - problem 193 >> |

# Problem 191: Prize Strings

(see projecteuler.net/problem=191)

A particular school offers cash rewards to children with good attendance and punctuality.

If they are absent for three consecutive days or late on more than one occasion then they forfeit their prize.

During an n-day period a trinary string is formed for each child consisting of L's (late), O's (on time), and A's (absent).

Although there are eighty-one trinary strings for a 4-day period that can be formed, exactly forty-three strings would lead to a prize:

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA

OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO

AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL

AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA

LAOO LAOA LAAO

How many "prize" strings exist over a 30-day period?

# My Algorithm

Another dynamic programming problem ... my function `count`

has 3 parameters:

- `day`

stands for the number of days to be evaluated, initially 30

- `absent`

counts the consecutive absent days

- `late`

represents the total number of days where the pupil was late

There are two important things:

1. `absent`

has to be reset to zero everytime the pupil shows up (it doesn't matter whether on time or late)

2. A massive amount of situations produce the same parameter set. That means, some parameter sets are evaluated several thousand times.

A simple memoization scheme brings down the computation time from several seconds to less than 10 milliseconds:

There are at most 30*2*3 = 1800 different parameter sets:

- 30 days

- child was 0 or 1 days late so far

- he/she was 0, 1 or 2 days absent (only counting the most recent days)

A simple hash `days * 2 * 3 + absent * 2 + late`

is unique for each parameter set and used as a index for a small `cache`

.

## Note

My cache can hold the results for up to 80 days.

The result fits in `unsigned int`

for 30 days, too.

# My code

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

#include <iostream>
// memoize intermediate results

unsigned long long cache[80*2*3] = { 0 };
// recursively evaluate a day:
// days - number of days left
// absent - number of consecutive absent day (only consider up to three past days)
// late - total number of late days

unsigned long long count(unsigned int days, unsigned int absent = 0, unsigned int late = 0)
{
// too many consecutive absent days ?
if (absent == 3)
return 0;
// too late to often ?
if (late > 1)
return 0;
// all days passed ? => collect prize
if (days == 0)
return 1;
// unique ID of current parameter set
unsigned int hash = days * 2 * 3 + absent * 2 + late;
// already computed ?
if (cache[hash] != 0)
return cache[hash];
unsigned long long result;
// assume pupil is today neither late nor absent
result = count(days - 1, 0, late);
// assume pupil is absent today
result += count(days - 1, absent + 1, late);
// assume pupil is late today
result += count(days - 1, 0, late + 1);
// store result
cache[hash] = result;
return result;
}
int main()
{
unsigned int days;
std::cin >> days;
std::cout << count(days) << std::endl;
return 0;
}

This solution contains 7 empty lines, 14 comments and 1 preprocessor command.

# 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 4 | ./191`

Output:

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

__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

May 25, 2017 submitted solution

May 25, 2017 added comments

# Difficulty

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

# Links

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

Code in various languages:

Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p134.java (written by Nayuki)

# 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 190 - Maximising a weighted product | Squarefree Numbers - problem 193 >> |