looking for efficient algorithm (non-trivial)
The problem "specification" (fancy version):

*It's Christmas! You have to buy presents!*

You have a set of already existing bundles of toys, and the corresponding price of the bundle:

    1 0 0 1 0 1 1 1 0 => 58
    0 1 0 0 1 1 1 0 0 => 27
    1 1 1 0 0 0 1 0 0 => 46
    0 0 0 0 1 1 1 1 0 => 73
    ...

Where a `1` indicates that the toy is in the bundle, and a `0` that it is not.

Now, Santa Claus promo is coming and a leftover bundle `X` is offered to you at a "special promo price". We will say `X` is a *bad* deal if there exists another bundle `Y` so that:

1. `X` is a subset of `Y`
2. `X` is more expensive than `Y`
3. `Y` contains at least `N` more presents than `X` (just to be sure)

The objective is to implement a function *`bool isBadSubset(X)`* which finds out efficiently whether `X` is good or not.

Given that there are millions of bundles, comparing it to each one is obviously not feasible. Moreover, you can take the assumption that in the existing collection of bundles, a subset of toys is always cheaper than a superset.

Tips:

- comparing whether a set is a subset or not of another set is easy
- one may limit the comparisons to set which are both *containing at least `N` more toys* and *cheaper*. However, the list might still be big.
- something in the direction of a sieve would be good

The challenge: is it possible to achieve this in constant time?

looking for efficient algorithm (non-trivial)
===

The problem "specification" (fancy version):

*It's Christmas! You have to buy presents!*

You have a set of already existing bundles of toys, and the corresponding price of the bundle:

    1 0 0 1 0 1 1 1 0 => 58
    0 1 0 0 1 1 1 0 0 => 27
    1 1 1 0 0 0 1 0 0 => 46
    0 0 0 0 1 1 1 1 0 => 73
    ...

Where a `1` indicates that the toy is in the bundle, and a `0` that it is not.

Now, Santa Claus promo is coming and a leftover bundle `X` is offered to you at a "special promo price". We will say `X` is a *bad* deal if there exists another bundle `Y` so that:

1. `X` is a subset of `Y`
2. `X` is more expensive than `Y`
3. `Y` contains at least `N` more presents than `X` (just to be sure)

The objective is to implement a function *`bool isBadSubset(X)`* which finds out efficiently whether `X` is good or not.

Given that there are millions of bundles, comparing it to each one is obviously not feasible. Moreover, you can take the assumption that in the existing collection of bundles, a subset of toys is always cheaper than a superset.

Tips:

- comparing whether a set is a subset or not of another set is easy
- one may limit the comparisons to set which are both *containing at least `N` more toys* and *cheaper*. However, the list might still be big.
- something in the direction of a sieve would be good

The challenge: is it possible to achieve this in constant time?
