<< 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 in `sets[x]`

Then I compare each bitmask (`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 of `set2`

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

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

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

# Benchmark

The correct solution to the original Project Euler problem was found in less than 0.01 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(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

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

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 105 - Special subset sums: testing | Minimal network - problem 107 >> |