<< 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 of `x`

(which might take a few iterations) then I update x's node to directly point at that leader

→ subsequent calls to `find`

will terminate after one iteration

The 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.

# 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.

# 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 "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)*

# Benchmark

The correct solution to the original Project Euler problem was found in 0.12 seconds on a 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=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 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

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 185 - Number Mind | Semiprimes - problem 187 >> |