<< problem 105 - Special subset sums: testing | Minimal network - problem 107 >> |
Problem 106: Special subset sums: meta-testing
(see projecteuler.net/problem=106)
Let S(A) represent the sum of elements in set A of size n.
We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:
1. S(B) != S(C); that is, sums of subsets cannot be equal.
2. If B contains more elements than C then S(B) > S(C).
For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.
Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4, only 1 of these pairs need to be tested for equality (first rule).
Similarly, when n = 7, only 70 out of the 966 subset pairs need to be tested.
For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?
NOTE: This problem is related to Problem 103 and Problem 105.
My Algorithm
Only subsets of the same size are candidates, the remaining combinations are disallowed by rule 2.
I compare two subsets pair-wise, e.g. when looking at the subsets { 1,3 } and { 2,4 } I check whether 1<2 and 3<4.
If for each of those pair the first number is smaller than the second number then the sum of the first set must be smaller than the sum of the second set
and there is no need to check for equality (rule 1).
Therefore I count how often that test fails, i.e. how often I find a number in the first subset that is larger than its partner in the second subset.
I wrote a brute-force solution quite some time ago. It solves the original problem in less than 0.01 seconds but times out for every Hackerrank test case.
Therefore I tried to find a better (= faster) algorithm. I read something about Catalan numbers (en.wikipedia.org/wiki/Catalan number)
and Dyck paths (explained in the same Wikipedia artible) - and had the correct result in less time.
However, my code was still definitely too slow for every Hackerrank test case.
My choose
function from problem 116 needs severe improvement and I'm currently out of ideas ...
Nevertheless, here is my brute force solution (which still finishes in less than 0.01 seconds) where I used a few tricks from my website bits.stephan-brumme.com .
The first step is to find all possible subsets:
- generate all 2^12 subsets as bitmasks: if the n-th bit of a bitmask is set, then the corresponding subset contains the n-th element
- store all those bitmasks/subsets where
x
bits are set insets[x]
set1
) in sets[x]
with all other bitmask (set2
) in sets[x]
:- repeatedly extract the lowest set bit:
set1
's lowest bit must be always at a lower position than the lowest bit ofset2
- clear those lowest bits and continue until all bits are cleared
Modifications by HackerRank
As mentioned before, my program is way too slow for Hackerrank: you are supposed to find the result for sets with up to
10^6 elements - and to make things worse, you have to do that for up to 30 sets within 2 seconds.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 7 | ./106
Output:
Note: the original problem's input 12
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>
// derived from bits.stephan-brumme.com/lowestBitSet.html
template <typename T>
T getLowestBit(T x)
{
return ~x & (x - 1);
}
template <typename T>
void clearLowestBit(T& x)
{
x &= x - 1;
}
int main()
{
unsigned int size = 12;
std::cin >> size;
// create all subset of { 0,1,2,...,10,11 } as bitmasks
// => if bit 2 is set then the subset contains 2
// store in sets[x] all bitmasks where x bits are set (=> with x elements)
std::vector<std::vector<unsigned int>> sets(size + 1);
// create all 2^size sets (if size=12 ==> 4096 sets)
auto numSets = 1 << size;
for (auto i = 0; i < numSets; i++)
{
auto numBits = 0;
auto reduce = i;
while (reduce != 0)
{
// clear lowest bit
clearLowestBit(reduce);
numBits++;
}
sets[numBits].push_back(i);
}
// count sets where equality has to be checked
auto count = 0;
// empty set and set with all elements don't to be checked (they are unique)
// sets with only one element must be unique, too (problem description: "strictly increasing elements")
for (unsigned int setSize = 2; setSize < size; setSize++)
{
auto setsSameSize = sets[setSize];
// compare each set with each other (of the same set size)
for (auto i = setsSameSize.begin(); i != setsSameSize.end(); i++)
for (auto j = std::next(i); j != setsSameSize.end(); j++)
{
auto set1 = *i;
auto set2 = *j;
// make sure both sets are distinct (no common bits)
if ((set1 & set2) != 0)
continue;
// set1 is always lexicographically smaller than set2,
// therefore the n-th bit of set1 must be at lower position than the n-th bit of set2
while (set1 != 0) // and set2 != 0
{
// extract lowest bit
if (getLowestBit(set1) > getLowestBit(set2))
{
// mismatch, the n-th bit of set1 is at a high position
// ==> that pair of sets needs a test for equality
count++;
break;
}
clearLowestBit(set1);
clearLowestBit(set2);
}
}
}
// show result
std::cout << count << std::endl;
return 0;
}
This solution contains 12 empty lines, 17 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
August 8, 2017 submitted solution
August 8, 2017 added comments
Difficulty
Project Euler ranks this problem at 50% (out of 100%).
Links
projecteuler.net/thread=106 - 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 105 - Special subset sums: testing | Minimal network - problem 107 >> |