egor.okhterov's blog

By egor.okhterov, history, 8 years ago, translation, In English

There are n boxes. Boxes contain marbles.
Box number 1 contains 1 marble.
Box number 2 contains 2 marbles.
...
Box number n contains n marbles.

We have to choose exactly b boxes out of n original boxes, so that we would have exactly t marbles in total.

For example, if we have a set of boxes B = {1, 2, 3, 4, 5} and we have to choose b = 4 boxes to get the total target value t = 13, then we should output 1 3 4 5.

But if we have the same set of boxes B = {1, 2, 3, 4, 5} and we have to choose b = 3 boxes with the same total value of t = 13, then we have to print Impossible.


I have a simple bruteforce solution, which is working, but for too long. And I have a dynamic programming solution, which is not correct:

Bruteforce

My dp solution is not correct, because it remembers only one configuration. For example, to get target value t = 5, we can choose (1, 4) or we can choose (2, 3). My code will remember only one of those 2 choices.

The task becomes even more complicated when we are given the following constraints:
1 ≤ n ≤ 1018
1 ≤ t ≤ 106
1 ≤ b ≤ n

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can read the editorial of this problem.