<< problem 371 - Licence plates | (prime-k) factorial - problem 381 >> |
Problem 375: Minimum of subsequences
(see projecteuler.net/problem=375)
Let S_n be an integer sequence produced with the following pseudo-random number generator:
S_0 = 290797
S_{n+1} = S^2_n mod 50515093
Let A(i, j) be the minimum of the numbers S_i, S_{i+1}, ... , S_j for i <= j.
Let M(N) = sum{A(i, j)} for 1 <= i <= j <= N.
We can verify that M(10) = 432256955 and M(10 000) = 3264567774119.
Find M(2 000 000 000).
My Algorithm
I wrote a bruteForce()
algorithm in a few minutes which - to my surprise - even solves the M(10000) case in less than a second.
After precomputing the first 10000 pseudo-random values it performs the following tasks for each position:
- set
minimum
to the current valuedata[i]
- go backwards until reaching the first position, compare
minimum
todata[j]
and update it according - add
minimum
to the result
It's more efficient to keep track of the positions where
data[j]
was smaller than minimum
.For example, if the next
minimum
is 5 positions away, then I can easily add 5 times the current minimum
to result
.The
search()
function implements this idea:- it has a stack
best
which contains those numbers smaller than the current number ("previous ''minimum's") and their position in the stream of pseudo-random numbers - this stack is initialized with
0
, a number smaller than anything generated bypseudoRandom
so that the stack is never empty (prevents a few corner-cases) - whenever a new pseudo-random number called
current
is generated then I reduce the stack until the top-most element is smaller thancurrent
current
and its positioni
are pushed to the stack- for all elements of the stack I add their value and their distance to the next element of the stack to
result
Alternative Approaches
My program needs just under a minute to solve the problem.
I didn't realize that pseudoRandom()
has a short cycle:
- there can be at most 50515093 different outputs (50515093 is the modulo)
- each number depends only on the previous number
- whenever the internal state becomes a number I have already seen before then a new cycle starts
- if you enable
FIND_CYCLE
then my code will almost instantly display 6308947.
... but it can dramatically reduce execution time:
- process the first cycle the same way I did
- remember the value of
result
- process the second cycle and determine how much
result
changed (let's call itdelta
) - skip 6308947 iterations of the loop and just add
delta
to theresult
- the last cycle will not be complete, process it the same way I did
A major drawback is that much more code is required for this faster algorithm.
Note
The stack best
remains quite small. It contains less than 40 values at any time.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 10000 | ./375
Output:
Note: the original problem's input 2000000000
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)
My code
… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.
#include <iostream>
#include <vector>
#include <algorithm>
// produce S1, S2, etc.
unsigned int pseudoRandom()
{
static unsigned long long state = 290797;
state *= state;
state %= 50515093;
return (unsigned int)state;
}
// basic O(n^2) algorithm, surprisingly fast for size = 10000
unsigned long long bruteForce(unsigned int size)
{
// precompute all values
std::vector<unsigned int> data = { 0 }; // dummy element to have S1,S2,... at positions 1,2,...
for (unsigned int i = 1; i <= size; i++)
data.push_back(pseudoRandom());
// just a dumb scan over all intervals
unsigned long long result = 0;
for (unsigned int i = 1; i <= size; i++)
{
auto minimum = data[i];
//for (unsigned int j = i; j <= size; j++)
for (unsigned int j = i; j >= 1; j--) // same concept as above but going backwards
{
minimum = std::min(minimum, data[j]);
result += minimum;
}
}
return result;
}
// "number" is the smallest number from its "position" to the current position
struct Minimum
{
unsigned int number;
unsigned int position;
};
// almost O(n), about a minute for size = 2*10^9
unsigned long long search(unsigned int size)
{
// basically a stack of all previous minimums
std::vector<Minimum> best;
// add an unused dummy element so that the stack never becomes empty
best.push_back({ 0, 0 });
unsigned long long result = 0;
for (unsigned int i = 1; i <= size; i++)
{
// produce next pseudo-random number
auto current = pseudoRandom();
// remove all elements larger than the current one
auto validUntil = i;
while (best.back().number >= current)
{
validUntil = best.back().position;
best.pop_back();
}
// the current value is at least the smallest value for a sequence of length 1 starting at i
best.push_back({ current, validUntil });
// add all sequences
auto last = i + 1;
for (unsigned int backwards = best.size() - 1; backwards > 0; backwards--)
{
// its the same minimum number for all those positions
unsigned long long distance = last - best[backwards].position;
result += distance * best[backwards].number;
// update position
last = best[backwards].position;
}
}
return result;
}
int main()
{
//#define FIND_CYCLE
#ifdef FIND_CYCLE
auto first = pseudoRandom();
unsigned int cycleLength = 0;
while (pseudoRandom() != first)
cycleLength++;
std::cout << "cycle length: " << cycleLength << std::endl;
#else
unsigned int limit = 2000000000;
std::cin >> limit;
//std::cout << bruteForce(limit) << std::endl;
std::cout << search(limit) << std::endl;
#endif
return 0;
}
This solution contains 14 empty lines, 17 comments and 6 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 56.6 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
(compiled for x86_64 / Linux, GCC flags: -O3 -march=native -fno-exceptions -fno-rtti -std=gnu++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
December 6, 2017 submitted solution
December 6, 2017 added comments
Difficulty
Project Euler ranks this problem at 40% (out of 100%).
Links
projecteuler.net/thread=375 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/Meng-Gen/ProjectEuler/blob/master/375.py (written by Meng-Gen Tsai)
Python github.com/roosephu/project-euler/blob/master/375.py (written by Yuping Luo)
Python github.com/smacke/project-euler/blob/master/python/375.py (written by Stephen Macke)
C++ github.com/roosephu/project-euler/blob/master/375.cpp (written by Yuping Luo)
C github.com/LaurentMazare/ProjectEuler/blob/master/e375.c (written by Laurent Mazare)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem375.java (written by Magnus Solheim Thrap)
Clojure github.com/rm-hull/project-euler/blob/master/src/euler375.clj (written by Richard Hull)
Those links are just an unordered selection of source code I found with a semi-automatic search script on Google/Bing/GitHub/whatever.
You will probably stumble upon better solutions when searching on your own. Maybe not all linked resources produce the correct result and/or exceed time/memory limits.
Heatmap
Please click on a problem's number to open my solution to that problem:
green | solutions solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too | |
yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |
gray | problems are already solved but I haven't published my solution yet | |
blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |
orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |
red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too | |
black | problems are solved but access to the solution is blocked for a few days until the next problem is published | |
[new] | the flashing problem is the one I solved most recently |
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 |
551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |
576 | 577 | 578 | 579 | 580 | 581 | 582 | 583 | 584 | 585 | 586 | 587 | 588 | 589 | 590 | 591 | 592 | 593 | 594 | 595 | 596 | 597 | 598 | 599 | 600 |
601 | 602 | 603 | 604 | 605 | 606 | 607 | 608 | 609 | 610 | 611 | 612 | 613 | 614 | 615 | 616 | 617 | 618 | 619 | 620 | 621 | 622 | 623 | 624 | 625 |
626 | 627 | 628 | 629 | 630 | 631 | 632 | 633 |
I scored 13526 points (out of 15700 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.
My username at Project Euler is stephanbrumme while it's stbrumme at Hackerrank.
Look at my progress and performance pages to get more details.
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 371 - Licence plates | (prime-k) factorial - problem 381 >> |