<< problem 185 - Number Mind | Semiprimes - problem 187 >> |
Problem 186: Connectedness of a network
(see projecteuler.net/problem=186)
Here are the records from a busy telephone system with one million users:
RecNrCallerCalled
1200007100053
2600183500439
3600863701497
.........
The telephone number of the caller and the called number in record n are Caller(n) = S_{2n-1} and Called(n) = S_{2n}
where S_{1,2,3,...} come from the "Lagged Fibonacci Generator":
For 1 <= k <= 55, S_k = [100003 - 200003k + 300007k^3] mod 1000000
For 56 <= k, S_k = [S_{k-24} + S_{k-55}] mod 1000000
If Caller(n) = Called(n) then the user is assumed to have misdialled and the call fails; otherwise the call is successful.
From the start of the records, we say that any pair of users X and Y are friends if X calls Y or vice-versa.
Similarly, X is a friend of a friend of Z if X is a friend of Y and Y is a friend of Z; and so on for longer chains.
The Prime Minister's phone number is 524287. After how many successful calls, not counting misdials,
will 99% of the users (including the PM) be a friend, or a friend of a friend etc., of the Prime Minister?
My Algorithm
There is a pretty descent description of the disjoint-set algorithm on Wikipedia (en.wikipedia.org/wiki/Disjoint-set data structure).
For each phone number (called node
in my source code) I track its "leader" and the number of friends.
A "leader" is an arbitrary person who represents the root of the current subtree. He/she doesn't have to be the prime minister.
In fact, the prime minister doesn't have to be a leader in hi/her subtree.
All persons in the same subtree share the same leader. And only the leader has the correct count of persons in that subtree.
Whenever person A calls person B then I track down their respective leaders.
If they share the same leader then nothing has to changed.
If they have different leaders then I merge both disjoint subtrees. The leader of the larger subtree will be the new leader of the joint subtree.
Whenever the subtree of the prime minister contains more than 990000 members (99% of one million) the algorithm has to finish.
My find
routine was optimized for speed:
- Wikipedia recommends a recursive solution but I wrote an iterative
- I "flatten" each tree: whenever
find
looks for the leader ofx
(which might take a few iterations) then I update x's node to directly point at that leader
find
will terminate after one iterationThe lagged Fibonacci generator needs to keep at least the last 55 values.
I keep a few more to avoid too frequent memory allocations and/or data moves.
Note
Even though it might be obvious to others, I was surprised when I saw that the actually phone number of the prime minister
doesn't really matter: the algorithm will produce the exactly same result for 99% of all phone numbers.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho "555552 10" | ./186
Output:
Note: the original problem's input 524287 99
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>
// a single phone number
struct Node
{
// choose one person to be the leader of a subtree (not necessarily the prime minister)
unsigned int leader;
// number of persons in the current subtree, value only valid for the leader
unsigned int count;
};
// all persons / phone numbers
std::vector<Node> nodes;
// return leader of current subtree
unsigned int find(unsigned int id)
{
auto current = id;
while (true)
{
auto leader = nodes[current].leader;
// stop if current node is its own leader
if (leader == current)
{
// "flatten" tree, replace former leader by actual leader
if (nodes[id].leader != leader)
nodes[id].leader = leader;
return leader;
}
// keep going, leader not found yet
current = leader;
}
}
// merge two subtrees
void merge(unsigned int x, unsigned int y)
{
// find leaders
auto rootX = find(x);
auto rootY = find(y);
// same tree ?
if (rootX == rootY)
return; // nothing left to do
// merge smaller tree into larger tree
if (nodes[rootX].count >= nodes[rootY].count)
{
nodes[rootX].count += nodes[rootY].count;
nodes[rootY].leader = rootX;
}
else
{
nodes[rootY].count += nodes[rootX].count;
nodes[rootX].leader = rootY;
}
}
// lagged Fibonacci generator
unsigned int generate()
{
// store recent output
static std::vector<unsigned int> history;
unsigned int current;
// one of the first 55 values
if (history.size() < 55)
{
auto k = history.size() + 1;
current = (300007ULL * k*k*k - 200003 * k + 100003) % 1000000;
}
else
{
current = (history[history.size() - 55] + history[history.size() - 24]) % 1000000;
// throw away history if too old
const size_t RemoveAtOnce = 100;
if (history.size() > 55 + RemoveAtOnce)
history.erase(history.begin(), history.begin() + RemoveAtOnce);
}
history.push_back(current);
return current;
}
int main()
{
// prime minister's phone 6-digit phone number
unsigned int phone = 524287;
// 99% should be friends or friends-of-friends of the prime minister
unsigned int percentage = 99;
std::cin >> phone >> percentage;
// create one million independent nodes
for (unsigned int i = 0; i < 1000000; i++)
nodes.push_back({ i, 1 });
// connect nodes
unsigned int calls = 0;
while (nodes[find(phone)].count < 1000000 * percentage / 100)
{
// randomly generate a call
auto from = generate();
auto to = generate();
// misdialled ?
if (from == to)
continue;
// valid call, connect subtrees
calls++;
merge(from, to);
}
// display result
std::cout << calls << std::endl;
return 0;
}
This solution contains 16 empty lines, 24 comments and 2 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.12 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 11 MByte.
(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
July 4, 2017 submitted solution
July 4, 2017 added comments
August 18, 2017 modified to solve Hackerrank, too
Hackerrank
see https://www.hackerrank.com/contests/projecteuler/challenges/euler186
My code solves 21 out of 21 test cases (score: 100%)
Difficulty
Project Euler ranks this problem at 60% (out of 100%).
Hackerrank describes this problem as easy.
Note:
Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.
In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is rarely an option.
Links
projecteuler.net/thread=186 - the best forum on the subject (note: you have to submit the correct solution first)
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 a new problem is published | |
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 |
I scored 13,486 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 185 - Number Mind | Semiprimes - problem 187 >> |