<< problem 189 - Tri-colouring a triangular grid | Prize Strings - problem 191 >> |
Problem 190: Maximising a weighted product
(see projecteuler.net/problem=190)
Let S_m = (x_1, x_2, ... , x_m) be the m-tuple of positive real numbers with x_1 + x_2 + ... + x_m = m for which P_m = x_1 * x_2^2 * ... * x_m^m is maximised.
For example, it can be verified that \lfloor P_10 \rfloor = 4112 (\lfloor \rfloor is the integer part function).
Find sum{\lfloor Pm \rfloor} for 2 <= m <= 15.
My Algorithm
I implemented a randomized search:
1. start with x_1 = x_2 = ... = x_m = 1
2. choose random positions x_{from} and x_{to}
3. subtract a small delta from x_{from}, add the same delta to x_{to}
4. evaluate x_1 * x_2^2 * ... * x_m^m, if it is bigger, keep the new x_{from} and x_{to}, else undo
5. go to step 2, unless the result didn't improve for a certain number of iterations
My randomized search uses deltas 0.1, 0.01, 0.001, 0.0001, 0.00001 and 0.000001 (in that order) and aborts if no improvement
has been observed in more than 100 iterations.
You can probably reduce the number of deltas and/or iterations but these values were my initial "guess" and worked perfectly fine.
In order to provide a reproducible result, I don't invoke the standard rand()
function but provide my own simple myrand()
which always generates the same random numbers, no matter what compiler / standard library is installed on your computer.
Alternative Approaches
After submitting my result I became aware that this kind of opimization problems can be solved with Lagrance multipliers, too (see en.wikipedia.org/wiki/Lagrange_multiplier).
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 10 | ./190
Output:
Note: the original problem's input 15
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>
// configure randomized search
const unsigned int StableIterations = 100;
const double InitialDelta = 0.1;
const double FinalDelta = 0.000001;
// a simple pseudo-random number generator, result in 0 .. modulo - 1
// (produces the same result no matter what compiler you have - unlike rand() from math.h)
unsigned int myrand(unsigned int modulo)
{
// code taken from problem 185
static unsigned int seed = 0;
seed = 1103515245 * seed + 12345;
return (seed >> 16) % modulo; // modified: don't use low bits but start at bit 16
}
// randomly adjust values' elements by delta until no further change observed
double optimize(unsigned int numValues)
{
// initially all values are 1
std::vector<double> values(numValues, 1);
double best = 0;
for (double delta = InitialDelta; delta > FinalDelta; delta /= 10)
{
// abort if best value didn't change for a few iterations
unsigned int countSame = 0;
while (countSame < StableIterations)
{
countSame++;
// select two random elements
auto from = myrand(numValues);
auto to = myrand(numValues);
// must be different from each other
if (from == to)
continue;
// values[from] - delta must remain positive
if (values[from] <= delta)
continue;
// adjust values: take delta from values[from] and move it to values[to]
values[from] -= delta;
values[to] += delta;
// compute new total value
double current = 1;
for (unsigned int j = 0; j < numValues; j++)
// the following loop is the same as pow(values[j], j + 1)
for (unsigned int exponent = 1; exponent <= j + 1; exponent++)
current *= values[j];
// higher than before ?
if (best < current)
{
// yes, keep these values
best = current;
// reset counter
countSame = 0;
}
else
{
// nope, restore old values
values[from] += delta;
values[to] -= delta;
}
}
}
return best;
}
int main()
{
unsigned int limit = 15;
std::cin >> limit;
unsigned int sum = 0;
for (unsigned int m = 2; m <= limit; m++)
{
// optimize and round down
sum += (unsigned int) optimize(m);
// via Lagrance multipliers
//double k = 2.0 / (m + 1);
//double lagrange = 1;
//for (unsigned int i = 1; i <= m; i++)
// lagrange *= pow(i * k, i);
}
// print result
std::cout << sum << std::endl;
return 0;
}
This solution contains 13 empty lines, 24 comments and 2 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in less than 0.01 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
June 27, 2017 submitted solution
June 27, 2017 added comments
Difficulty
Project Euler ranks this problem at 50% (out of 100%).
Links
projecteuler.net/thread=190 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/LaurentMazare/ProjectEuler/blob/master/e190.py (written by Laurent Mazare)
Python github.com/smacke/project-euler/blob/master/python/190.py (written by Stephen Macke)
C++ github.com/roosephu/project-euler/blob/master/190.cpp (written by Yuping Luo)
Java github.com/HaochenLiu/My-Project-Euler/blob/master/190.java (written by Haochen Liu)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem190.java (written by Magnus Solheim Thrap)
Go github.com/frrad/project-euler/blob/master/golang/Problem190.go (written by Frederick Robinson)
Mathematica github.com/steve98654/ProjectEuler/blob/master/190.nb
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 |
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 189 - Tri-colouring a triangular grid | Prize Strings - problem 191 >> |