Sazzon's blog

Interesting problem at work.
By Sazzon, history, 7 years ago, In English

Hi!

An interesting problem appeared at work today. I've managed to reduce the problem into what seems to be a solvable problem. Here it is:

Given an resultant array A of C elements and a list of N arrays, also with C elements. Is there a way to sum a subset of the N given arrays such that every element in the i-th position is summed with the element on the i-th position of the other array and result in the given array A? Let me give you an example:

C = 3

N = 6

A = {2,1,1}

N arrays:

1 = {1,0,1} 2 = {1,1,0} 3 = {1,0,1} 4 = {1,0,0} 5 = {0,1,1} 6 = {0,1,0}

The best answer is both 1 and 2 or 2 and 3. If we sum 1,0,1 + 1,1,0 = 2,1,1 or 1,1,0 + 1,0,1 = 2,1,1.

Have you ever came across a problem like this ? Is there any problem here in codeforces which has the same solution or editorial ? Do you know any technique that maybe useful for this purpose. If you have any input, please feel more than welcome to share.

Thank you in advance :-)

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

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It's basically a multidimensional knapsack.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it harder to understand than traditional knapsack ? Because I'm also with problems trying to understand the traditional.

    :-\

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's exactly the same, but with adding arrays instead of adding numbers.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think I understood how it can be done. I just need to find a clever way to create this knapsack table. Thanks!

        → Reply